Gallai-colorings of triples and 2-factors of \(\mathcal{B}_3\) (Q2248724): Difference between revisions

Summary: A coloring of the edges of the \(r\)-uniform complete hypergraph is a \(G_r\)-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 \(G_2\)-colorings which are often called Gallai-colorings and originates from a seminal paper of Gallai. One well-known property of \(G_2\)-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 \(G_r\)-colorings and proposed to study \(f_r(n)\), the size of the largest monochromatic component which can be found in every \(G_r\)-coloring of \(K_n^r\), the complete \(r\)-uniform hypergraph. The previous remark says that \(f_2(n) = n\) and in this note, we address the case \(r=3\). We prove that \(\lceil (n+3)/2\rceil \leq f_3(n)\leq \lceil 4n/5 \rceil\) and this determines \(f_3(n)\) for \(n<7\). We also prove that \(f_3(7)=6\) by excluding certain 2-factors from the middle layer of the Boolean lattice on seven elements.