Mathematics – Combinatorics
Scientific paper
2007-09-20
Mathematics
Combinatorics
9 pages
Scientific paper
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 \ge 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 \ge 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 \le 5$, give an almost optimal construction for $r=6$, prove that any $r$-partite intersecting hypergraph with $\tau(H) \ge 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.
Mansour Toufik
Song Chunwei
Yuster Raphael
No associations
LandOfFree
A comment on Ryser's conjecture for intersecting hypergraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A comment on Ryser's conjecture for intersecting hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A comment on Ryser's conjecture for intersecting hypergraphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-517682