arXiv preprint ·
Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study the mixing time of the single-site Glauber dynamics for sampling proper \(q\)-colorings on sparse Erdős-Ré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 = (α^* + o_d(1))d\) where \(α^* = 1.7632...\) is the unique solution of \(x = \exp(1/x)\) on \([1, \infty)\) by Efthymiou, Hayes, Štefankovič, 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áková, Galanis, Goldberg, and Štefankovič (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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Probability
ARRIVAL in cube-root subexponential time
Degree Stability of Parallel Greedy Matching in Random Graphs
Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings
When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
Get the few papers worth your time in Probability every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.