pipette
ESEspañol

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold

Zhidan Li, Kuan Yang

Preprint

In the authors' words

We study the mixing time of the single-site Glauber dynamics for sampling proper \(q\)-colorings on sparse Erd\H{o}s-R\'{e}nyi random graphs \(\mathcal{G}(n, d/n)\). We prove that, whenever \(q \ge (1 + o_d(1))d\), Glauber dynamics mixes in polynomial time with high probability over \(\mathcal{G}(n, d/n)\) for all sufficiently large integer \(n\). This improves the previous bound \(q = (\alpha^* + o_d(1))d\) where \(\alpha^* = 1.7632...\) is the unique solution of \(x = \exp(1/x)\) on \([1, \infty)\) by Efthymiou, Hayes, \v{S}tefankovi\v{c}, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bez\'{a}kov\'{a}, Galanis, Goldberg, and \v{S}tefankovi\v{c} (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 50 pages