Monochromatic components with many edges

DOI10.4310/JOC.2024.V15.N1.A3MaRDI QIDQ6087338zbMATH OpenFDO

Authors David Conlon, Sammy Luo, Mykhaylo Tyomkyn

Publication date 15 November 2023

Published in Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

connected componentsedge coloringRamsey theory

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Connectivity (05C40) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: Given an $r$-edge-coloring of the complete graph $K_n$, what is the largest number of edges in a monochromatic connected component? This natural question has only recently received the attention it deserves, with work by two disjoint subsets of the authors resolving it for the first two special cases, when $r=2$ or $3$. Here we introduce a general framework for studying this problem and apply it to fully resolve the $r=4$ case, showing that any $4$-edge-coloring of $K_n$ contains a monochromatic component with at least $$ edges, where the constant $frac112$ is optimal only when the coloring matches a certain construction of Gy'arf'as.

Recommendations

• Modeling, estimation, and their applications for distributed parameter systems
• scientific article; zbMATH DE number 3453478
• One More Proof of Kronecker's Theorem
• A note on power residues
• Generalized Cells in Generalized Manifolds
• scientific article; zbMATH DE number 3183246
• scientific article; zbMATH DE number 3128524
• scientific article; zbMATH DE number 3799115

Cited in

(2)

• Large monochromatic components in colorings of complete hypergraphs
• The power of many colours

This page was built for publication: Monochromatic components with many edges

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