This paper, authored by Noga Alon and Michael Krivelevich, provides a definitive answer to a lingering question in the study of random graphs: how many colors are needed to "clique color" a dense random graph?
TL;DR
The authors prove that for a dense random graph (where any two nodes have a 50% chance of being connected), the number of colors required to ensure no maximal clique is monochromatic grows logarithmically with the number of vertices. This establishes a lower bound that matches the previously known upper bound, settling the order of magnitude for this graph invariant.
What Problem Does This Paper Address?
In traditional graph coloring, you want to color vertices so that no two adjacent vertices share a color (i.e., no edge is monochromatic). Clique coloring is a more relaxed variation: a coloring is valid if no maximal clique is monochromatic. A clique is a set of vertices where every pair is connected by an edge; it is "maximal" if it cannot be extended by adding another vertex from the graph.
While researchers had a good handle on clique coloring for "sparse" random graphs (graphs with few edges), the "dense" case—specifically the binomial random graph $G(n, 1/2)$—remained elusive. Previous work by McDiarmid, Mitsche, and Prałat had shown that $O(\log n)$ colors are sufficient, but no one had been able to prove that a similarly large number of colors was necessary. This paper fills that gap, proving the lower bound is also $\Omega(\log n)$.
Methods
The authors employ the probabilistic method, a staple of combinatorics. The proof is structured around showing that in any partition of the graph's vertices into a small number of color classes, at least one color class will inevitably contain a monochromatic maximal clique.
Key technical steps include:
- Neighborhood Lemmas: The authors prove three lemmas regarding the distribution of "non-neighbors" (missing edges) in the graph. They show that even in dense graphs, small sets of vertices have many common non-neighbors, and large sets don't have too many "outlier" vertices with weird neighborhood properties.
- Significant Sets: They define a "significant set" of vertices based on these neighborhood properties. They show that if you try to color the graph with too few colors, at least one color class must be "significant."
- Extended Janson Inequality: This is a sophisticated tool from probabilistic combinatorics used to estimate the lower tail of a sum of indicator variables. The authors use it to prove that any "significant" set of vertices is almost certain to contain a specific type of clique that is guaranteed to be maximal within the entire graph, thus forcing a monochromatic maximal clique.
Datasets
As a theoretical mathematics paper, this work does not use empirical datasets. It focuses on the mathematical properties of the Erdős–Rényi random graph model $G(n, p)$, specifically where $p = 1/2$.
Key Insights and Ideas
- The "Maximal" Constraint is the Key: The difficulty of clique coloring lies in the fact that a monochromatic clique only violates the rule if it is maximal. If a monochromatic clique is contained within a larger clique that has other colors, it’s perfectly fine.
- Forcing Maximality: The core "aha moment" is the construction in Lemma 2.3. The authors show that a significant set $Y$ (a color class) contains a clique $K$ such that every vertex outside of $Y$ is missing at least one edge to $K$. This ensures that any maximal clique containing $K$ must be entirely contained within $Y$, making that maximal clique monochromatic.
- Logarithmic Tightness: The paper demonstrates that the logarithmic behavior is a fundamental property of dense random graphs, mirroring the behavior of the standard chromatic number, though the mechanisms are different.
Key Results
- The Lower Bound: The authors prove there exists a constant $c$ such that, with high probability, the clique chromatic number $\chi_c(G(n, 1/2)) \geq c \log_2 n$.
- Tight Estimate: Combined with previous upper bounds, this settles the growth rate: $\chi_c(G(n, 1/2)) = \Theta(\log n)$.
- Generalization: The proof isn't just for $p=1/2$; it applies to any constant edge probability $p$ between 0 and 1.
Limitations and Future Work
- The Constant Factor: While the paper settles the $\Theta(\log n)$ growth, the constant $c$ provided ($1/2000$) is very small and likely not optimal. The authors acknowledge they made no attempt to optimize it.
- The Leading Constant Conjecture: The authors suggest it is "plausible" that the true value is $(1/2 + o(1)) \log n$, which would perfectly match the known upper bound.
- The Sparse Gap: For cases where the edge probability $p$ tends toward zero as $n$ grows, a gap still exists between the current upper and lower bounds. The authors note that their specific method only provides an $\Omega(\log n / \log(1/p))$ lower bound for small $p$, which is weaker than the known upper bounds in that regime.
Summary updated