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

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Cited by in corpus (17)

• 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
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• 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
• A Lattice Model for Colloidal Gels and Glasses
• Approximating the XY model on a random graph with a $q$-state clock model
• AKLT Models with Quantum Spin Glass Ground States
• Large Deviation Property of Free Energy in p-Body Sherrington-Kirkpatrick Model
• Critical properties of the four-state Commutative Random Permutation Glassy Potts model in three and four dimensions
• Random-field p-spin glass model on regular random graphs
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Spin glass behavior in a random Coulomb antiferromagnet
• The effect of quantum fluctuations on the coloring of random graphs
• Academic Meeting Scheduling Using an Antiferromagnetic Potts Model