Discoveries / combinatorics

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

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.