Florent Krzakala 1, Lenka Zdeborová 2
Europhysics Letters (EPL) 81 (2008) 57005
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.
- 1. Laboratoire de Physico-Chimie Théorique (LPCT),
CNRS : UMR7083 – ESPCI ParisTech - 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
CNRS : UMR8626 – Université Paris XI – Paris Sud