Potts Glass on Random Graphs

Abstract

We solve the q-state Potts model with anti-ferromagnetic interactions on large random lattices of finite coordination. Due to the frustration induced by the large loops and to the local tree-like structure of the lattice this model behaves as a mean field spin glass. We use the cavity method to compute the temperature-coordination phase diagram and to determine the location of the dynamic and static glass transitions, and of the Gardner instability. We show that for q>=4 the model possesses a phenomenology similar to the one observed in structural glasses. We also illustrate the links between the positive and the zero-temperature cavity approaches, and discuss the consequences for the coloring of random graphs. In particular we argue that in the colorable region the one-step replica symmetry breaking solution is stable towards more steps of replica symmetry breaking.

6 pages, 2 figures, 1 table

References in corpus (20)

• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• Lattice Glass Models
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Reconstruction on trees and spin glass transition
• Glass models on Bethe lattices
• A ferromagnet with a glass transition
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• On the dynamics of the glass transition on Bethe lattices
• Landscape of solutions in constraint satisfaction problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Random Graph Coloring - a Statistical Physics Approach
• The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme
• The Glassy Potts Model
• Discrete energy landscapes and replica symmetry breaking at zero temperature

Cited by in corpus (37)

• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Microscopic theory of the jamming transition of harmonic spheres
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Perspective: Gardner Physics in Amorphous Solids and Beyond
• Avalanches in mean-field models and the Barkhausen noise in spin-glasses
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• Constraint satisfaction problems with isolated solutions are hard
• Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
• Typology of phase transitions in Bayesian inference problems
• A Lattice Model for Colloidal Gels and Glasses
• The hard-core model on random graphs revisited
• Conjecture on the maximum cut and bisection width in random regular graphs
• Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
• Approximating the XY model on a random graph with a $q$-state clock model
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Aligning biological sequences by exploiting residue conservation and coevolution
• AKLT Models with Quantum Spin Glass Ground States
• A positive temperature phase transition in random hypergraph 2-coloring
• Critical properties of the four-state Commutative Random Permutation Glassy Potts model in three and four dimensions
• Spin systems on Bethe lattices
• Large Deviation Property of Free Energy in p-Body Sherrington-Kirkpatrick Model
• Antiferromagnetic Potts model on the Erdos-Renyi random graph
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Random-field p-spin glass model on regular random graphs
• Thermodynamic Construction of an One-Step Replica-Symmetry-Breaking Solution in Finite Connectivity Spin Glasses
• Spin glass phase transitions in the random feedback vertex set problem
• Mean-field phase diagram and spin glass phase of the dipolar Kagome Ising antiferromagnet
• Spin glass behavior in a random Coulomb antiferromagnet
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Soft modes in vector spin glass models on sparse random graphs
• Analytical solution to Heisenberg spin glass models on sparse random graphs and their de Almeida-Thouless line
• The effect of quantum fluctuations on the coloring of random graphs
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• The replica symmetric solution for Orthogonally Constrained Heisenberg Model on Bethe lattice