# Rapid Mixing for Colorings via Spectral Independence

arXiv: https://arxiv.org/abs/2007.08058 · HTML: https://mlsanity.com/paper/2007.08058/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jul 2020.

## Built on by (most cited first, 4 of 4)

- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Fast Doubly-Adaptive MCMC to Estimate the Gibbs Partition Function with Weak Mixing Time Bounds](https://mlsanity.com/paper/2111.07372/) (2021)

## Abstract (arXiv)

The spectral independence approach of Anari et al. (2020) utilized recent results on high-dimensional expanders of Alev and Lau (2020) and established rapid mixing of the Glauber dynamics for the hard-core model defined on weighted independent sets. We develop the spectral independence approach for colorings, and obtain new algorithmic results for the corresponding counting/sampling problems. Let α^*≈ 1.763 denote the solution to exp(1/x)=x and let α>α^*. We prove that, for any triangle-free graph G=(V,E) with maximum degree Delta, for all q≥αDelta+1, the mixing time of the Glauber dynamics for q-colorings is polynomial in n=|V|, with the exponent of the polynomial independent of Delta and q. In comparison, previous approximate counting results for colorings held for a similar range of q (asymptotically in Delta) but with larger girth requirement or with a running time where the polynomial exponent depended on Delta and q (exponentially). One further feature of using the spectral independence approach to study colorings is that it avoids many of the technical complications in previous approaches caused by coupling arguments or by passing to the complex plane; the key improvement on the running time is based on relatively simple combinatorial arguments which are then translated into spectral bounds.