Monochromatic components with many edges in random graphs

Hannah Fox, Sammy Luo ∗ · 2025

Read Monochromatic components with many edges in random graphs by Hannah Fox, Sammy Luo ∗ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-01766.txt.

Introduction

Hannah Fox and Sammy Luo study how large a single color linked group must be inside colored random graphs. Color the edges of a full graph with several colors, and linked groups of one color form. A classic build shows some colorings keep all such groups small. A past conjecture claims larger groups can always be forced, and it is proven for some color counts.

Fox and Luo move the question to sparse random graphs and to graphs where each point has many links. They extend key steps from the full graph work to both new settings. Analogues of the known bound hold for all color counts in both settings. The tight case for three colors also carries over to the high link setting.

Catalog record

CREATORHannah Fox, Sammy Luo ∗
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-01766

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Monochromatic components with many edges in random graphs Thanks: ∗ Massachusetts Institute of Technology. Research supported by NSF Award No. 2303290. [email protected] Hannah Fox, Sammy Luo ∗ Abstract . In an r r -coloring of edges of the complete graph on n n vertices, how many edges are there in the largest monochromatic connected component? A construction of Gyárfás shows that for infinitely many values of r r , there exist colorings where all monochromatic components have at most ( 1 r 2 − r + o ⁡ ( 1 ) ) ​ ( n 2 ) \left(\frac{1}{r^{2}-r}+o(1)\right)\binom{n}{2} edges. Conlon, Luo, and Tyomkyn conjectured that components with at least this many edges are attainable for all r ≥ 3 r\geq 3 . Conlon, Luo, and Tyomkyn proved this conjecture for r = 3 r=3 and Luo proved it for r = 4 r=4 , along with a lower bound of 1 r 2 − r + 5 4 ​ ( n 2 ) \frac{1}{r^{2}-r+\frac{5}{4}}{n\choose 2} for all r ≥ 2 r\geq 2 and n n . In this paper, we look at extensions of this problem where the graph being r r -colored is a sparse random graph or a graph of high minimum degree. By extending several intermediate technical results from previous work in the complete graph setting, we prove analogues of the bound for general r r in both the sparse random setting and the high minimum degree setting, as well as the bound for r = 3 r=3 in the latter setting. 1. Introduction A classical observation of Erdős and Rado is that in any 2-coloring of the edges of the complete graph K_{n} , one of the two color classes consists of a single connected component on all n vertices. Gyárfás [ 4 ] extended this result, proving that for r\geq 2 , in any r -coloring of the edges of K_{n} , there is a monochromatic connected component with at least \frac{n}{r-1} vertices. He also exhibited a construction showing that this bound is tight for arbitrarily large n and infinitely many values of r . Since then, Gyárfás’s result has been further generalized in many different ways. One notable example is due to Bal and DeBiasio [ 1 ] , who showed that a similar result holds when K_{n} is replaced by an Erdős-Rényi random graph G(n,p) , which is a random graph on n vertices where each pair of vertices is adjacent with an independent probability of p . Theorem 1.1 ( [ 1 ] ) . For all r\geq 2 and sufficiently small \varepsilon>0 , there exists C such that for p\geq\frac{C}{n} , with high probability every r -coloring of G(n,p) contains a monochromatic connected component with at least (1-\varepsilon)\frac{n}{r-1} vertices. We can also ask analogous questions about the largest number of edges in a monochromatic component. Question 1.2 . If the edges of K_{n} are colored with r colors, what is the largest number of edges that some monochromatic component is guaranteed to have? This question was first studied by Conlon and Tyomkyn [ 2 ] , who showed that in the case r=2 , every such coloring contains a monochromatic component with at least \frac{2}{9}n^{2}+O(n^{3/2}) edges. Later work by Luo [ 5 ] and by Conlon, Luo, and Tyomkyn [ 3 ] resolved the cases r=3 and r=4 respectively, showing that when the edges of K_{n} are colored with 3 (resp. 4 ) colors, there always exists a monochromatic connected component with at least \frac{1}{6}\binom{n}{2} (resp. \frac{1}{12}\binom{n}{2} ) edges, and that these bounds are tight. The lower bounds in the r=3 and r=4 cases match the upper bounds arising from a close examination of Gyárfás’s construction, which shows that for infinitely many values of r (in particular, whenever r-1 is a prime power), there is an r -coloring of K_{n} where every monochromatic component has at most (\frac{1}{r(r-1)}+o(1))\binom{n}{2} edges. Conlon, Luo, and Tyomkyn conjectured that a matching lower bound holds for every value of r . Conjecture 1.3 ( [ 3 ] ) . For any positive integers n,r with r\geq 3 , in every r -coloring of the edges of K_{n} , there is some monochromatic connected component with at least \frac{1}{r(r-1)}\binom{n}{2} edges. In [ 5 ] , Luo proves a general lower bound that approximates the conjectured lower bound within a factor of 1-O(\frac{1}{r^{2}}) . Theorem 1.4 ( [ 5 ] ) . In any r -coloring of the edges of K_{n} for r\geq 2 , there is a monochromatic connected component with at least \frac{1}{r^{2}-r+\frac{5}{4}}{n\choose 2} edges. In analogy to the generalization of Gyárfás’s original result to Theorem 1.1 , in this paper we study a generalization of 1.2 for random graphs: In an r -coloring of the edges of the random graph G(n,p) , what lower bounds can we obtain (with high probability) for the number of edges in the largest monochromatic component? The answer to this question naturally depends on our choice of the density p . We may ask if there is a threshold for values of p above which the answer to the above question about G(n,p) starts to behave in a certain way with high probability, e.g. when our bounds on the number of edges in the largest monochromatic component start to behave similarly to the analogous bounds in the complete graph setting. Our main result is an analogue of Theorem 1.4 in the setting of G(n,p) for any p=\omega(\frac{\log n}{n}) . Theorem 1.5 . For any fixed integer r\geq 2 and any p=\omega(\frac{\log n}{n}) , G:=G(n,p) satisfies the following property with high probability: In every r -coloring of the edges of G , there is a monochromatic connected component with at least \frac{1}{r^{2}-r+\frac{5}{4}}|E(G)| edges. We prove this result by extending the argument used in proving Theorem 1.4 , including several technical lemmas, to the sparse random graph setting. Applying similar extensions yields a sparse random analogue of the lower bound for r=3 as well. The paper proceeds as follows. We begin in Section 2 by providing some background on previous work on 1.2 for complete graphs, including some technical tools that we will adapt for the random graph setting. We also introduce some relevant results on random graphs that will be used later in the proofs. Then, in Section 3 , we prove our main results on G(n,p) . We follow in Section 4 by investigating analogues of our questions in the setting of graphs of high minimum degree and discussing how this setting relates to the sparse random setting. We conclude by discussing some potential future directions. 2. Preliminaries All graphs studied in this paper are finite and simple. For a graph G , let E(G) and V(G) denote the sets of edges and vertices of G , respectively, and write e(G)=|E(G)| and v(G)=|V(G)| . Given subsets of vertices S,T\subseteq V(G) , let G[S] denote the induced subgraph of G on the vertex set S (i.e. G[S] is the graph on S such that two vertices v,w\in S are adjacent in G[S] if and only if they are adjacent in G ). Let E_{G}(S)=E(G[S]) , e_{G}(S)=|E_{G}(S)| , and let e_{G}(S,T) denote the number of ordered pairs (s,t)\in S\times T such that

Read the complete text