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:

Systems investigated:

Publications in reverse chronological order:

• O.C. Martin and P. Sulc, Return probabilities and hitting times of random walks on sparse Erdos-Renyi graphs, Phys. Rev. E 81, 031111 (2010). We consider random walks on random graphs, focusing on return probabilities and hitting times for sparse Erdos-Renyi 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 self-similarity.

• 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 vice-versa. Our framework generalizes a multi-agent model of Bouchaud and Mezard, and leads to a steady state with fluctuating connectivities. The system spontaneously self-organizes into a critical state where the wealth distribution has a fat tail and the network is scale-free; 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 scale-free 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 non-trivial scale-free behavior when the spin glass is of the mean-field type.

• F. Liers and O.C. Martin, Magnetic exponents of two-dimensional Ising spin glasses, Phys. Rev. B 76, 060405 (2007). The magnetic critical properties of two-dimensional 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 zero-field 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 d-dimensional 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 two-leg 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 Two-Dimensional 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 two-dimensional Ising spin glasses, Phys. Rev. Lett. 96, 237205 (2006). At zero temperature, two-dimensional Ising spin glasses are known to fall into several universality classes. Here we consider the scaling at low but non-zero 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 multi-index 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 multi-index 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 3-d Ising spin glasses. Phys. Rev B 72, 014443 (2005). We consider spin-spin correlation functions in the low temperature phase of spin-glasses. A near-infrared 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 multi-index matching problem. Phys. Rev. Lett. 93, 217205 (2004). We use the cavity method to solve the thermodynamics of the multi-index 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 Sherrington-Kirkpatrick model.

• J. Lukic, A. Galluccio, E. Marinari, O. C. Martin and G. Rinaldi, Critical thermodynamics of the two-dimensional +/-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 Migdal-Kadanoff spin glasses. Phys. Rev. Lett. 91, 097201 (2003). We probe the scales relevant for rejuvenation and memory in Migdal-Kadanoff spin glasses. First, we find super-exponential 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 3-d Edwards-Anderson 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 3-d spin glasses when changing the mean value of the spin-spin 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):523-530 (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^{1-1/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 GREM-like 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 random-entropy random-energy 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 Sherrington-Kirkpatrick and Edwards-Anderson 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, Non-compact local excitations in spin glasses. Europhys. Lett. 58 (3), 321 (2002). We consider the lowest-lying local excitations of the 3D Edwards-Anderson 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, Zero-temperature responses of a 3D spin glass in a field. Phys. Rev. Lett. 87, 197204 (2001). We probe the energy landscape of the 3D Edwards-Anderson 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 3-dimensional Edwards-Anderson 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 free-energy 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 sponge-like clusters, just as found previously for low-energy system-size 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 (1-2) (2001) 3-67. 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) 749-755. 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 non-degenerate case) even if there are zero energy large scale excitations (complex energy landscape).

• J. Houdayer, F. Krzakala and O.C. Martin, Large-scale low-energy excitations in 3-d spin glasses. Eur. Phys. J. B 18 (2000) 467-477. We extract large-scale excitations above the ground state in the 3-dimensional Edwards-Anderson spin glass. Their energies are O(1) and they generally are sponge-like. 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 3-dimensional spin glasses. Phys. Rev. Lett. 85 (2000) 3013. Copyright 2000, American Physical Society. Excitations of three-dimensional 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 non-trivial spin overlap distribution P(q). These low energy excitations are topologically non-trivial 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) 794-800. Copyright 2000, EDP Sciences . A controversial issue in spin glasses is whether mean field theory correctly describes 3-dimensional 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 system-size low-energy excitations that are sponge-like.

• 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 out-of-equilibrium measurements to test for an Almeida-Thouless 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) 4934-4937. Copyright 1999, American Physical Society. Ground states of the three dimensional Edwards-Anderson 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 Almeida-Thouless 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) 739-758. 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) 2554-2557. Copyright 1998, American Physical Society. We develop an algorithm to enumerate the low-lying 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) 383-393. 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 kth-nearest neighbor distances on closed manifolds. Advances in Applied Mathematics 21 (1998) 424-436. (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 kth-nearest 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) 167-170. 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) 117-136. 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) 1188-1191. 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