Summary: A famous conjecture (usually called Ryser’s conjecture) that appeared in [Permutation decompositions of \((0,1)\)-matrices and decomposition transversals. Pasadena, CA: Caltech (PhD Thesis) (1971), http://thesis.library.caltech.edu/5726/1/Henderson_jr_1971.pdf] of his student J. R. Henderson, states that for an \(r\)-uniform \(r\)-partite hypergraph \(\mathcal{H}\), the inequality \(\tau(\mathcal{H})\leq(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 R. Aharoni [Combinatorica 21, No. 1, 1–4 (2001; Zbl 1107.05307)].
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\leq 5\) by A. Gyárfás [“Partition coverings and blocking sets in hypergraphs”, MTA SZTAKI Tanulmányok 71 (1977)] and Z. Tuza [“On special cases of Ryser’s conjecture”, Preprint]. 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})\leq 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.