TR-2016-14

On some special cases of Ryser's conjecture

Zoltán Király, Lilla Tóthmérész



Abstract

A famous conjecture (usually called Ryser's conjecture), appeared in the Ph.D thesis of his student, J.~R.~Henderson [6], states that for an $r$-uniform $r$-partite hypergraph $\cH$ the inequality $\tau(\cH)\le(r-1)\!\cdot\! \nu(\cH)$ always holds.
 
This conjecture is widely open, except in the case of $r=2$, when it is equivalent to K\H onig's theorem [8], and in the case of $r=3$, which was proved by Aharoni in 2001 [1], using topological results from [2].
 
Here we study some special cases of Ryser's conjecture. First of all the most studied special case is when $\nu=1$, i.e., when $\cH$ is intersecting. Even for this special case, not too much is known. The case $r=2$ is an observation of Erd\H os and Rado. The cases $r=3,4$ were proved by Gy\'arf\'as, and the case $r=5$ by Tuza [11]. For $r>5$ this conjecture is also widely open. Some recent papers study this special case, e.g., see [3,10].
 
We strengthen the conjecture for intersecting hypergraphs by conjecturing the following. If an $r$-uniform $r$-partite hypergraph $\cH$ is $t$-intersecting (i.e., every two hyperedges meet in at least $t$ vertices), then $\tau(\cH)\le r-t$. We prove this conjecture for the case $t> r/4$.
 
Gy\'arf\'as [5] 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 how much fraction of the vertices can be covered by $r-1$ monochromatic components of \emph{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.


Bibtex entry:

@techreport{egres-16-14,
AUTHOR = {Kir{\'a}ly, Zolt{\'a}n and T{\'o}thm{\'e}r{\'e}sz, Lilla},
TITLE = {On some special cases of Ryser's conjecture},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-14}
}


Last modification: 5.12.2018. Please email your comments to Tamás Király!