Rapid Mixing from Spectral Independence beyond the Boolean Domain

Weiming Feng*, Heng Guo, Yitong Yin, Chihao Zhang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We extend the notion of spectral independence (introduced by Anari, Liu, and Oveis Gharan [4]) 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 𝑞-colourings mixes in polynomial-time for the family of triangle-free graphs with maximum degree Δ provided 𝑞 ≥ (𝛼 ∗ + 𝛿 )Δ where 𝛼 ∗ ≈ 1.763 is the unique solution to 𝛼 ∗ = exp (1/𝛼 ∗ ) and 𝛿 > 0 is any constant. This is the first efficient algorithm for sampling proper 𝑞-colourings in this regime with possibly unbounded Δ. Our main tool of establishing spectral independence is the recursive coupling by Goldberg, Martin, and Paterson.
Original languageEnglish
Article number28
Number of pages33
JournalACM Transactions on Algorithms
Issue number3
Early online date27 Apr 2022
Publication statusPublished - 11 Oct 2022


  • graph colouring
  • Markov chain Monte Carlo
  • spectral independence


Dive into the research topics of 'Rapid Mixing from Spectral Independence beyond the Boolean Domain'. Together they form a unique fingerprint.

Cite this