On Ryser's conjecture for linear intersecting multipartite hypergraphs

Nevena Francetic, Sarada Herke, Brendan Damien McKay, Ian Wanless

Research output: Contribution to journalArticleResearchpeer-review

8 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)91-105
Number of pages15
JournalEuropean Journal of Combinatorics
Volume61
DOIs
Publication statusPublished - 1 Mar 2017

Cite this