TY - JOUR
T1 - On Ryser's conjecture for linear intersecting multipartite hypergraphs
AU - Francetić, Nevena
AU - Herke, Sarada
AU - McKay, Brendan D.
AU - Wanless, Ian M.
N1 - Publisher Copyright:
© 2016 Elsevier Ltd
PY - 2017/3/1
Y1 - 2017/3/1
N2 - Ryser conjectured that τ⩽(r−1)ν for r-partite hypergraphs, where τ is the covering number and ν is the matching number. We prove this conjecture for r⩽9 in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex. Aharoni formulated a stronger version of Ryser's conjecture which specified that each r-partite hypergraph should have a cover of size (r−1)ν of a particular form. We provide a counterexample to Aharoni's conjecture with r=13 and ν=1. We also report a number of computational results. For r=7, we find that there is no linear intersecting hypergraph that achieves the equality τ=r−1 in Ryser's conjecture, although non-linear examples are known. We exhibit intersecting non-linear examples achieving equality for r∈{9,13,17}. Also, we find that r=8 is the smallest value of r for which there exists a linear intersecting r-partite hypergraph that achieves τ=r−1 and is not isomorphic to a subhypergraph of a projective plane.
AB - Ryser conjectured that τ⩽(r−1)ν for r-partite hypergraphs, where τ is the covering number and ν is the matching number. We prove this conjecture for r⩽9 in the special case of linear intersecting hypergraphs, in other words where every pair of lines meets in exactly one vertex. Aharoni formulated a stronger version of Ryser's conjecture which specified that each r-partite hypergraph should have a cover of size (r−1)ν of a particular form. We provide a counterexample to Aharoni's conjecture with r=13 and ν=1. We also report a number of computational results. For r=7, we find that there is no linear intersecting hypergraph that achieves the equality τ=r−1 in Ryser's conjecture, although non-linear examples are known. We exhibit intersecting non-linear examples achieving equality for r∈{9,13,17}. Also, we find that r=8 is the smallest value of r for which there exists a linear intersecting r-partite hypergraph that achieves τ=r−1 and is not isomorphic to a subhypergraph of a projective plane.
UR - http://www.scopus.com/inward/record.url?scp=85006869808&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2016.10.004
DO - 10.1016/j.ejc.2016.10.004
M3 - Article
SN - 0195-6698
VL - 61
SP - 91
EP - 105
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -