Back to main page
Selected results
On the growing lengthscales in glassy systems
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.
Rigorous Inequalities between Length and Time Scales in Glassy Systems
Andrea Montanari, Guilhem Semerjian
cond-mat/0603018 ,
J. Stat. Phys. 125, 23 (2006)
The number of long cycles in random graphs
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.
On the number of circuits in random graphs
Enzo Marinari, Guilhem Semerjian
cond-mat/0603657 ,
J. Stat. Mech. P06019 (2006)
Phase transitions in random constraint satisfaction problems
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.
Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
Florent Krzakala, Andrea Montanari, Federico Ricci-Tersenghi, Guilhem Semerjian, Lenka Zdeborova
cond-mat/0612365 , Proc. Natl. Acad. Sci. 104, 10318 (2007)
On the freezing of variables in random constraint satisfaction problems
Guilhem Semerjian
arXiv/0705.2147 ,
J. Stat. Phys. 130, 251 (2008)