Volume 81, Number 5, March 2008
Article Number 57005
Number of page(s) 6
Section Condensed Matter: Electronic Structure, Electrical, Magnetic and Optical Properties
Published online 04 February 2008
EPL, 81 (2008) 57005
DOI: 10.1209/0295-5075/81/57005

Potts glass on random graphs

F. Krzakala1 and L. Zdeborová2, 3

1  PCT, UMR 7083 CNRS-ESPCI - 10 rue Vauquelin, 75231 Paris, France
2  Université Paris-Sud, LPTMS, UMR8626 - Bât. 100, Université Paris-Sud, 91405 Orsay cedex, France
3  CNRS, LPTMS, UMR8626 - Bât. 100, Université Paris-Sud, 91405 Orsay cedex, France

received 20 October 2007; accepted in final form 4 January 2008; published March 2008
published online 4 February 2008

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$\geq$ 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.

75.10.Nr - Spin-glass and other random models.
89.20.Ff - Computer science and technology.

© EPLA 2008