The power of many colours

Noga Alon, Matija Bucić, Micha Cristoph, Michael Krivelevich

This paper, authored by a "dream team" of combinatorists including Noga Alon and Michael Krivelevich, explores a fundamental question in extremal graph theory: how much "structure" can we guarantee in a graph if we are allowed to use a combination of multiple colors? By solving several long-standing problems and disproving a 2007 conjecture, the authors provide a near-complete map of how the size of connected components and vertex coverage scales as you increase the number of allowed colors.

TL;DR

The researchers determine the approximate size of the largest connected component and the minimum vertex coverage guaranteed in any $r$-edge coloring of a complete graph when using up to $s$ colors. They disprove a major conjecture regarding the growth of these components and bridge the gap between classical single-color results and multi-color generalizations.

What Problem Does This Paper Address?

In the world of Ramsey theory, we often ask: "If I color the edges of a giant network (a complete graph $K_n$) with $r$ different colors, how big of a monochromatic (single-color) structure am I guaranteed to find?" A classic 1967 result by Gerencsér and Gyárfás tells us we can always find a single-color connected component covering at least $n/(r-1)$ vertices.

But what if we are allowed to pick a subset of $s$ colors? This is the "power of many colors" paradigm. The paper addresses two main functions:

  1. $f(n, r, s)$: The maximum number of vertices we can guarantee to connect using edges from any $s$ colors.
  2. $g(n, r, s)$: The minimum number of vertices incident to at least one edge of some $s$ colors (essentially a vertex-coverage problem).

Before this paper, the behavior of these functions—especially how they transition from small $s$ to large $s$—was poorly understood, with significant gaps between known upper and lower bounds.

Methods

The authors employ a sophisticated toolkit from the Probabilistic Method and Extremal Set Theory:

  • Hypergraph Reductions: They show that these graph coloring problems are equivalent to finding specific types of "intersecting hypergraphs" (collections of sets where every pair of sets overlaps).
  • Random Colorings and Blow-ups: To establish upper bounds, they use random edge colorings and "blow-up" constructions, where vertices are replaced by sets of vertices to scale small counter-examples to large $n$.
  • Probabilistic Inequalities: They utilize Janson’s Inequality and the Lovász Local Lemma (LLL) to prove the existence of specific coloring patterns, and Azuma’s Inequality for concentration results.
  • Mader’s Theorem: To handle the more general case of $k$-connectivity (where a graph remains connected even after removing $k-1$ vertices), they use Mader's structural results on dense graphs.

Datasets

Not discussed in the paper. This is a theoretical mathematics paper; results are established through formal proofs rather than empirical data or training on datasets.

Key Insights and Ideas

  • The "Aha" Moment on Growth: Previous researchers (Liu, Morris, and Prince, 2007) conjectured that the size of the largest component $f$ might grow exponentially in $s$. This paper disproves that in a strong form, showing that for a significant range ($s \le \sqrt{r}$), the growth is essentially quadratic ($\approx s^2/r$).
  • Divergence and Convergence: A major insight is that $f$ (connectivity) and $g$ (coverage) behave very differently when $s$ is small. For $s=1$, $f$ is roughly $n/r$ while $g$ is roughly $n/\sqrt{r}$. However, as $s$ grows toward $\sqrt{r \log r}$, these two functions converge and begin to exhibit the same asymptotic behavior.
  • The Power of $s=2$: The authors highlight that even moving from one color to two provides a massive jump in connectivity, which they quantify more precisely than previous literature.

Key Results

  • Theorem 1.1 (Small $s$): For very small $s$, they show $f(n, r, s) = \Theta(2^s/r) \cdot n$. This confirms that connectivity initially grows exponentially, but only for a very short range.
  • Theorem 1.2 (Intermediate $s$): For $1 \le s \le \sqrt{r}$, they prove $f(n, r, s) = \tilde{\Theta}_r(s^2/r) \cdot n$, effectively disproving the 2007 conjecture that suggested exponential growth in this regime.
  • Theorem 1.4 (The $g$ function): They provide a complete asymptotic characterization of $g(n, r, s)$ for the entire range of $1 \le s \le r$, identifying five distinct regimes of behavior.
  • Asymptotic Tightness: For the range $s \ge \sqrt{r \log r}$, they show that the guaranteed structure covers almost the entire graph: $f(n, r, s) = (1 - e^{-\Theta(s^2/r)})n$.

Limitations and Future Work

  • The Logarithmic Gap: While the authors determined the behavior of $f$ up to a constant factor for most ranges, there remains a "logarithmic term" of uncertainty in the transition zone where $s \approx \log \log r$.
  • Conjecture 4.2: They propose a new, more refined conjecture for the exact value of $f$ when $s$ is very small, suggesting the correct factor involves a $(log r)^{1-o(1)}$ term.
  • Sparse Graphs: The current work focuses on complete graphs ($K_n$). The authors suggest that exploring these "power of many colors" questions in sparse random graphs (like $G(n, p)$) is a promising next step for the field.

Summary updated

Abstract

A classical problem, due to Gerencsér and Gyárfás from 1967, asks how large a monochromatic connected component can we guarantee in any $r$-edge colouring of $K_n$? We consider how big a connected component can we guarantee in any $r$-edge colouring of $K_n$ if we allow ourselves to use up to $s$ colours. This is actually an instance of a more general question of Bollobás from about 20 years ago which asks for a $k$-connected subgraph in the same setting. We complete the picture in terms of the approximate behaviour of the answer by determining it up to a logarithmic term, provided $n$ is large enough. We obtain more precise results for certain regimes which solve a problem of Liu, Morris and Prince from 2007, as well as disprove a conjecture they pose in a strong form. We also consider a generalisation in a similar direction of a question first considered by Erdős and Rényi in 1956, who considered given $n$ and $m$, what is the smallest number of $m$-cliques which can cover all edges of $K_n$? This problem is essentially equivalent to the question of what is the minimum number of vertices that are certain to be incident to at least one edge of some colour in any $r$-edge colouring of $K_n$. We consider what happens if we allow ourselves to use up to $s$ colours. We obtain a more complete understanding of the answer to this question for large $n$, in particular determining it up to a constant factor for all $1\le s \le r$, as well as obtaining much more precise results for various ranges including the correct asymptotics for essentially the whole range.
BibTeX
@inproceedings{alon2024power,
  author = {Noga Alon and Matija Bucić and Micha Cristoph and Michael Krivelevich},
  title = {{The power of many colours}},
  booktitle = {Forum},
  year = {2024},
  doi = {10.1017/fms.2024.120},
}
Figure