Reconstruction versus mixing for Glauber dynamics on sparse random graphs

For Gibbs measures on sparse random graphs that are locally tree-like, such as the Erdos-Renyi graph $G(n,d/n)$ or random regular graphs, non-reconstruction of the limiting measure on the associated Galton-Watson or regular tree is known to be a necessary condition for rapid mixing of local Markov chains such as Glauber dynamics, and on trees the two notions essentially coincide for well-studied models. On sparse random graphs themselves, a full characterization of when non-reconstruction guarantees rapid mixing is still lacking. The ferromagnetic Ising case is resolved (the mixing threshold sits exactly at the tree uniqueness threshold), but for antiferromagnetic systems and random constraint satisfaction measures the conjecture that Glauber dynamics mixes rapidly throughout the non-reconstruction regime remains open: for $q$-colorings rapid mixing is proven only for $q>1.763d$ against a reconstruction threshold near $d/\ln d$, and for the hard-core model only a 2025 breakthrough reaches beyond uniqueness, still a factor of two in occupancy below the reconstruction threshold. The problem is to settle, in general or per model, whether and up to which threshold non-reconstruction implies rapid mixing, and to characterize the exceptions.

Background

Many distributions of interest in computer science, statistics, and physics live on the vertices of a large sparse graph: proper $q$-colorings of a graph, independent sets weighted by a per-vertex weight parameter $\lambda$ called the fugacity (the hard-core model), Ising and Potts spin configurations, and more generally uniform measures over solutions of random constraint satisfaction problems (CSPs). A canonical family of average-case instances is the Erdos-Renyi random graph $G(n,d/n)$ on $n$ vertices with constant expected degree $d$, or random $\Delta$-regular graphs. These graphs are locally tree-like: a ball of fixed radius around a typical vertex converges, as $n\to\infty$, to the corresponding ball in an infinite tree (the Galton-Watson tree with mean offspring $d$ for $G(n,d/n)$, or the infinite $\Delta$-regular tree), a fact known as local weak convergence. The standard way to sample from such a distribution is Markov chain Monte Carlo: run a local Markov chain whose stationary distribution is the target measure, most commonly the Glauber dynamics (also called Gibbs sampling), which at each step picks a vertex uniformly at random and resamples its spin conditional on its neighbors. The chain is useful only if its mixing time, i.e. the number of steps needed to come within small total-variation distance of stationarity, is small (polynomial in $n$, conjecturally near-linear). Whether Glauber dynamics mixes rapidly on typical sparse random graphs is a central question in the rigorous theory of average-case sampling algorithms. A key structural quantity is the reconstruction problem, phrased on the limiting tree. Sample a spin at the root uniformly and broadcast it down the tree through the single-site conditional laws of the model; the model is reconstructible if the spins at depth $t$ retain non-vanishing information about the root spin as $t\to\infty$, and non-reconstructible if the root becomes asymptotically independent of a typical deep boundary. Non-reconstruction is a weak form of correlation decay, weaker than extremality of the free-boundary Gibbs measure, which is in turn weaker than uniqueness of the Gibbs state; for the ferromagnetic Ising model on the $\Delta$-regular tree, for example, uniqueness fails at $(\Delta-1)\tanh\beta=1$ while reconstruction only becomes solvable at the Kesten-Stigum threshold $(\Delta-1)\tanh^2\beta=1$. Gerschenfeld and Montanari, and later Montanari, Restrepo and Tetali, developed the framework showing that for models on random graphs the graph-level reconstruction threshold (root information under the random graph's own Gibbs measure) typically coincides with the tree threshold. Berger, Kenyon, Mossel and Peres proved that non-reconstruction is necessary for fast mixing of local chains: in the reconstructible regime, boundary information percolates and any local chain takes exponentially long. On trees the converse direction is now largely settled: Martinelli, Sinclair and Weitz proved for the Ising model on trees that non-reconstruction is equivalent to fast mixing, and they, Tetali-Vera-Vigoda-Yang, Sly-Zhang, and Restrepo-Štefankovič-Vera-Vigoda-Yang established the corresponding reconstruction-versus-mixing correspondences for colorings and the hard-core model, with the mixing transition located at the tree reconstruction threshold. On general graphs the converse can fail. For sparse random graphs, the survey of Dembo and Montanari established non-reconstructibility as a necessary condition for fast mixing of local chains, noted that the converse may in general fail, and left the graph-side sufficiency question open: only the necessary direction was known, and no characterization of when non-reconstruction guarantees rapid mixing was available.

Problem Statement

For a sequence of sparse random graphs, such as $G(n,d/n)$ with constant expected degree $d$ or random $\Delta$-regular graphs, whose neighborhoods converge locally to a tree $T$, consider the Gibbs measure of a spin system or random CSP on the graph and its single-site Glauber dynamics. A resolution is either (i) a general characterization of the relation between non-reconstruction of the graph measure in the sense of Dembo-Montanari's Definition 5.1 (root information under the random graph's own Gibbs measure; by the Gerschenfeld-Montanari framework this typically coincides with tree broadcast non-reconstruction for the models at issue here, but not in general: for ferromagnetic Ising the graph reconstruction threshold coincides with the tree uniqueness threshold rather than the Kesten-Stigum threshold) and the mixing time of the dynamics on the random graph, or (ii) a proof or disproof of the implication for one of the models below. The general characterization in (i) proves or disproves that, with high probability over the random graph, non-reconstruction implies rapid mixing (polynomial, conjecturally near-linear time) and identifies the spin systems and parameter ranges for which this implication holds or fails. The concrete surviving core is the antiferromagnetic and CSP setting, where the conjectured onset of slow mixing is the tree reconstruction threshold but proven rapid mixing stops far short of it. Concrete open instances within this core include: for $q$-colorings of $G(n,d/n)$, the gap between the proven regime $q>\alpha d$ ($\alpha\approx1.763$) and the non-reconstruction regime $q\gtrsim d/\ln d$; for the hard-core model on random $\Delta$-regular graphs, the extension of the proven regime (fugacity $O(1/\sqrt{\Delta})$, occupancy $\sim\ln\Delta/(2\Delta)$) up to the reconstruction threshold at occupancy $\sim\ln\Delta/\Delta$; and more generally the question whether a local chain can be rapidly mixing exactly up to the reconstruction threshold for every model whose non-reconstruction regime is well defined, with the resolved tree and ferromagnetic Ising cases (where phase coexistence, not reconstruction, is the first obstruction to fast mixing) as consistency requirements on any general characterization.

References

1. Amir Dembo and Andrea Montanari, Gibbs Measures and Phase Transitions on Sparse Random Graphs (2010), Brazilian Journal of Probability and Statistics 24, DOI 10.1214/09-bjps027, arXiv:0910.5460, https://arxiv.org/abs/0910.5460
2. Noam Berger, Claire Kenyon, Elchanan Mossel, and Yuval Peres, Glauber dynamics on trees and hyperbolic graphs (2005), Probability Theory and Related Fields 131, DOI 10.1007/s00440-004-0369-4, https://doi.org/10.1007/s00440-004-0369-4
3. Fabio Martinelli, Alistair Sinclair, and Dror Weitz, Glauber Dynamics on Trees: Boundary Conditions and Mixing Time (2004), Communications in Mathematical Physics 250, DOI 10.1007/s00220-004-1147-y, https://doi.org/10.1007/s00220-004-1147-y
4. Fabio Martinelli, Alistair Sinclair, and Dror Weitz, Fast mixing for independent sets, colorings, and other models on trees (2007), Random Structures & Algorithms 31, DOI 10.1002/rsa.20132, https://doi.org/10.1002/rsa.20132
5. Prasad Tetali, Juan C. Vera, Eric Vigoda, and Linji Yang, Phase transition for the mixing time of the Glauber dynamics for coloring regular trees (2012), Annals of Applied Probability 22, DOI 10.1214/11-AAP833, https://doi.org/10.1214/11-AAP833
6. Allan Sly and Yumeng Zhang, The Glauber dynamics of colorings on trees is rapidly mixing throughout the nonreconstruction regime (2017), Annals of Applied Probability 27, DOI 10.1214/16-aap1253, https://doi.org/10.1214/16-aap1253
7. Ricardo Restrepo, Daniel Štefankovič, Juan C. Vera, Eric Vigoda, and Linji Yang, Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees (2014), SIAM Journal on Discrete Mathematics, DOI 10.1137/120885498, https://doi.org/10.1137/120885498
8. Elchanan Mossel and Allan Sly, Exact thresholds for Ising-Gibbs samplers on general graphs (2013), Annals of Probability 41, DOI 10.1214/11-AOP737, arXiv:0903.2906, https://arxiv.org/abs/0903.2906
9. Elchanan Mossel and Allan Sly, Gibbs rapidly samples colorings of G(n, d/n) (2009), Probability Theory and Related Fields 148, DOI 10.1007/s00440-009-0222-x, https://doi.org/10.1007/s00440-009-0222-x
10. Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda, Sampling Random Colorings of Sparse Random Graphs (2018), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, DOI 10.1137/1.9781611975031.115, arXiv:1707.03796, https://arxiv.org/abs/1707.03796
11. Yitong Yin and Chihao Zhang, Spatial mixing and approximate counting for Potts model on graphs with bounded average degree (2015), arXiv:1507.07225, https://arxiv.org/abs/1507.07225
12. Allan Sly, Reconstruction of Random Colourings (2009), Communications in Mathematical Physics 288, DOI 10.1007/s00220-009-0783-7, https://doi.org/10.1007/s00220-009-0783-7
13. Michael Anastos, Alan Frieze, and Wesley Pegden, Constraining the Clustering Transition for Colorings of Sparse Random Graphs (2018), Electronic Journal of Combinatorics, DOI 10.37236/7040, https://doi.org/10.37236/7040
14. Nayantara Bhatnagar, Allan Sly, and Prasad Tetali, Reconstruction Threshold for the Hardcore Model (2010), Proceedings of APPROX/RANDOM 2010, arXiv:1004.3531, https://arxiv.org/abs/1004.3531
15. Xiaoyu Chen, Zejia Chen, Zongchen Chen, Yitong Yin, and Xinyuan Zhang, Rapid Mixing on Random Regular Graphs beyond Uniqueness (2025), arXiv:2504.03406, https://arxiv.org/abs/2504.03406
16. Andreas Göbel, Matthew Jenssen, Marcus Michelen, Marcus Pappik, Will Perkins, and Leon Schiller, A simple proof of rapid mixing on random regular graphs beyond uniqueness (2026), arXiv:2606.27545, https://arxiv.org/abs/2606.27545
17. Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, and David X. Wu, Fast Mixing in Sparse Random Ising Models (2024), arXiv:2405.06616, https://arxiv.org/abs/2405.06616
18. Reza Gheissari, Will Perkins, and Corrine Yap, Fixed-magnetization Ising on random graphs up to reconstruction (2025), arXiv:2511.16620, https://arxiv.org/abs/2511.16620
19. Antonio Blanca and Reza Gheissari, Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics (2021), arXiv:2107.10246, https://arxiv.org/abs/2107.10246
20. Antonio Blanca, Reza Gheissari, Heehyun Park, and Xusheng Zhang, Uniqueness and Mixing in the Low-Temperature Random-Cluster Model on Trees and Random Graphs (2026), arXiv:2604.20693, https://arxiv.org/abs/2604.20693
21. Antoine Gerschenfeld and Andrea Montanari, Reconstruction for Models on Random Graphs (2007), 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), DOI 10.1109/focs.2007.58, https://doi.org/10.1109/focs.2007.58
22. Andrea Montanari, Ricardo Restrepo, and Prasad Tetali, Reconstruction and Clustering in Random Constraint Satisfaction Problems (2011), SIAM Journal on Discrete Mathematics 25, DOI 10.1137/090755862, https://doi.org/10.1137/090755862