Statistical physics of disordered systems
We use analytical, phenomenological and numerical approaches
to understand the low temperature properties of frustrated
disordered systems such as spin glasses or systems inspired from
different combinatorial optimization problems. To have an overview of our
work on spin glasses, see some
slides from a talk
given for "Aspects of Complexity and its Applications"
in Rome.
Keywords:
Statistical physics, disordered and frustrated systems,
mean field, spin glasses, energy landscapes, combinatorial optimization,
stochastic optimization, geometric probability, complex networks.
Systems investigated:
Spin glasses (maxcut), glasses, minimum matching, traveling salesman
problem, multiagent systems.
Publications in reverse chronological order:
 O.C. Martin and P. Sulc,
Return probabilities and hitting times of random walks
on sparse ErdosRenyi graphs,
Phys. Rev. E 81, 031111 (2010).
We consider random walks on random graphs, focusing on return probabilities
and hitting times for sparse ErdosRenyi graphs. Using the tree approach,
which is expected to be exact in the large graph limit, we show how to solve
for the distribution of these quantities and we find that these
distributions exhibit a form of selfsimilarity.
 Z. Burda, A. Krzywicki and O.C. Martin,
Adaptive network of trading agents, Phys. Rev. E 78, 046106 (2008).
We study adaptive networks where the
agents trade ``wealth'' when they are linked together while links
can appear and disappear according to the wealth of the corresponding
agents; thus the agents influence the network dynamics and viceversa.
Our framework generalizes a multiagent model of Bouchaud and Mezard,
and leads to a steady state with fluctuating connectivities. The system
spontaneously selforganizes into a critical state where the wealth
distribution has a fat tail and the network is scalefree; in
addition, network heterogeneities lead to enhanced wealth condensation.
 Z. Burda, A. Krzywicki and O.C. Martin,
Network of inherent structures in spin glasses: scaling and scalefree
distributions, Phys. Rev. E 76, 051107 (2007).
The local minima (inherent structures) of a system and their associated
transition links give rise to a network. Here we consider the topological
and distance properties of such a network in the context of spin
glasses. We find that differences between linked inherent structures
are typically associated with local clusters of spins; we interpret
this within a framework based on droplets in which the
characteristic ``length scale'' grows with the barrier height. We
also consider the network connectivity and the degrees of its nodes,
finding a nontrivial scalefree behavior when the spin glass is of the
meanfield type.

F. Liers and O.C. Martin,
Magnetic exponents of twodimensional Ising spin glasses,
Phys. Rev. B 76, 060405 (2007).
The magnetic critical properties of twodimensional spin glasses are
controversial. Using exact ground state determination, we extract the
properties of clusters flipped when increasing continuously a uniform
field. We show that these clusters have many holes but otherwise have
statistical properties similar to those of zerofield droplets. A detailed
analysis gives for the magnetization exponent delta = 1.30 +/ 0.02 using
lattice sizes up to 80x80; this is compatible with the droplet model
prediction delta=1.282. The reason for previous disagreements stems from
the need to analyze both singular and analytic contributions in the low
field regime.

S.N. Majumdar and O. C. Martin,
The Statistics of the Number of Minima in a Random Energy
Landscape, Phys. Rev. E 74, 061112 (2006).
We consider random energy landscapes constructed from ddimensional
lattices or trees. In dimension 1, we calculate the large deviation
function for the distribution of the number of local minima. We then
determine for the Cayley tree, the twoleg ladder and hypercubic
lattices, the probability of the maximum possible number of minima.

J. Lukic, E. Marinari, O. C. Martin and S. Sabatini,
Temperature Chaos in TwoDimensional Ising Spin Glasses with
Binary Couplings: a Further Case for Universality,
J. Stat. Mech. (2006) L10001.
In general spin glasses, the chaos exponent is given by
zeta = d_s/2  theta. The binary model however differs in its
values of d_s and theta; nevertheless, we find numerically that
zeta is the same in all models, confirming our previous claims
of a single finite temperature universality class.

T. Jorg, J. Lukic, E. Marinari and O. C. Martin,
Strong universality and algebraic scaling in twodimensional
Ising spin glasses, Phys. Rev. Lett. 96, 237205 (2006).
At zero temperature, twodimensional Ising spin glasses are known
to fall into several universality classes. Here we consider the
scaling at low but nonzero temperature and provide evidence, both
numerical and theoretical, that for thermal properties (T>0) there
is a single universality class.
 Z. Burda, A. Krzywicki, O.C. Martin and Z. Tabor,
From simple to complex networks: inherent structures, barriers
and valleys in the context of spin glasses. Phys. Rev. E 73,
036110 (2006).
We use the lid algorithm to study the energy landscape of spin
glasses on a variety of random graphs. We determine the multiplicity
of the inherent structures and find simple scaling laws for the
growth of the height of the
energy barrier between the two degenerate ground states and the
size of the associated valleys.
 J. Lukic, E. Marinari and O. C. Martin,
Plaquette disorder in Villain's fully frustrated model:
a very relevant perturbation. Europhys. Lett. 73 (2006) 779.
We first study Villain's fully frustrated model, unveiling
an unexpected finite size scaling law. Then we show that the
introduction of even a small amount of disorder on the plaquettes
dramatically changes the scaling laws associated with the T=0
critical point.
 O. C. Martin, M. Mezard and O. Rivoire,
Random multiindex matching problems.
J. Stat. Mech. (2005) P09006.
We present a detailed analysis via the cavity equations (RS and 1RSB)
of the low temperature properties of random multiindex matching problems.
For d>2 there is a frozen glassy phase with vanishing entropy. We also
investigate some properties of small samples by enumerating the
lowest cost matchings and compare with our theoretical predictions.
 C. De Dominicis, I. Giardina, E. Marinari, O. C. Martin and F. Zuliani,
Spatial correlation functions in 3d Ising spin glasses.
Phys. Rev B 72, 014443 (2005).
We consider spinspin correlation functions in the low temperature
phase of spinglasses. A nearinfrared massive longitudinal mode
is identified within the replica field theory formalism and
this prediction is corroborated by numerical simulations in 3 dimensions.
 O. C. Martin, M. Mezard and O. Rivoire,
A frozen glass phase in the multiindex matching problem.
Phys. Rev. Lett. 93, 217205 (2004).
We use the cavity method to solve the thermodynamics of the multiindex
matching problem with random costs. We derive the critical temperature,
the ground state energy density, and properties of the energy
landscape.

A. Andreanov, F. Barbieri and O. C. Martin,
Large deviations in spin glass ground state energies.
Eur. Phys. J. B. 41 (3), 365 (2004).
The ground state energy E_0 of a spin glass is an example of an
extreme statistic. We consider the large deviations of this energy
for various models, including hierarchical lattices and the
SherringtonKirkpatrick model.

J. Lukic, A. Galluccio, E. Marinari, O. C. Martin and G. Rinaldi,
Critical thermodynamics of the twodimensional +/J Ising spin glass.
Phys. Rev. Lett. 92, 117202 (2004).
Exact partition functions of 2d Ising spin glasses with binary
couplings are computed. We find that the low temperature specific
heat density does not scale as exp(4J/T) but more slowly, perhaps
as exp(2J/T), corresponding to an ``effective'' gap of size 2J
rather than the actual gap of size 4J. We justify these
scalings via the degeneracy of the low lying excitations and by the
way low energy domain walls proliferate in this model.

O. Rivoire, G. Biroli, O. C. Martin and M. Mezard,
Glass models on Bethe lattices.
Eur. Phys. J. B (2004).
We consider ``lattice glass models''. Using the cavity method, we
derive the phase diagram, with a particular focus on the vitreous
phase and the highest packing limit. We also study the energy
landscape via the configurational entropy. Finally, we show that a
kinetic freezing can prevent the equilibrium glass transitions.

J.P. Bouchaud, F. Krzakala and O. C. Martin,
Energy exponents and corrections to scaling in Ising spin glasses.
Phys. Rev. B 68, 224404 (2003).
We study the probability distribution P(E) of the ground state energy
E in various Ising spin glasses. In most cases, P(E) scales as
in the central limit theorem but there are notable exceptions.
We also find violations of universality.

M. Sasaki and O. C. Martin,
Temperature chaos, rejuvenation and memory in MigdalKadanoff
spin glasses. Phys. Rev. Lett. 91, 097201 (2003).
We probe the scales relevant for rejuvenation and memory
in MigdalKadanoff spin glasses. First, we find superexponential decay
of correlations in domain wall free energies. Second,
we find that rejuvenation arises at a length scale smaller
than the ``overlap length'' l(T,T') while
memory survives even if equilibration goes out
to length scales much larger than l(T,T').

C. Amoruso, E. Marinari, O. C. Martin and A. Pagnani,
Scalings of domain wall energies in two dimensional Ising
spin glasses. Phys. Rev. Lett. 91, 087201 (2003).
We find that two dimensional spin glasses fall
into three universality classes. The first is associated
with the exponent theta =0.28, the other two classes have theta = 0.
We also find that theta=0 does not indicate d=d_l but rather d <= d_l,
where d_l is the lower critical dimension.

J. Lamarcq, J.P. Bouchaud and O. C. Martin,
Local excitations of a spin glass in a magnetic field.
Phys. Rev. B 68, 012404 (2003).
We study the minimum energy clusters above the ground state for the 3d
EdwardsAnderson spin glass in a magnetic field.
For fields B above 0.4, both the mec energy and magnetization
grow with V, as expected in a paramagnetic phase.
Also, the geometry of the mec is completely insensitive to the
field, giving further credence that they are lattice animals
even in the absence of a field.

F. Krzakala and O. C. Martin,
Absence of an equilibrium ferromagnetic spin glass phase in
three dimensions. Phys. Rev. Lett. 89, 267202 (2002).
Using ground state computations, we study the transition from a
spin glass to a ferromagnet in 3d spin glasses when changing the mean
value of the spinspin interaction. We find good evidence
for replica symmetry breaking up till the
critical value where ferromagnetic ordering sets in, and
no mixed (ferromagnetic and spin glass) phase.

M. Sasaki and O. C. Martin,
Temperature chaos in a replica symmetry broken spin glass model  A
hierarchical model with temperature chaos .
Europhys. Lett. 60 (2), 316 (2002).
Temperature chaos is an extreme sensitivity of the equilibrium state
to a change of temperature. We consider a model
spin glass on a tree and show that although it has mean field behavior
with replica symmetry breaking, it manifestly has ``strong'' temperature
chaos; we also compute the overlap length.

J.H. Boutet de Monvel O. C. Martin,
Almost sure convergence of the minimum bipartite matching functional
in Euclidean space.
Combinatorica 22(4):523530 (2002).
Let L_N be the minimum length of a bipartite matching between two
sets of N points independently and uniformly distributed in [0,1]^d.
We prove that for d greater or equal to 3, L_N / N^{11/d}
converges with probability one to a constant beta(d)>0 as N
goes to infinity.

M. Sasaki and O. C. Martin,
Discreteness and entropic fluctuations in GREMlike systems.
Phys. Rev. B 66, 174411 (2002).
Within generalized random energy models, we study the effects of
energy discreteness and of entropy extensivity in the low
temperature phase.
At zero temperature, discreteness of the energy induces replica
symmetry breaking; however, when the ground state energy has
an extensive entropy, the distribution of overlaps P(q) instead tends
towards a single delta function in the large volume limit.

F. Krzakala and O. C. Martin,
Chaotic temperature dependence in a model of spin glasses.
Eur. Phys. J. B. 28 (2), 199 (2002).
We address the problem of chaotic temperature dependence in
disordered glassy systems at equilibrium by following states of
a randomentropy randomenergy model in temperature, focusing on
the statistics of level crossings. Our model
exhibits strong, weak or no temperature chaos depending on
the value of an exponent, and thus predicts
the presence of temperature chaos in the SherringtonKirkpatrick
and EdwardsAnderson spin glass models, albeit when the number
of spins is at least of order 1000.

J. Lamarcq, J.P. Bouchaud, O. C. Martin and M. Mezard,
Noncompact local excitations in spin glasses.
Europhys. Lett. 58 (3), 321 (2002).
We consider the lowestlying local excitations of the 3D
EdwardsAnderson model: given the ground state and a number of
spins to be flipped, we determine the connected cluster of
minimum energy having that size and containing a particular spin.
The fractal dimension of these clusters turns out to be
close to two, suggesting an analogy with lattice animals. Furthermore,
their energy does not grow with their size.

F. Krzakala, J. Houdayer, E. Marinari, O.C. Martin and G. Parisi,
Zerotemperature responses of a 3D spin glass in a field.
Phys. Rev. Lett. 87, 197204 (2001).
We probe the energy landscape of the 3D EdwardsAnderson spin glass
in a magnetic field to test for a spin glass ordering.
Our data suggest that a transition from
the spin glass to the paramagnetic phase takes place at B_c=0.65,
though the possibility B_c=0 cannot be excluded. We also discuss
the question of the nature of the putative frozen phase.

E. Marinari, O.C. Martin and F. Zuliani,
Equilibrium valleys in spin glasses at low temperature .
Phys. Rev. B. 64, 184413 (2001).
We investigate the 3dimensional EdwardsAnderson spin glass model
at low temperature on simple cubic lattices of sizes up to L=12.
We cluster the equilibrium configurations into "valleys". On average,
these valleys have freeenergy differences of O(1), but a difference
in the (extensive) internal energy that grows significantly with L.
We also find that valleys typically differ by spongelike
clusters, just as found previously for lowenergy systemsize excitations
above the ground state.

O.C. Martin, R. Monasson and R. Zecchina,
Statistical mechanics methods and phase transitions in
optimization problems .
Theoretical Computer Science 265 (12) (2001) 367.
This review presents tools and
concepts designed by physicists to deal with optimization or
decision problems in an accessible language for computer scientists
and mathematicians, with no prerequisites in physics. We cover
the use of such methods for random graphs,
Satisfiability, and the Traveling Salesman problems.

F. Krzakala and O.C. Martin,
Discrete energy landscapes and replica symmetry breaking at
zero temperature .
Europhys. Lett. 53 (6) (2001) 749755.
The order parameter P(q) for disordered and frustrated systems with
degenerate ground states is reconsidered. We propose that entropy
fluctuations lead to a trivial P(q) at zero temperature (as in the
nondegenerate case) even if there are zero energy large scale
excitations (complex energy landscape).

J. Houdayer, F. Krzakala and O.C. Martin,
Largescale lowenergy excitations in 3d spin glasses.
Eur. Phys. J. B 18 (2000) 467477.
We extract largescale excitations above the ground state
in the 3dimensional EdwardsAnderson spin glass.
Their energies are O(1) and they generally are
spongelike. However, they coarsen when the system size is increased,
so either finite size effects are very large or the mean field
picture of homogeneous excitations has to be modified.

F. Krzakala and O.C. Martin,
Spin and link overlaps in 3dimensional spin glasses.
Phys. Rev. Lett. 85 (2000) 3013.
Copyright 2000,
American Physical Society.
Excitations of threedimensional spin glasses are computed numerically.
We find that one can flip a finite fraction of an L.L.L lattice with
an O(1) energy cost, confirming the mean field picture of a nontrivial
spin overlap distribution P(q). These low energy excitations are
topologically nontrivial and
reach out to the boundaries of the lattice.

J. Houdayer and O.C. Martin,
A geometrical picture for finite dimensional spin glasses.
Europhys. Lett. 49 (2000) 794800.
Copyright 2000,
EDP Sciences .
A controversial issue in spin glasses is whether mean field
theory correctly describes 3dimensional spin glasses. If it
does, how can replica symmetry breaking arise in terms of spin
clusters in Euclidean space? Here we argue that it arises via
systemsize lowenergy excitations that are spongelike.

J. Houdayer and O.C. Martin,
Reply to Comment on "Ising Spin Glasses in a Magnetic Field".
Phys. Rev. Lett. 84 (2000) 1057.
Copyright 2000,
American Physical Society.
In their comment to our paper, Marinari, Parisi and
Zuliani use outofequilibrium measurements to test for an
AlmeidaThouless line.
In our view such a dynamic approach can easily be misleading
and cannot be as compelling as equilibrium approaches.

J. Houdayer and O.C. Martin,
Ising Spin Glasses in a Magnetic Field.
Phys. Rev. Lett. 82 (1999) 49344937.
Copyright 1999,
American Physical Society.
Ground states of the three dimensional EdwardsAnderson spin glass
are computed in the presence of an external magnetic field.
Their analysis as a function of the field suggests
that the spin glass phase
does not survive in the presence of any finite field, i.e.,
no AlmeidaThouless line is visible.

A.G. Percus and O.C. Martin,
The stochastic traveling salesman problem: Finite size scaling and
the cavity prediction.
Journal of Statistical Physics 94:5/6 (1999) 739758.
The validity of the cavity prediction is tested in two dimensions
and in the limit of large dimensions. We find that the frequency
of visiting one's kth nearest neighbor in the optimal
tour decreases exponentially at large k. We also consider the behavior
of this system when the link lengths are chosen from
an exponential distribution.

J. Houdayer and O.C. Martin,
Droplet Phenomenology and Mean Field in a
Frustrated Disordered System.
Phys. Rev. Lett. 81(12) (1998) 25542557.
Copyright 1998,
American Physical Society.
We develop an algorithm to enumerate the lowlying excitations
of the minimum matching problem. The excitations' energies
grow with their size; however, some low energy  infinite size 
excitations create multiple valleys in the energy landscape,
consistent with mean field predictions.

J. Houdayer, J. H. Boutet de Monvel and O.C. Martin,
Comparing Mean Field and Euclidean Matching Problems.
Eur. Phys. J. B 6 (1998) 383393.
Gives numerous scaling properties of the ground state
matching cost which we find to have a Gaussian
probability distribution. We also present a conjecture
for the neighborhood preferences in the optimal matching; since,
this has been derived by Parisi and Ratieville and proven by
Aldous.

A.G. Percus and O.C. Martin,
Scaling universalities of kthnearest neighbor distances
on closed manifolds.
Advances in Applied Mathematics 21 (1998) 424436.
(Copyright © 1998 by Academic Press.)
Consider N sites randomly and uniformly distributed on
a smooth manifold without boundaries, and look at the expected
distance from a point on the manifold to its kthnearest site. When
the manifold has no curvature, we find that the 1/N scaling
law for this quantity is universal in k. When the
manifold has intrinsic curvature, we show that the leading
1/N term depends only on the Euler
characteristic and is thus a topological invariant.

J. Boutet de Monvel and O.C. Martin,
Mean Field and Corrections for the Euclidean Minimum Matching
Problem.
Phys. Rev. Lett. 79:1 (1997) 167170.
Copyright 1997,
American Physical Society.
A study of the random link approximation is given on
the minimum (complete) matching of random points in Euclidean space.
We show that the approximation leads to a few percent error on
the ground state energy in d=2 and 3, and that this error
decreases as O(1/dČ).
In addition, we consider an expansion in link correlations
which decreases this error by a factor 10 at low
dimension. It also shows that the O(1/dČ) corrections
are beyond all orders of perturbation theory.

N.J. Cerf, J. Boutet de Monvel, O. Bohigas, O.C. Martin and A.G. Percus,
The random
link approximation for the Euclidean
traveling salesman problem.
Journal de Physique I 7:1 (1997) 117136.
Copyright 1997,
Les Editions de Physique.
This paper gives extensive results on the stochastic TSP. We give
precise asymptotic (large N) values for the Euclidean
optimum tour length. We then make use
of the random link approximation to derive analytical predictions
of the tour length, showing that at high dimension d the
approximation is valid up to O(1/dČ).

A.G. Percus and O.C. Martin,
Finite size and dimensional dependence in the Euclidean traveling
salesman problem.
Phys. Rev. Lett. 76:8 (1996) 11881191.
Copyright 1996,
American Physical Society.
Using finite size scaling, we extract the asymptotic expression
for the length of the shortest closed tour going through N
points randomly distributed in Euclidean space. We then consider
a random link approach. This gives a good approximation of the
large N tour length at low dimension, as well as its dimensional
scaling law at high dimension.
LPTMS Home Page
IPN Home Page
Olivier MARTIN Home Page
Last modified: December 2007
in anti spam format: olivier adothere martin (at sign)
upsud adotthere fr
http://ipnweb.in2p3.fr/lptms/membres/martino