Gallai-Colorings of Triples and 2-Factors of ℬ3

Abstract EN

A coloring of the edges of the r-uniform complete hypergraph is a Gr-coloring if there is no rainbow simplex; that is, every set of r+1 vertices contains two edges of the same color.

The notion extends G2-colorings which are often called Gallai-colorings and originates from a seminal paper of Gallai.

One well-known property of G2-colorings is that at least one color class has a spanning tree.

J.

Lehel and the senior author observed that this property does not hold for Gr-colorings and proposed to study fr(n), the size of the largest monochromatic component which can be found in every Gr-coloring of Knr, the complete r-uniform hypergraph.

The previous remark says that f2(n)=n, and in this note, we address the case r=3.

We prove that ⌈(n+3)/2⌉≤f3(n)≤⌈4n/5⌉, and this determines f3(n) for n<7.

We also prove that f3(7)=6 by excluding certain 2-factors from the middle layer of the Boolean lattice on seven elements.