Abstract. A method is introduced for studying large deviations in the context of statistical physics of disordered systems. The approach, based on an extension of the cavity method to atypical realizations of the quenched disorder, allows us to compute exponentially small probabilities (rate functions) over different classes of random graphs. It is illustrated with two combinatorial optimization problems, the vertex-cover and colouring problems, for which the presence of replica symmetry breaking phases is taken into account. Applications include the analysis of models on adaptive graph structures.

Key words: cavity and replica method; disordered systems (theory); random graphs, networks; typical-case computational complexity

E-print number: cond-mat/0506164
Cited: by
Refers: to

Received 7 June 2005, accepted for publication 29 June 2005
Published 14 July 2005