Rapid Mixing for Colorings via Spectral Independence

Understand

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 $\alpha^*\approx 1.763$ denote the solution to $\exp(1/x)=x$ and let $\alpha>\alpha^*$.