TR-2011-02

Monochromatic components in edge-colored complete uniform hypergraphs

Zoltán Király



Abstract

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:

@techreport{egres-11-02,
AUTHOR = {Kir{\'a}ly, Zolt{\'a}n},
TITLE = {Monochromatic components in edge-colored complete uniform hypergraphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2011},
NUMBER = {TR-2011-02}
}


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