Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications
Journal of the ACM · 21.08.2026
DOI: 10.1145/3837755 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 21.08.2026. Verfasst von Zongchen Chen und 3 weiteren Autor:innen. Die Arbeit nennt 55 Literaturangaben.
Abstract (Originalsprache)
Strong spatial mixing (SSM) is an important quantitative notion of correlation decay for Gibbs distributions arising in statistical physics, probability theory, and theoretical computer science. A longstanding conjecture is that the uniform distribution on proper q -colorings on a Δ -regular tree exhibits SSM whenever q ≥ Δ + 1. Moreover, it is widely believed that as long as SSM holds on bounded-degree trees with q colors, one would obtain an efficient sampler for q -colorings on all bounded-degree graphs via simple Markov chain algorithms. It is surprising that such a basic question is still open, even on trees, but then again it also highlights how much we still have to learn about random colorings. In this paper, we show the following: (1) For any Δ ≥ 3, SSM holds for random q -colorings on trees of maximum degree Δ whenever q ≥ Δ + 3. Thus we almost fully resolve the aforementioned conjecture. Our result substantially improves upon the previously best bound which requires q ≥ 1.59 Δ + γ * for an absolute constant γ * > 0. (2) For any Δ ≥ 3 and \(g=\Omega _\Delta (1) \) , we establish optimal mixing of the Glauber dynamics for q -colorings on graphs of maximum degree Δ and girth g whenever q ≥ Δ + 3. Our approach is based on a new general reduction from spectral independence on large-girth graphs to SSM on trees that is of independent interest. Using the same techniques, we also prove near-optimal bounds on weak spatial mixing (WSM), a closely-related notion to SSM, for the antiferromagnetic Potts model on trees.
Zitieren
APA
Chen, Z., Liu, K., Mani, N., & Moitra, A. (2026). Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications. Journal of the ACM. https://doi.org/10.1145/3837755
Vancouver
Chen Z, Liu K, Mani N, Moitra A. Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications. Journal of the ACM. 2026. doi:10.1145/3837755
BibTeX
@article{Chen2026,
author = {Chen, Zongchen and Liu, Kuikui and Mani, Nitya and Moitra, Ankur},
title = {Strong Spatial Mixing for Colorings on Trees and its Algorithmic Applications},
journal = {Journal of the ACM},
year = {2026},
doi = {10.1145/3837755}
}
EUVIMED