Improved Bounds for Randomly Sampling Colorings via Linear Programming

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

Abstract

A central conjecture in computer science and statistical physics posits that Glauber dynamics on the set of $k$-colorings of a graph $G$ with maximum degree $\Delta$ is rapidly mixing for $k \ge \Delta + 2$. Since 1999, the best known bound for general graphs was $k > \frac{11}{6}\Delta$, established by Eric Vigoda using flip dynamics. This paper breaks the $\frac{11}{6}\Delta$ barrier by identifying the specific local configurations that obstruct further progress. By employing linear programming (LP) and duality arguments, the authors demonstrate that these extremal configurations are "brittle" and can be bypassed using either variable-length coupling or a refined metric. This result provides the first improvement for general graphs in nearly two decades and extends to the more general problem of list coloring.

Introduction

Randomly sampling proper colorings of a graph is a fundamental problem in combinatorics and the study of phase transitions in physics. A proper $k$-coloring assigns one of $k$ colors to each vertex such that no two adjacent vertices share the same color. Sampling these colorings uniformly at random is a prerequisite for estimating the total number of possible colorings—a problem known to be #P-complete.

For decades, researchers have focused on Glauber dynamics, a Markov Chain Monte Carlo (MCMC) algorithm that transitions between colorings by updating a single vertex at a time. The efficiency of this algorithm is measured by its "mixing time"—the number of steps required to reach a state close to the uniform distribution. While it is conjectured that $k \ge \Delta + 2$ colors are sufficient for rapid mixing, the mathematical community remained stuck at the $k > \frac{11}{6}\Delta$ threshold established by Vigoda in 1999.

The $\frac{11}{6}\Delta$ Barrier

The $\frac{11}{6}$ limit was long considered a "natural barrier" for the path coupling technique, a standard method for proving mixing times. In path coupling, one attempts to show that the distance between two colorings (typically measured by the Hamming distance) decreases on average in a single step. At $k = \frac{11}{6}\Delta$, there exist specific local graph structures where the expected distance does not decrease, causing the standard proof technique to fail.

Methodology: Linear Programming as a Diagnostic

The authors of this paper approached the problem by treating the analysis of the coupling as a Linear Programming (LP) problem. In this framework, the constraints of the LP represent various local color configurations. By analyzing the dual of this LP, the researchers were able to precisely characterize the "extremal configurations"—the specific arrangements of colors that make the $\frac{11}{6}$ bound tight.

Bypassing Obstructions

Once the obstructions were identified, the authors developed two distinct strategies to prove that the algorithm still converges efficiently:

  1. Variable-Length Coupling: Instead of requiring the distance between colorings to decrease in every single step, the authors analyzed the dynamics over a random window of time. They proved that the problematic extremal configurations are "brittle"; they are likely to break apart into more favorable configurations before the coupling window terminates.
  2. Alternative Metrics: The authors designed a new metric to measure the distance between colorings. Unlike the standard Hamming distance, which treats all color differences equally, this new metric assigns higher weights to the extremal configurations. Under this refined lens, the algorithm can be shown to make progress even when it appears stalled under the Hamming metric.

Key Results

The primary contribution of this work is the proof that Glauber dynamics is rapidly mixing for $k \ge (\frac{11}{6} - \epsilon_0)\Delta$ for a small constant $\epsilon_0 > 0$. While the numerical value of $\epsilon_0$ is small (approximately $10^{-5}$), the theoretical impact is significant as it proves the $\frac{11}{6}$ limit is not a fundamental lower bound for general graphs.

Furthermore, the paper provides significant improvements for list coloring, a generalization where each vertex has a specific list of available colors. Previously, the best known bound for list coloring was $k > 2\Delta$. This work brings the list coloring bound down to the same $(\frac{11}{6} - \epsilon_0)\Delta$ range.

In terms of computational complexity, the authors established that the flip dynamics (a variant of the algorithm) mixes in $O(n \log n)$ time, while the standard Glauber dynamics mixes in $O(n^2)$ time under these conditions.

Conclusion and Future Work

By using Linear Programming to diagnose and resolve the bottlenecks in classical coupling proofs, this paper opens a new path toward the $\Delta + 2$ conjecture. The discovery that worst-case configurations are brittle suggests that more sophisticated multi-step analyses or even more complex metrics could further lower the bound. Future research may focus on optimizing the $\epsilon_0$ constant or applying these LP-based techniques to other Markov chains in statistical physics.

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