In pure statistical mechanics models (e.g. ferromagnets), the ordering phase transition encountered by lowering the temperature reflects itself both in the spatial correlations (the correlation length diverges at the critical point) and in the temporal ones (there is a critical slowing down). These two divergences are linked by the dynamic exponent z, this connection being well understood in the field theory approach to phase transitions. The situation is less clear for structural glasses. These are materials that become increasingly slow (i.e. very viscous) when they are cooled, yet they remain spatially disordered at a microscopic level. The natural intuition that a growth of the correlation time must be related to a raise of some sort of correlation length has thus been difficult to substantiate quantitatively, mainly by lack of a meaningful definition of a spatial correlation function. In a result obtained with Andrea Montanari, we could show that the thought experiment proposed previously in this context by Biroli and Bouchaud does indeed lead to a satisfying definition of the correlation length, that can be rigorously connected to the correlation time of the system.

Andrea Montanari, Guilhem Semerjian

cond-mat/0603018 , J. Stat. Phys. 125, 23 (2006)

Counting the number of distinct copies of a given pattern in a graph can be a difficult problem when the sizes of both the pattern and the graph get large : there are typically an exponentially large number of such patterns. Statistical mechanics techniques can be employed to solve (approximately) this kind of problems, by devising a well-chosen model that has the generating function of the patterns to be enumerated as its partition function. When one looks for the the typical properties of these numbers in an ensemble of random graphs, one faces naturally a mean field disordered spin model, for which analytical and algorithm methods have been extensively developed in the recent years. This strategy has been applied to the problem of counting the long cycles (a.k.a. circuits) in random graphs, yielding new conjectures on the typical number of such patterns in large random graphs, and heuristic algorithms for counting and constructing them.

Enzo Marinari, Guilhem Semerjian

cond-mat/0603657 , J. Stat. Mech. P06019 (2006)

A graph is said to be q-colorable if one can find an assignment of one out of q colors to each of its vertices, such that no edge links two vertices of the same color. In a probabilistic setting one can investigate the q-colorability of random graphs, that is the probability that a graph drawn from a given distribution (for instance according to the Erdos-Renyi ensemble) is q-colorable. A sharp threshold phenomenon occurs as the mean degree c of the random graph is increased: graphs with mean degree smaller than a threshold c_q are asymptotically almost surely colorable, whereas for c > c_q they are asymptotically almost surely non-colorable. This threshold phenomenon is reminiscent of a phase transition in traditional statistical mechanics. In fact the coloring problem can be viewed as an antiferromagnetic Potts model at zero temperature. This correspondance triggered an important research effort in the community of the statistical mechanics of disordered systems, relying on analytical techniques originally developed to study mean-field spin-glasses. An important outcome of this line of research has been the suggestion of the presence of other phase transitions in the c < c_q regime, related to some structural changes in the space of solutions of the coloring (or other more general random constraint satisfaction problems). Some of my recent works have been devoted to the clarification of these structural changes, in particular in the underquoted references we showed how the previous picture of the colorable regime had to be refined to take into account the fluctuations in the size of the groups of solutions that occur in this regime, and the fact that structure in the solution space can occur without a vertex being frozen to a given color in a group of solutions.

Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, Lenka Zdeborova

cond-mat/0612365 , Proc. Natl. Acad. Sci. 104, 10318 (2007)

Guilhem Semerjian

arXiv/0705.2147 , J. Stat. Phys. 130, 251 (2008)