Charting the replica symmetric phase

Abstract

Diluted mean-field models are spin systems whose geometry of interactions is induced by a sparse random graph or hypergraph. Such models play an eminent role in the statistical mechanics of disordered systems as well as in combinatorics and computer science. In a path-breaking paper based on the non-rigorous `cavity method', physicists predicted not only the existence of a replica symmetry breaking phase transition in such models but also sketched a detailed picture of the evolution of the Gibbs measure within the replica symmetric phase and its impact on important problems in combinatorics, computer science and physics [Krzakala et al.: PNAS 2007]. In this paper we rigorise this picture completely for a broad class of models, encompassing the Potts antiferromagnet on the random graph, the $k$-XORSAT model and the diluted $k$-spin model for even $k$. We also prove a conjecture about the detection problem in the stochastic block model that has received considerable attention [Decelle et al.: Phys. Rev. E 2011].

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The high temperature region of the Viana-Bray diluted spin glass model
• The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
• The cavity method at zero temperature
• The number of satisfying assignments of random regular k-SAT formulas
• On the number of solutions in random graph $k$-colouring

Cited by in corpus (9)

• Typology of phase transitions in Bayesian inference problems
• Spin systems on Bethe lattices
• Metastability of the Potts ferromagnet on random regular graphs
• The replica symmetric phase of random constraint satisfaction problems
• Strong replica symmetry for high-dimensional disordered log-concave Gibbs measures
• Random-link matching problems on random regular graphs
• Satisfiability Thresholds for Regular Occupation Problems
• Breaking of 1RSB in random MAX-NAE-SAT
• Frozen $1$-RSB structure of the symmetric Ising perceptron