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 (25)

• The Bethe lattice spin glass revisited
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Statistical physics of inference: Thresholds and algorithms
• Algorithmic barriers from phase transitions
• Reconstruction on trees and spin glass transition
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Exact solutions for diluted spin glasses and optimization problems
• Information-theoretic thresholds from the cavity method
• 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
• Information-theoretic thresholds for community detection in sparse networks
• The condensation phase transition in random graph coloring
• Finite size corrections to disordered Ising models on Random Regular Graphs
• Finite size corrections to disordered systems on Erdös-Rényi random graphs
• Harnessing the Bethe free energy
• Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models
• A positive temperature phase transition in random hypergraph 2-coloring
• Structure of 1-RSB asymptotic Gibbs measures in the diluted p-spin models
• Antiferromagnetic Potts model on the Erdos-Renyi random graph
• Planting colourings silently
• Pathwidth and nonrepetitive list coloring
• 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