Clustering transition and Bethe-state decomposition for Gibbs measures on sparse random graphs

The Gibbs measure of a random constraint satisfaction problem on a sparse random graph, such as the uniform measure over proper q-colorings of $G(n,c/n)$, is predicted by statistical mechanics to undergo a sequence of phase transitions: a clustering transition at density $\alpha_d(q)$ where the solution set shatters into exponentially many well-separated clusters, a condensation transition at $\alpha_c(q)$ where all but boundedly many clusters vanish, and a satisfiability threshold. Dembo and Montanari's lecture notes (arXiv:0910.5460) posed the rigorous validation of this picture as an open problem: the clustering transition, its conjectured coincidence with the reconstruction threshold of the associated tree model, the cluster complexity function $\Sigma(\alpha)$, and a general theory of Bethe states for diluted models were all unproven. Subsequent work resolved the replica-symmetric phase and the condensation threshold for large alphabets, and made one-step replica symmetry breaking rigorous for the random regular NAE-SAT family, but the clustering threshold and cluster geometry for q-colorings and a general Bethe-state decomposition theory remain open.

Background

A random constraint satisfaction problem (CSP) on a sparse random graph, such as the Erdos-Renyi graph $G(n,c/n)$ with average degree $c$, or a random $(k+1)$-regular graph, asks for assignments of spins or colors to vertices that satisfy local constraints, e.g. proper $q$-colorings in which adjacent vertices receive different colors. The uniform probability measure over solutions, written $\mu_G(\cdot)$, is the Gibbs measure of a diluted (finite-degree factor-graph) model, and its log-partition function per vertex, the free entropy, governs the typical number of solutions. Because such graphs are locally tree-like, physicists apply belief propagation (an iterative message-passing algorithm that computes marginals on trees exactly) and the Bethe-Peierls approximation, which predicts marginals and free entropy from a set of cavity messages. A Gibbs measure is a Bethe state when it is actually well approximated, locally, by such a message set; Bethe states are the diluted analogues of pure extremal Gibbs states on infinite lattices, and the central unproven assumption of the cavity method is that the Gibbs measure of a random CSP decomposes (up to small errors) into a convex combination of extremal Bethe states. Dembo and Montanari proved this implication conditionally: under a correlation-decay (extremality) hypothesis, the measure is Bethe approximable. For proper $q$-colorings, statistical mechanics predicts a four-regime phase diagram in the constraint density $\alpha$ (the ratio of constraints to variables, i.e. half the average degree for graph constraints): (I) below a clustering threshold $\alpha_d(q)$ the solution set forms a single compact lump and the measure is approximately spherical, meaning two independent samples have an asymptotically uniform joint color-type matrix; (II) for $\alpha_d(q)<\alpha<\alpha_c(q)$ the measure exhibits coexistence (clustering): the solution set splits into exponentially many clusters separated by linear Hamming distance, the restriction of the measure to each cluster is Bethe approximable, and the exponential growth rate of the number of clusters of size $s$ is described by a size-resolved complexity function $\Sigma_s$, whose maximum over $s$ is the equilibrium complexity $\Sigma(\alpha)$ at density $\alpha$; (III) for $\alpha_c(q)<\alpha<\alpha_s(q)$ condensation occurs, with all but a stochastically bounded number of clusters carrying negligible weight; (IV) beyond the colorability threshold $\alpha_s(q)$ no solutions exist. Mézard and Montanari conjectured that $\alpha_d(q)$ coincides with the reconstruction threshold of the tree model: the reconstruction problem asks whether the root spin of a broadcast model on a Galton-Watson tree (the random rooted tree generated by giving each vertex an independent number of offspring drawn from a fixed distribution, here Poisson with mean $2\alpha$, the local limit of the graph ensemble) retains nontrivial information about the spins at depth $t$ as $t\to\infty$; in the broadcast model the root spin is drawn from its marginal law and each child's spin from the conditional law given its parent's spin (for colorings, uniformly among the colors different from the parent's). The reconstruction threshold was the only ingredient of this picture that the notes established for colorings, via Sly's analysis of reconstruction of random colourings on trees. The clustering prediction is the physical mechanism behind the one-step replica symmetry breaking (1RSB) scheme of the cavity method, in which the complexity function $\Sigma$ plays the role of a free entropy over clusters, and it underlies predicted algorithmic barriers: local Markov-chain (Glauber) dynamics are expected to mix slowly once the measure splits into clusters. By 2009-2010 essentially none of the clustered regime had been made rigorous: for XORSAT (a CSP of linear equations modulo 2) the critical densities were known, with the transition governed by the emergence of the 2-core (the largest subhypergraph in which every vertex lies in at least two constraints), but the notes themselves state that even there the coexistence picture was not completely proved, and the order of the next term in the finite-size scaling expansion beyond $n^{-1/6}$ was also open.

Problem Statement

Establish rigorously, or refute, the conjectured cluster (Bethe-state) decomposition of Gibbs measures of random constraint satisfaction problems on sparse random graphs, in the flagship instance of proper $q$-colorings and in its general form. Concretely, for the uniform measure $\mu_G(\cdot)$ over proper $q$-colorings of the random graph $G(n,2\alpha/n)$ of average degree $2\alpha$ (equivalently, a uniformly chosen graph with $\lfloor\alpha n\rfloor$ edges), so that $\alpha$ is the constraint density, the ratio of edges to vertices (for a random $(k+1)$-regular graph ensemble the average degree is instead fixed at $k+1$ rather than continuously tunable): (1) prove that there is a sharp clustering (coexistence) threshold $\alpha_d(q)$ such that below it $\mu_G$ has no coexistence and is approximately spherical, while above it, up to the condensation threshold $\alpha_c(q)$, $\mu_G$ exhibits coexistence in the formal sense of the source: with high probability there exist $\epsilon,C>0$ and, for each $n$, a partition of the configuration space into $N_n$ sets $\{\Omega_{\ell,n}\}$ whose relative boundary mass is exponentially small, $\mu_G(\partial_\epsilon\Omega_{\ell,n})/\mu_G(\Omega_{\ell,n})\le e^{-Cn}$ (where $\partial_\epsilon\Omega=\{x:1\le d(x,\Omega)\le n\epsilon\}$ is the $\epsilon$-boundary in Hamming distance), together with a typical subfamily of the partition that carries all but exponentially small $\mu_G$-mass and consists of $e^{n\Sigma(\alpha)+o(n)}$ clusters, each of mass $e^{-n\Sigma(\alpha)+o(n)}$, and such that the restriction of $\mu_G$ to each dominant cluster is Bethe approximable — the formal version of the predicted picture in which the solution set splits into exponentially many well-separated clusters, each internally connected at a sublinear scale; (2) determine the complexity function $\Sigma(\alpha)$, the equilibrium complexity at density $\alpha$ (the maximum over cluster sizes $s$ of the size-resolved complexity $\Sigma_s$ that gives the exponential rate of the number of clusters of size $s$), as predicted by the one-step-replica-symmetry-breaking cavity method; and (3) decide whether $\alpha_d(q)$ coincides with the reconstruction threshold $\alpha_r(q)$ of the associated tree (broadcast) model, as conjectured by Mézard and Montanari. In general form: construct a mathematical theory that, for broad classes of constraint specifications $\psi$ on locally tree-like random graphs, decomposes the canonical Gibbs measure into extremal Bethe states with the predicted cluster statistics, following the broad decomposition conjecture stated in the source; the intended class includes both permissive specifications in the sense of the source's Definition 1.1 (there exist 'permitted' spin values $x^p_i$ with $\min_{(i,j)\in E,\,x'}\psi_{ij}(x^p_i,x')\ge\kappa\psi_{\max}$ for some $\kappa>0$, under which the source's conditional Bethe-approximability theorem is proved) and hard-constraint specifications such as proper $q$-colorings ($\psi_{ij}(x,y)=I(x\neq y)$), which admit no such permitted state.

References

1. Dembo, A. and Montanari, A. (2010). Gibbs measures and phase transitions on sparse random graphs. Brazilian Journal of Probability and Statistics 24(2), 137-211. DOI 10.1214/09-BJPS027. https://doi.org/10.1214/09-BJPS027 (arXiv:0910.5460, https://arxiv.org/abs/0910.5460)
2. Mézard, M. and Montanari, A. (2006). Reconstruction on trees and spin glass transition. Journal of Statistical Physics 124, 1317-1350. DOI 10.1007/s10955-006-9162-3. https://doi.org/10.1007/s10955-006-9162-3
3. Krząkała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G. and Zdeborová, L. (2007). Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences 104, 10318-10323. DOI 10.1073/pnas.0703685104. https://doi.org/10.1073/pnas.0703685104
4. Zdeborová, L. and Krząkała, F. (2007). Phase transitions in the coloring of random graphs. Physical Review E 76, 031131. DOI 10.1103/PhysRevE.76.031131. https://doi.org/10.1103/PhysRevE.76.031131
5. Sly, A. (2009). Reconstruction of random colourings. Communications in Mathematical Physics 288, 943-961. DOI 10.1007/s00220-009-0783-7. https://doi.org/10.1007/s00220-009-0783-7
6. Montanari, A., Restrepo, R. and Tetali, P. (2009). Reconstruction and clustering in random constraint satisfaction problems. arXiv:0904.2751. https://arxiv.org/abs/0904.2751
7. Bhatnagar, N., Vera, J., Vigoda, E. and Weitz, D. (2011). Reconstruction for colorings on trees. SIAM Journal on Discrete Mathematics 25(2), 809-826. DOI 10.1137/090755783. https://doi.org/10.1137/090755783
8. Bapst, V., Coja-Oghlan, A., Hetterich, S., Raßmann, F. and Vilenchik, D. (2015). The condensation phase transition in random graph coloring. Communications in Mathematical Physics 341, 543-606. DOI 10.1007/s00220-015-2464-z. https://doi.org/10.1007/s00220-015-2464-z (arXiv:1404.5513)
9. Coja-Oghlan, A., Efthymiou, C. and Jaafari, N. (2018). Local convergence of random graph colorings. Combinatorica 38, 341-380. DOI 10.1007/s00493-016-3394-x. https://doi.org/10.1007/s00493-016-3394-x
10. Coja-Oghlan, A., Kapetanopoulos, T. and Müller, N. (2020). The replica symmetric phase of random constraint satisfaction problems. Combinatorics, Probability and Computing 29(3), 346-422. DOI 10.1017/S0963548319000440. https://doi.org/10.1017/S0963548319000440
11. Coja-Oghlan, A., Krząkała, F., Perkins, W. and Zdeborová, L. (2018). Information-theoretic thresholds from the cavity method. Advances in Mathematics 333, 694-795. DOI 10.1016/j.aim.2018.05.029. https://doi.org/10.1016/j.aim.2018.05.029 (arXiv:1611.00814)
12. Bapst, V. and Coja-Oghlan, A. (2016). Harnessing the Bethe free energy. Random Structures and Algorithms 49, 694-741. DOI 10.1002/rsa.20692. https://doi.org/10.1002/rsa.20692
13. Ding, J., Sly, A. and Sun, N. (2014). Satisfiability threshold for random regular NAE-SAT. Proceedings of STOC 2014, 814-822. DOI 10.1145/2591796.2591862. https://doi.org/10.1145/2591796.2591862
14. Ding, J., Sly, A. and Sun, N. (2022). Proof of the satisfiability conjecture for large k. Annals of Mathematics 196. DOI 10.4007/annals.2022.196.1.1. https://doi.org/10.4007/annals.2022.196.1.1 (arXiv:1411.0650)
15. Sly, A., Sun, N. and Zhang, Y. (2016). The number of solutions for random regular NAE-SAT. Proceedings of FOCS 2016, 724-731. DOI 10.1109/FOCS.2016.82. https://doi.org/10.1109/FOCS.2016.82 (arXiv:1604.08546)
16. Nam, D., Sly, A. and Sohn, Y. (2021). One-step replica symmetry breaking of random regular NAE-SAT I. Proceedings of FOCS 2021, 310-318. DOI 10.1109/FOCS52979.2021.00039. https://doi.org/10.1109/FOCS52979.2021.00039 (arXiv:2011.14270)
17. Sly, A. and Sohn, Y. (2024). Local geometry of NAE-SAT solutions in the condensation regime. Proceedings of STOC 2024, 1083-1093. DOI 10.1145/3618260.3649781. https://doi.org/10.1145/3618260.3649781 (arXiv:2305.17334)
18. Panchenko, D. (2014). Structure of 1-RSB asymptotic Gibbs measures in the diluted p-spin models. Journal of Statistical Physics 155, 1-22. DOI 10.1007/s10955-014-0955-5. https://doi.org/10.1007/s10955-014-0955-5
19. Panchenko, D. (2015). Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models. Journal of Statistical Physics 162, 1-42. DOI 10.1007/s10955-015-1385-8. https://doi.org/10.1007/s10955-015-1385-8
20. Bartha, Z., Sun, N. and Zhang, Y. (2019). Breaking of 1RSB in random regular MAX-NAE-SAT. Proceedings of FOCS 2019, 1405-1416. DOI 10.1109/FOCS.2019.00086. https://doi.org/10.1109/FOCS.2019.00086
21. Anastos, M., Frieze, A. and Pegden, W. (2018). Constraining the clustering transition for colorings of sparse random graphs. Electronic Journal of Combinatorics 25(1). DOI 10.37236/7040. https://doi.org/10.37236/7040
22. Budzynski, L. and Semerjian, G. (2020). The asymptotics of the clustering transition for random constraint satisfaction problems. Journal of Statistical Physics 181, 1490-1522. DOI 10.1007/s10955-020-02635-8. https://doi.org/10.1007/s10955-020-02635-8 (arXiv:1911.09377)
23. Mossel, E., Weitz, D. and Wormald, N. (2008). On the hardness of sampling independent sets beyond the tree threshold. Probability Theory and Related Fields 143, 401-439. DOI 10.1007/s00440-007-0131-9. https://doi.org/10.1007/s00440-007-0131-9
24. Helmuth, T., Jenssen, M. and Perkins, W. (2023). Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs. Annales de l'Institut Henri Poincare Probabilites et Statistiques 59. DOI 10.1214/22-aihp1263. https://doi.org/10.1214/22-aihp1263
25. Coja-Oghlan, A., Kang, M., Krieg, L. and Rolvien, M. (2024). The k-XORSAT threshold revisited. Electronic Journal of Combinatorics 31(1). DOI 10.37236/11815. https://doi.org/10.37236/11815
26. Mossel, E., Sly, A. and Sohn, Y. (2023). Exact phase transitions for stochastic block models and reconstruction on trees. Proceedings of STOC 2023. DOI 10.1145/3564246.3585155. https://doi.org/10.1145/3564246.3585155 (arXiv:2212.03362, https://arxiv.org/abs/2212.03362)