On Ryser's conjecture for \(t\)-intersecting and degree-bounded hypergraphs

Zoltán Király¹ ; Lilla Tóthmérész²

¹Eötvös University
²Eötvös Loránd University

The electronic journal of combinatorics, Tome 24 (2017) no. 4

Résumé

A famous conjecture (usually called Ryser's conjecture) that appeared in the PhD thesis of his student, J. R. Henderson, states that for an $r$-uniform $r$-partite hypergraph $\mathcal{H}$, the inequality $\tau(\mathcal{H})\le(r-1)\!\cdot\! \nu(\mathcal{H})$ always holds. This conjecture is widely open, except in the case of $r=2$, when it is equivalent to Kőnig's theorem, and in the case of $r=3$, which was proved by Aharoni in 2001.Here we study some special cases of Ryser's conjecture. First of all, the most studied special case is when $\mathcal{H}$ is intersecting. Even for this special case, not too much is known: this conjecture is proved only for $r\le 5$ by Gyárfás and Tuza. For $r>5$ it is also widely open.Generalizing the conjecture for intersecting hypergraphs, we conjecture the following. If an $r$-uniform $r$-partite hypergraph $\mathcal{H}$ is $t$-intersecting (i.e., every two hyperedges meet in at least $t<r$ vertices), then $\tau(\mathcal{H})\le r-t$. We prove this conjecture for the case $t> r/4$.Gyárfás showed that Ryser's conjecture for intersecting hypergraphs is equivalent to saying that the vertices of an $r$-edge-colored complete graph can be covered by $r-1$ monochromatic components.Motivated by this formulation, we examine what fraction of the vertices can be covered by $r-1$ monochromatic components of different colors in an $r$-edge-colored complete graph. We prove a sharp bound for this problem.Finally we prove Ryser's conjecture for the very special case when the maximum degree of the hypergraph is two.

Détail

DOI : 10.37236/6448

Classification : 05C15, 05C65, 05B40, 05B25
Mots-clés : Ryser's conjecture, intersecting hypergraph, edge-colored graph, affine plane