Intersecting Extremal Constructions in Ryser’s Conjecture for $r$-partite Hypergraphs

Abstract

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\le 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\le 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\le f(6)\le 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)\le 22$ and $f(11)\le 51$. Our results for $f(6)$ and $f(7)$ have been obtained independently by Aharoni, Barat, and Wanless.