Monochromatic components in edge-colored complete uniform hypergraphs

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 , … , f } ; it defines monochromatic r -uniform hypergraphs H i = ( V , E i ) for i = 1 , … , f , where E i contains the r -tuples colored by i . The connected components of hypergraphs H i are called monochromatic components. For n > r k 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 > r k f ( n , r , k ) . A reformulation (see Gyárfás (1977) [5]) 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 ≤ 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 r k .