Abstract
What is the minimum number of edges that must be added to the random graph $G = G_{n,0.5}$ to increase its chromatic number $\chi(G)$ by one percent? One intuitive strategy is to add all missing edges on a set of $1.01 \chi$ vertices, creating a clique with a chromatic number of $1.01 \chi$. This approach requires, with high probability, the addition of $\Omega(n^2/\log^2 n)$ edges. This research demonstrates that this "clique-building" strategy is tight up to a constant factor. The study extends these findings to more general random graphs $G_{n,p}$ and explores a local version of the resilience question, improving upon previous results in the study of graph property resilience.
Introduction
In graph theory, the chromatic number $\chi(G)$ represents the minimum number of colors required to label the vertices of a graph such that no two adjacent vertices share the same color. For a random graph $G_{n,p}$, where $n$ is the number of vertices and $p$ is the edge probability, the chromatic number is a well-characterized value, typically concentrated around $n / (2 \log_b(np))$.
This paper addresses the concept of resilience: how much must an adversary modify a random graph to fundamentally change its properties? Specifically, the authors investigate the number of edges ($E$) or the local edge density ($H$) required to force the chromatic number to increase to at least $(1+\epsilon)\chi(G)$. While prior research by Sudakov and Vu established initial bounds, a significant gap remained between the lower bounds and the obvious strategy of creating a large clique. This work successfully closes that gap.
Methodological Framework
As a study in theoretical combinatorics, the paper utilizes rigorous probabilistic proofs rather than empirical simulations. The authors focus on the behavior of Erdős-Rényi random graphs $G_{n,p}$, using several key mathematical tools:
- Concentration Inequalities: The Alon-Kim-Spencer inequality is employed to prove that the size of a collection of independent sets remains close to its expected value, even under perturbation.
- The Technical Lemma: The core of the proof is a lemma showing that nearly-maximal independent sets in a random graph are distributed with high uniformity. This implies that even if an adversary adds many edges, large independent sets will persist that contain very few of these new, "bad" edges.
- Iterative Coloring: To establish upper bounds, the authors use an iterative algorithm: they identify a large independent set in the modified graph, assign it a color, remove those vertices, and repeat the process until the graph is fully colored.
- Turán's Theorem: This classical result provides the necessary lower bounds on independent set sizes based on the resulting edge density.
Key Insights
The Optimality of the Clique Strategy
The most straightforward way to increase a graph's chromatic number is to select a subset of vertices and turn them into a clique (a complete subgraph). The authors prove that this brute-force method is essentially optimal. To nudge the chromatic number up by even a small percentage, an adversary must perform an action as drastic as building a massive clique, requiring $\Omega(n^2/\log^2 n)$ edges.
Uniformity as a Defense
The inherent resilience of random graphs stems from the uniform distribution of their independent sets. Because these sets are "everywhere" in the graph's structure, an adversary cannot easily "clog" all of them without adding a massive number of edges. The randomness of the original graph ensures that alternative large independent sets remain available for coloring.
Principal Results
Global Resilience (Theorem 1.2)
The authors prove that for a random graph $G_{n,p}$, adding $m \approx \Omega(n^2 / \log^2 n)$ edges is necessary to increase the chromatic number by a factor of $(1+\epsilon)$. This result is "tight," matching the order of magnitude required by the clique-building benchmark.
Local Resilience (Theorem 1.3)
The paper also considers a local version of the problem: how many edges can be added to each individual vertex? They prove that an adversary can add a graph $H$ with a maximum degree $\Delta(H) \approx \epsilon n / (\log n \log \log n)$ without increasing the chromatic number beyond $(1+\epsilon)\chi(G)$. This demonstrates that the graph is resilient even against distributed, vertex-specific modifications.
Limitations and Future Directions
Despite closing the primary gap in global resilience, several questions remain:
- The $\log \log n$ Factor: The local resilience bound (Theorem 1.3) contains a $\log \log n$ factor in the denominator which the authors suspect is an artifact of the proof technique rather than a property of the graph itself. They conjecture the true threshold is higher.
- Lower-Order Increases: This research focuses on multiplicative increases (e.g., 1%). Determining the cost of increasing the chromatic number by a small additive constant (e.g., $\chi(G) + 1$) remains a difficult open problem.
- Constant Optimization: The authors focused on the scaling laws (the relationship between $n$ and $\log n$) rather than optimizing the absolute constants within the theorems, leaving room for further numerical refinement.
Summary updated