The power of many colours

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

TL;DR

This paper provides a near-complete characterization of how the size of connected components grows in a colored graph when multiple colors are used instead of just one. By bridging the gap between previously known quadratic and exponential bounds, the authors disprove long-standing conjectures and establish the correct asymptotic behavior for vertex coverage and connectivity in edge-colored complete graphs.

What Problem Does This Paper Address?

In extremal combinatorics, a classic question (Gerencsér and Gyárfás, 1967) asks: in any $r$-edge coloring of a complete graph $K_n$, how large a monochromatic connected component can we guarantee? The answer is roughly $n/(r-1)$.

This paper explores the "power of many colours" paradigm: what happens if we are allowed to use a subset of $s$ colors to form our connected component? This is a specific instance of a broader problem posed by Bollobás regarding $k$-connected subgraphs.

The authors tackle two primary functions:

  1. $f(n, r, s)$: The maximum number of vertices guaranteed to be connected using edges of up to $s$ colors in an $r$-colored $K_n$.
  2. $g(n, r, s)$: The minimum number of vertices incident to at least one edge of some $s$ colors (essentially a "0-connectivity" version or a clique-covering problem).

Before this paper, there was a significant gap in understanding $f(n, r, s)$ for small $s$, with known bounds ranging wildly between quadratic and exponential growth.

Methods

The authors employ a sophisticated mix of probabilistic and combinatorial techniques:

  • Probabilistic Method: They use random hypergraph constructions to establish upper bounds. For the $g$ function, they utilize a "nonstandard" combination of Janson’s Inequality and the Lovász Local Lemma to prove the existence of intersecting hypergraphs with specific covering properties.
  • Algebraic Constructions: Projective planes and affine planes are used to create tight examples for specific divisibility conditions, particularly when $s$ is very small.
  • Greedy Inductive Arguments: To establish lower bounds for connectivity, the authors use an inductive approach, showing that if a component isn't large enough, many vertices must send edges of many different colors toward it, allowing for the "expansion" of the component using a new color.
  • Mader’s Theorem: This classical result on graph connectivity is used to extend the results from simple connectivity ($k=1$) to higher $k$-connectivity.

Datasets

As a theoretical mathematics paper, it does not use empirical datasets. The "evaluation" consists of formal proofs that apply to the class of all complete graphs $K_n$.

Key Insights and Ideas

  • The Exponential-to-Quadratic Transition: The paper reveals a surprising shift in behavior. For very small $s$ (relative to $r$), the connectivity $f(n, r, s)$ grows exponentially as $\Theta(2^s/r) \cdot n$. However, as $s$ approaches $\sqrt{r}$, the behavior becomes quadratic: $\Theta(s^2/r) \cdot n$.
  • Connectivity vs. Coverage: A major insight is that while the connectivity function ($f$) and the coverage function ($g$) behave very differently for small $s$ (exponential vs. linear), they converge to the same asymptotic behavior once $s \ge \sqrt{r \log r}$.
  • Disproving the Liu-Morris-Prince Conjecture: The authors disprove a 2007 conjecture which suggested a more precise exponential form for $f(n, r, s)$. They show that the actual behavior is much more nuanced and transitions to a quadratic regime earlier than expected.
  • Hypergraph Duality: The authors show that the problem of finding small vertex covers in colored graphs is fundamentally equivalent to finding the minimum number of edges in intersecting hypergraphs with specific "space-restricted" properties.

Key Results

  • Theorem 1.1: For fixed $s$ and large $r$, $f(n, r, s) = \Theta(2^s / r) \cdot n$. This closes the gap for the "very small $s$" regime.
  • Theorem 1.2: For $1 \le s \le \sqrt{r}$, the paper establishes $f(n, r, s) = \Theta(s^2 / r) \cdot n$, providing the first tight bounds for this range.
  • Theorem 1.4 (The $g$ function): The authors provide a complete asymptotic map for $g(n, r, s)$ across all ranges of $s$, from $s=1$ to $s=r/2$. For example, when $s \ll \sqrt{r}$, $g(n, r, s) \approx \frac{s}{\sqrt{r}}n$.
  • Precise Small Cases: The paper solves specific cases for $r=5, 6, 7$, providing exact values for the number of vertices covered under various color constraints.

Limitations and Future Work

  • The Logarithmic Gap: In the regime where $s$ is between $\sqrt{r}$ and $\sqrt{r} \log r$, there remains a small uncertainty (a factor of $\log r$). The authors propose Conjecture 4.2 to bridge this final gap.
  • Transition Thresholds: While the paper identifies where $f$ and $g$ begin to behave similarly, the exact "meeting point" of these two functions is still an open question (Question 4.3).
  • Sparse Graphs: The current work focuses on complete graphs ($K_n$). The authors suggest that exploring these questions in sparse random graphs ($G(n, p)$) or graphs with specific minimum degree requirements is a promising next step for the field.

Summary updated

Abstract

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 we can 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 Christoph and Michael Krivelevich},
  title = {{The power of many colours}},
  booktitle = {Forum},
  year = {2024},
  doi = {10.1017/fms.2024.120},
}
Figure