Monochromatic components in edge-colored complete uniform hypergraphs

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