Rapid mixing from spectral independence beyond the Boolean domain

Abstract

We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [2]) from the Boolean domain to general discrete domains. This property characterises distributions with limited correlations, and implies that the corresponding Glauber dynamics is rapidly mixing. As a concrete application, we show that Glauber dynamics for sampling proper q-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree ∆ provided q ≥ (α∗ + δ)∆ where α∗ ≈ 1.763 is the unique solution to α∗ = exp (1/α∗) and δ > 0 is any constant. This is the first efficient algorithm for sampling proper q-colourings in this regime with possibly unbounded ∆. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson [19].