Menu
Ryser’s Conjecture states that for any \( r \)-partite \( r \)-uniform hypergraph, the vertex cover number is at most \( r-1 \) times the matching number. This conjecture is only known to be true for \( r \leq 3 \). For intersecting hypergraphs, Ryser’s Conjecture reduces to saying that the edges of every \( r \)-partite intersecting hypergraph can be covered by \( r-1 \) vertices. This special case of the conjecture has only been proven for \( r \leq 5 \).
It is interesting to study hypergraphs which are extremal in Ryser’s Conjecture, i.e., those hypergraphs for which the vertex cover number is exactly \( r-1 \) times the matching number. There are very few known constructions of such graphs. For large \( r \), the only known constructions come from projective planes and exist only when \( r-1 \) is a prime power. Mansour, Song, and Yuster studied how few edges a hypergraph which is extremal for Ryser’s Conjecture can have. They defined \( f(r) \) as the minimum integer so that there exists an \( r \)-partite intersecting hypergraph \( \mathcal{H} \) with \( \tau(\mathcal{H}) = r-1 \) and with \( f(r) \) edges. They showed that \( f(3) = 3 \), \( f(4) = 6 \), \( f(5) = 9 \), and \( 12 \leq f(6) \leq 15 \).
In this paper, we focus on the cases when \( r = 6, 7 \), and \( 11 \). We show that \( f(6) = 13 \), improving previous bounds. Also, by providing the first known extremal hypergraphs for the \( r = 7 \) and \( r = 11 \) case of Ryser’s Conjecture, we show that \( f(7) \leq 22 \) and \( f(11) \leq 51 \). Our results for \( f(6) \) and \( f(7) \) have been obtained independently by Aharoni, Barat, and Wanless.