|
Let $K_n^r$ denote the complete $r$-uniform hypergraph on vertex set $V=[n]$. An $f$-coloring is a coloring of the edges with colors $\{1, 2, \ldots, f\}$, it defines monochromatic $r$-uniform hypergraphs $\cH_i=(V,\cE_i)$ for $i=1,\ldots, f$, where $\cE_i$ contains the $r$-tuples colored by $i$. The connected components of hypergraphs $\cH_i$ are called monochromatic components. For $n> rk$ let $f(n,r,k)$ denote the maximum number of colors, such that in any $f$-coloring of $K_n^r$, there exist $k$ monochromatic components covering $V$. Moreover let $f(r,k)=\min_{n>rk} f(n,r,k)$. A reformulation (see \cite{Gy}) of an important special case of Ryser's conjecture states that $f(2,k)=k+1$ for all $k$. This conjecture is proved to be true only for $k\le 4$, so the value of $f(2,5)$ is not known. On the contrary, in this paper we show that for $r>2$ we can determine $f(r,k)$ exactly, and its value is $rk$.
Bibtex entry:
| AUTHOR | = | {Kir{\'a}ly, Zolt{\'a}n}, |
| TITLE | = | {Monochromatic components in edge-colored complete uniform hypergraphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2011}, |
| NUMBER | = | {TR-2011-02} |