Intersecting extremal constructions in Ryser's conjecture for r-partite hypergraphs

摘要

Ryser's Conjecture states that for any r-partite r-uniform hyper-graph the vertex cover number is at most r - 1 times the matching number. This conjecture is only known to be true for r ≤ 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 ≤ 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 exist an r-partite intersecting hypergraph H with τ(H) = r - 1 and with f(r) edges. They showed that f(3) = 3, f(4) = 6, f(5) = 9, and 12 ≤ f(6) ≤ 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 τ = 7 and r = 11 case of Ryser's Conjecture, we show that f(7) ≤ 22 and f(11) ≤ 51.