Improved Bounds for Randomly Sampling Colorings via Linear Programming

Sitan Chen, Michelle Delcourt, Ankur Moitra, Guillem Perarnau, Luke Postle

This paper, published in 2018, represents a significant breakthrough in the field of randomized algorithms and combinatorics. It tackles a long-standing open problem regarding how quickly we can randomly sample "proper colorings" of a graph.

TL;DR

The authors break a 20-year-old theoretical barrier in graph theory by proving that a standard sampling algorithm (Glauber dynamics) works efficiently even when the number of colors is slightly less than the long-standing limit of $\frac{11}{6}\Delta$. By using linear programming to identify and bypass "worst-case" graph structures, they provide the first improvement for general graphs since 1999.

What Problem Does This Paper Address?

In computer science and statistical physics, we often need to pick a "proper coloring" of a graph (where no two adjacent nodes share the same color) uniformly at random. This is essential for counting the total number of possible colorings (an NP-hard problem) and for understanding physical systems like the Potts model.

The standard tool for this is Glauber dynamics: you pick a random node and change its color to a new random valid color. The big question is: How many colors ($k$) do we need, relative to the graph's maximum degree ($\Delta$), for this process to "mix" (reach a random state) quickly?

A famous conjecture suggests that $k \ge \Delta + 2$ is enough. However, for general graphs, the best result for nearly two decades was Eric Vigoda’s 1999 proof that $k > \frac{11}{6}\Delta \approx 1.833\Delta$ is sufficient. This $\frac{11}{6}$ value became a "natural barrier" because, at that point, the standard mathematical technique used to prove speed (called "one-step path coupling") simply stops working.

Methods

The authors use Linear Programming (LP) not just as a calculation tool, but as a diagnostic lens to understand why the $\frac{11}{6}\Delta$ barrier exists.

  1. Identifying the Obstructions: They cast the analysis of the sampling algorithm as an LP problem. The "constraints" in this LP represent different local arrangements of colors. By looking at the "tight" constraints, they identified specific, rare local graph structures (extremal configurations) that prevent the algorithm from appearing to make progress in a single step.
  2. Two Bypassing Strategies: Once they knew exactly what the "bad" configurations looked like, they developed two ways to prove the algorithm still works:
  3. Variable-Length Coupling: Instead of looking at the algorithm's progress one step at a time, they analyzed it over a random window of time. They proved that these "bad" configurations are "brittle"—they break apart quickly before the window ends.
  4. Alternative Metrics: They designed a new way to measure the "distance" between two different colorings. By assigning higher "costs" to the bad configurations, they showed that the algorithm is actually making progress on average, even if it doesn't look like it using standard distance measures (Hamming distance).

Datasets

As a theoretical paper in computer science, this work does not use empirical datasets. Instead, it provides mathematical proofs that hold for all general graphs with a maximum degree $\Delta$. The authors did use computer-assisted solvers to verify the feasibility and slack of their Linear Programs for specific small-scale configurations.

Key Insights and Ideas

  • The LP "Aha Moment": The researchers realized that Vigoda’s 1999 analysis was actually an optimal solution to a specific LP. By analyzing the dual of this LP, they could see exactly which graph structures were "holding back" the proof.
  • Brittleness: A key insight was that the worst-case scenarios for the algorithm are extremely fragile. While they might stall progress for one step, the very next random move is highly likely to destroy that bad configuration.
  • List Coloring Breakthrough: The paper extends these results to "list coloring" (where every node has its own unique list of allowed colors). Previously, the best bound for list coloring was $k > 2\Delta$; this paper brings it down to the same $1.833\Delta$ level as standard coloring.

Key Results

  • Breaking the Barrier: They proved rapid mixing for $k \ge (\frac{11}{6} - \epsilon_0)\Delta$. While $\epsilon_0$ is a very small constant (roughly $10^{-5}$), the result is theoretically massive because it proves the $\frac{11}{6}$ limit is not a fundamental law of nature for general graphs.
  • Mixing Times: They established that the "flip dynamics" (a more complex version of the algorithm) mixes in $O(n \log n)$ time, and the simpler Glauber dynamics mixes in $O(n^2)$ time under these new bounds.
  • General Applicability: Unlike previous improvements that only worked for graphs with no triangles or high "girth," this result applies to any graph.

Limitations and Future Work

  • The Size of $\epsilon_0$: The improvement is mathematically significant but numerically tiny. There is still a massive gap between $1.833\Delta$ and the conjectured $\Delta + 2$ (which is $1.0\Delta + 2$).
  • Complexity of the Metric: The "alternative metric" approach is powerful but requires very delicate tuning of parameters.
  • Future Direction: The authors suggest that their LP-based approach could be used to find even better metrics or longer coupling windows, potentially pushing the bound down toward $1.5\Delta$ or further.

Summary updated

Abstract

A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of $k$-colorings of a graph $G$ on $n$ vertices with maximum degree $\Delta$ is rapidly mixing for $k\ge\Delta+2$. In FOCS 1999, Vigoda showed that the flip dynamics (and therefore also Glauber dynamics) is rapidly mixing for any $k>\frac{11}{6}\Delta$. It turns out that there is a natural barrier at $\frac{11}{6}$, below which there is no one-step coupling that is contractive with respect to the Hamming metric, even for the flip dynamics. We use linear programming and duality arguments to fully characterize the obstructions to going beyond $\frac{11}{6}$. These extremal configurations turn out to be quite brittle, and in this paper we use this to give two proofs that the Glauber dynamics is rapidly mixing for any $k\ge\left(\frac{11}{6} - \epsilon_0\right)\Delta$ for some absolute constant $\epsilon_0>0$. This is the first improvement to Vigoda's result that holds for general graphs. Our first approach analyzes a variable-length coupling in which these configurations break apart with high probability before the coupling terminates, and our other approach analyzes a one-step path coupling with a new metric that counts the extremal configurations. Additionally, our results extend to list coloring, a widely studied generalization of coloring, where the previously best known results required $k > 2 \Delta$.
BibTeX
@inproceedings{chen2019improved,
  author = {Sitan Chen and Michelle Delcourt and Ankur Moitra and Guillem Perarnau and Luke Postle},
  title = {{Improved Bounds for Randomly Sampling Colorings via Linear Programming}},
  booktitle = {SODA},
  year = {2019},
  url = {https://openreview.net/forum?id=i6KRDhY5Qy},
}

Loading related content...

Figure