TR-2016-03

Covering complete partite hypergraphs by monochromatic components

András Gyárfás, Zoltán Király



Abstract

A well-known special case of a conjecture attributed to Ryser (actually appeared in the thesis of Henderson \cite{HE}) states that $k$-partite intersecting hypergraphs have transversals of at most $k-1$ vertices. An equivalent form of the conjecture in terms of coloring of complete graphs is formulated in \cite{GY1}: if the edges of a complete graph $K$ are colored with $k$ colors then the vertex set of $K$ can be covered by at most $k-1$ sets, each connected in some color. It turned out that the analogue of the conjecture for hypergraphs can be answered: Z. Király proved \cite{KI} that in every $k$-coloring of the edges of the $r$-uniform complete hypergraph $K^r$ ($r\ge 3$), the vertex set of $K^r$ can be covered by at most $\lceil k/r \rceil$ sets, each connected in some color.
 
Here we investigate the analogue problem for complete $r$-uniform $r$-partite hypergraphs. An edge coloring of a hypergraph is called {\bf spanning} if every vertex is incident to edges of any color used in the coloring. We propose the following analogue of Ryser conjecture.
 
\noindent {\em In every spanning $(r+t)$-coloring of the edges of a complete $r$-uniform $r$-partite hypergraph, the vertex set can be covered by at most $t+1$ sets, each connected in some color.}
 
We show that the conjecture (if true) is best possible. Our main result is that the conjecture is true for $1\le t\le r-1$. We also prove a slightly weaker result for $t\ge r$, namely that $t+2$ sets, each connected in some color, are enough to cover the vertex set.
 
To build a bridge between complete $r$-uniform and complete $r$-uniform $r$-partite hypergraphs, we introduce a new notion. A hypergraph is complete $r$-uniform $(r,\ell)$-partite if it has all $r$-sets that intersect each partite class in at most $\ell$ vertices (where $1\le\ell\le r$).
 
Extending our results achieved for $\ell=1$, we prove that for any $r\ge 3,\; 2\le\ell\le r,\; k\ge 1+r-\ell$, in every spanning $k$-coloring of the edges of a complete $r$-uniform $(r,\ell)$-partite hypergraph, the vertex set can be covered by at most $1+\lfloor \frac{k-r+\ell-1}{\ell}\rfloor$ sets, each connected in some color.


Bibtex entry:

@techreport{egres-16-03,
AUTHOR = {Gy{\'a}rf{\'a}s, Andr{\'a}s and Kir{\'a}ly, Zolt{\'a}n},
TITLE = {Covering complete partite hypergraphs by monochromatic components},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2016},
NUMBER = {TR-2016-03}
}


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