A comment on Ryser's conjecture for intersecting hypergraphs
| dc.creator | Mansour, Toufik | |
| dc.creator | Song, Chunwei | |
| dc.creator | Yuster, Raphael | |
| dc.date | 2007-09-20 | |
| dc.date.accessioned | 2026-07-07T08:31:00Z | |
| dc.date.available | 2026-07-07T08:31:00Z | |
| dc.description | Let $τ(\mathcal{H})$ be the cover number and $ν(\mathcal{H})$ be the matching number of a hypergraph $\mathcal{H}$. Ryser conjectured that every $r$-partite hypergraph $\mathcal{H}$ satisfies the inequality $τ(\mathcal{H}) \leq (r-1) ν(\mathcal{H})$. This conjecture is open for all $r \ge 4$. For intersecting hypergraphs, namely those with $ν(\mathcal{H})=1$, Ryser's conjecture reduces to $τ(\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 $τ(\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 $τ(\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 $τ(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 $Θ(r)$ edges. | |
| dc.description | 9 pages | |
| dc.identifier | https://arxiv.org/abs/0709.3138 | |
| dc.identifier | http://arxiv.org/abs/0709.3138 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/138390 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C65, 05D05, 05C75 | |
| dc.title | A comment on Ryser's conjecture for intersecting hypergraphs | |
| dc.type | text |