|
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:
| 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} |