Large monochromatic components in colorings of complete hypergraphs

DOI10.1016/J.JCTA.2024.105867MaRDI QIDQ6126163zbMATH OpenOpenAlexFDO

Authors Lyuben Lichev, Sammy Luo

Publication date 9 April 2024

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2302.04487

zbMATH Keywords

blow-up constructioncoloringcombinatorial designscomplete hypergraphtight component

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Ramsey theory (05D10)

Abstract: Gy'arf'as famously showed that in every $r$-coloring of the edges of the complete graph $K_n$, there is a monochromatic connected component with at least $fracnr-1$ vertices. A recent line of study by Conlon, Tyomkyn, and the second author addresses the analogous question about monochromatic connected components with many edges. In this paper, we study a generalization of these questions for $k$-uniform hypergraphs. Over a wide range of extensions of the definition of connectivity to higher uniformities, we provide both upper and lower bounds for the size of the largest monochromatic component that are tight up to a factor of $1+o(1)$ as the number of colors grows. We further generalize these questions to ask about counts of vertex $s$-sets contained within the edges of large monochromatic components. We conclude with more precise results in the particular case of two colors.

Recommendations

• Large monochromatic components in colorings of complete 3-uniform hypergraphs
• Large monochromatic components in hypergraphs with large minimum codegree
• Large monochromatic components in expansive hypergraphs
• Monochromatic components with many edges
• Large monochromatic components and long monochromatic cycles in random hypergraphs

Cites work

• Asymptotic behavior of the chromatic index for hypergraphs
• Covering \(t\)-element sets by partitions
• Covering random graphs with monochromatic trees
• Forcing large tight components in 3-graphs
• scientific article; zbMATH DE number 487720 (Why is no real title available?)
• Large components in r-edge-colorings of K_n have diameter at most five
• Large monochromatic components and long monochromatic cycles in random hypergraphs
• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• Large monochromatic components in colorings of complete 3-uniform hypergraphs
• Large monochromatic components in edge colored graphs with a minimum degree condition
• Large monochromatic components in multicolored bipartite graphs
• Minimum degree conditions for tight Hamilton cycles
• Monochromatic components with many edges
• On Connected Components with Many Edges
• Partitioning random graphs into monochromatic components
• Ramsey numbers of trails and circuits

Cited in

(4)

• Large monochromatic components in hypergraphs with large minimum codegree
• Large monochromatic components in 3‐edge‐colored Steiner triple systems
• Large monochromatic components in expansive hypergraphs
• The power of many colours

This page was built for publication: Large monochromatic components in colorings of complete hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126163)