Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications

Nitya Mani (Massachusetts Institute of Technology) https://simons.berkeley.edu/talks/nitya-mani-massachusetts-institute-technology-2026-09-24 Local to Global Principles Strong spatial mixing (SSM) is an important quantitative notion of correlation decay that has been surprisingly challenging to establish for many natural Gibbs distributions. Notably, it has been long conjectured that random $q$-colorings on $\Delta$-regular trees exhibit SSM whenever $q ≥ \Delta + 1$. We establish that for any $\Delta \ge 3$, SSM holds for random $q$-colorings on trees of maximum degree $\Delta$ whenever $q ≥ \Delta + 3$. Using this, we also establish optimal Glauber mixing for fixed $\Delta$ and $q ≥ \Delta + 3$ when the girth of the underlying graph is sufficiently large as a function of $\Delta$.