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

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), \url{http://thesis.library.caltech.edu/5726/1/Henderson_jr_1971.pdf}] of his student \textit{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 \textit{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 \textit{A. Gyárfás} [``Partition coverings and blocking sets in hypergraphs'', MTA SZTAKI Tanulmányok 71 (1977)] and \textit{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.