Journal of Combinatorics

Volume 15 (2024)

Number 1

Monochromatic components with many edges

Pages: 59 – 75

DOI: https://dx.doi.org/10.4310/JOC.2024.v15.n1.a3

Authors

David Conlon (Department of Mathematics, California Institute of Technology, Pasadena, Calif., U.S.A.)

Sammy Luo (Department of Mathematics, Stanford University, Stanford, California, U.S.A.)

Mykhaylo Tyomkyn (Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic)

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 $\frac{1}{12} \binom{n}{2}$ edges, where the constant $\frac{1}{12}$ is optimal only when the coloring matches a certain construction of Gyárfás.

Keywords

connected components, edge coloring, Ramsey theory

2010 Mathematics Subject Classification

05C15, 05C35, 05C40, 05C55

Full Text (PDF format)

Conlon was supported by NSF Award DMS-2054452, Luo by NSF GRFP Grant DGE-1656518, and Tyomkyn by ERC Synergy Grant DYNASNET 810115 and GAČR Grant 22-19073S.

Received 26 April 2022

Accepted 20 September 2022

Published 7 November 2023