05644624

j

05644624 Mansour, Toufik Song, Chunwei Yuster, Raphael A comment on Ryser's conjecture for intersecting hypergraphs. Graphs Comb. 25, No. 1, 101-109 (2009). 2009 Springer-Verlag, Tokyo EN

doi:10.1007/s00373-008-0821-9

Summary: Let $\tau({\mathcal{H}})$ be the cover number and $\nu({\mathcal{H}})$ be the matching number of a hypergraph ${\mathcal{H}}$. Ryser conjectured that every $r$-partite hypergraph ${\mathcal{H}}$ satisfies the inequality $\tau({\mathcal{H}}) \leq (r-1) \nu ({\mathcal{H}})$. This conjecture is open for all $r \geq 4$. For intersecting hypergraphs, namely those with $\nu({\mathcal{H}}) = 1$, Ryser's conjecture reduces to $\tau({\mathcal{H}}) \leq r-1$. Even this conjecture is extremely difficult and is open for all $r \geq 6$. For infinitely many $r$ there are examples of intersecting $r$-partite hypergraphs with $\tau({\mathcal{H}}) = r-1$, demonstrating the tightness of the conjecture for such $r$. However, all previously known constructions are not optimal as they use far too many edges. How sparse can an intersecting $r$-partite hypergraph be, given that its cover number is as large as possible, namely $\tau({\mathcal{H}}) \ge r-1$? In this paper we solve this question for $r \leq 5$, give an almost optimal construction for $r = 6$, prove that any $r$-partite intersecting hypergraph with $\tau (H) \geq r - 1$ must have at least $(3-\frac{1}{\sqrt{18}})r(1-o(1)) \approx 2.764r(1-o(1))$ edges, and conjecture that there exist constructions with $\Theta (r)$ edges.