On Ryser's Conjecture for Linear Intersecting Multipartite Hypergraphs

Abstract

Ryser conjectured that $\tau \le (r-1)\nu$ for $r$-partite hypergraphs, where $\tau$ is the covering number and $\nu$ is the matching number. We prove this conjecture for $r\le 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)\nu$ of a particular form. We provide a counterexample to Aharoni's conjecture with $r=13$ and $\nu =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 $\tau =r-1$ in Ryser's conjecture, although non-linear examples are known. We exhibit intersecting non-linear examples achieving equality for $r\in \{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 $\tau =r-1$ and is not isomorphic to a subhypergraph of a projective plane.

Submitted for peer review in August 2015. An ancillary has been added. Otherwise, the results in all versions are identical

References in corpus (2)

• Multipartite hypergraphs achieving equality in Ryser's conjecture
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs

Cited by in corpus (2)

• Intersecting and $2$-intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited
• A note on extremal intersecting linear Ryser systems