Rapid mixing for spin systems on graphs of girth at least five

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\geq(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 local spectral contraction condition, including the anti-ferromagnetic Potts model with $q\geq(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.

For fixed $\delta\in(0,1)$ and all sufficiently large $\Delta$ depending only on $\delta$, Glauber dynamics for proper $q$-colorings mixes rapidly on every graph of girth at least $5$ whenever $q\ge(1+\delta)\Delta$: spectral gap $\Omega_\delta(1/n)$ and $t_{\mathrm{mix}}(\varepsilon)=O_\delta(n^2\log q+n\log(1/\varepsilon))$. An analogous theorem holds for the anti-ferromagnetic Potts model at $q\ge(1+\delta)(1-\beta)\Delta$. What it does and does not improve. On girth it is a large gain: previous results near the $(1+\delta)\Delta$ threshold needed girth at least eleven (Hayes-Vigoda, extended to constant degrees by Jain-Mizgerd-Vigoda). On the mixing rate it is weaker - those give optimal $O(n\log n)$, this gives $O(n^2\log q)$. It does not touch the folklore conjecture that mixing is rapid on every graph for $q\ge\Delta+2$; Remark 7 names spanning 4-cycles as the obstruction.