Multipartite hypergraphs achieving equality in Ryser's conjecture

Abstract

A famous conjecture of Ryser is that in an $r$-partite hypergraph the covering number is at most $r-1$ times the matching number. If true, this is known to be sharp for $r$ for which there exists a projective plane of order $r-1$. We show that the conjecture, if true, is also sharp for the smallest previously open value, namely $r=7$. For $r\in \{6,7\}$, we find the minimal number $f(r)$ of edges in an intersecting $r$-partite hypergraph that has covering number at least $r-1$. We find that $f(r)$ is achieved only by linear hypergraphs for $r\le 5$, but that this is not the case for $r\in \{6,7\}$. We also improve the general lower bound on $f(r)$, showing that $f(r)\ge 3.052r+O(1)$. We show that a stronger form of Ryser's conjecture that was used to prove the $r=3$ case fails for all $r>3$. We also prove a fractional version of the following stronger form of Ryser's conjecture: in an $r$-partite hypergraph there exists a set $S$ of size at most $r-1$, contained either in one side of the hypergraph or in an edge, whose removal reduces the matching number by 1.

Minor revisions after referee feedback

References in corpus (3)

• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Extremal Hypergraphs for Ryser's Conjecture: Home-Base Hypergraphs
• Extremal Hypergraphs for Ryser's Conjecture: Connectedness of Line Graphs of Bipartite Graphs

Cited by in corpus (6)

• On Ryser's Conjecture for Linear Intersecting Multipartite Hypergraphs
• Intersecting extremal constructions in Ryser's Conjecture for r-partite hypergraphs
• Monochromatic tree covers and Ramsey numbers for set-coloured graphs
• Covers in Partitioned Intersecting Hypergraphs
• Intersecting and $2$-intersecting hypergraphs with maximal covering number: the Erdős-Lovász theme revisited
• A note on extremal intersecting linear Ryser systems