Rapid Mixing from Spectral Independence beyond the Boolean Domain
Weiming Feng, Heng Guo, Yitong Yin, Chihao Zhang
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].