A Spectral Local-to-Global Principle for Spin Systems on Graphs with Girth At Least Five

Abstract

It is proved that, for every $\delta \in (0,1)$, the Glauber dynamics for the uniform distribution on proper $q$-colorings is rapidly mixing when $q\ge (1+\delta )\Delta$ and the underlying graph has girth at least $5$ and maximum degree $\Delta ={\Omega }_{\delta }(1)$. This result also extends to general multi-spin systems satisfying a $\text{local spectral contraction}$ condition, including the anti-ferromagnetic Potts model with $q\ge (1+\delta )(1-\beta )\Delta$. These results are achieved by a new spectral local-to-global principle on graphs with girth at least five for general multi-spin systems, and a novel Fourier analysis for Glauber dynamics on a star. The main ideas behind all the proofs were developed through several rounds of interaction with GPT-5.6 Sol Ultra.