On Ryser’s conjecture for linear intersecting multipartite hypergraphs

详细信息    查看全文

• 作者：Nevena Francetić^a ; ^{nevena.francetic@utoronto.ca} ; Sarada Herke^a ; ^b ; ^{s.herke@uq.edu.au} ; Brendan D. McKay^c ; ^{bdm@cs.anu.edu.au} ; Ian M. Wanless^a ; ^c ; ^{ian.wanless@monash.edu}
• 刊名：European Journal of Combinatorics
• 出版年：2017
• 出版时间：March 2017
• 年：2017
• 卷：61
• 期：Complete
• 页码：91-105
• 全文大小：441 K
• 卷排序：61

文摘

Ryser conjectured that τ⩽(r−1)ντ⩽(r−1)ν for rr-partite hypergraphs, where ττ is the covering number and νν is the matching number. We prove this conjecture for r⩽9r⩽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 rr-partite hypergraph should have a cover of size (r−1)ν(r−1)νof a particular form  . We provide a counterexample to Aharoni’s conjecture with r=13r=13 and ν=1ν=1.We also report a number of computational results. For r=7r=7, we find that there is no linear intersecting hypergraph that achieves the equality τ=r−1τ=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}r∈{9,13,17}. Also, we find that r=8r=8 is the smallest value of rr for which there exists a linear intersecting rr-partite hypergraph that achieves τ=r−1τ=r−1 and is not isomorphic to a subhypergraph of a projective plane.