zbMATH — the first resource for mathematics

Gibbs measures and phase transitions on sparse random graphs. (English) Zbl 1205.05209
Many problems in probability, theoretical computer science and theoretical physics study a set of random variables associated with the vertices of a large (but finite) sparse graph, a natural way to generate “locally dependent” collections of random variables. However there is a large gap between what physicists have satisfied themselves of via heuristic arguments and what has been rigorously proven. This article is a contribution to the rigorous theory in this direction for sparse random graphs. While these are not contained in lattices, implying that the direct link with physics is lost, one might hope, via some “universality” ideas, that at least some of the structure emerging might subsist in lattice models too.
We take a graph \(G=(V,E)\) with each vertex \(i\in V\) having an attached variable \(x_{i}\) taking values in a finite set \( {\mathcal X}\). To each edge \(ij\) of \(G\) associate a map \(\psi_{ij}: {\mathcal X}\times {\mathcal X}\rightarrow [0,\psi_{max}]\) for a constant \(\psi_{max}\): note \(\psi_{ij}=\psi_{ji}\). We may also have a function \(\psi_{i}\) from each vertex to \({\mathcal X}\). We then form the canonical probability measure \(\mu_{G,\psi}\) associated to \(G\) and this collection \(\underline{\psi}\) of maps \(\psi_{ij}\) and \(\psi_{i}\): \[ \mu_{G,\psi}=\frac{1}{Z(G,\underline{\psi})}\prod_{ij\in E(G)}\psi_{ij}(x_{i},x_{j})\prod_{i\in V}\psi_{i}(x_{i}) \] where \(Z(G,\underline{\psi})\) is a normalising constant. A special case much studied is the Curie-Weiss model where \(x_{i}=\pm 1\), \(G=K_{n}\) and \(\psi_{ij}(x_{i},x_{j})=\exp(\beta x_{i}x_{j}/n)\), or the generalised Curie-Weiss model with additionally a “magnetic field” given by \(\psi_{i}(x_{i})=\exp(B x_{i})\). Other examples include the Ising model (basically, the generalised Curie-Weiss model on a more general \(n\)-vertex graph \(G\) than \(K_{n}\): here one tends to use \(Z_{n}(\beta,B)\) rather than \(Z(G,\psi)\), \(G\) being quietly understood), ‘spin glasses’, various random constraint satisfaction problems, proper colourings of graphs and various problems in communications.
The rest of this review concentrates on broad ideas rather than detail. We say a model \((G,\underline{\psi})\) displays “coexistence” if \(\mu_{G,\underline{\psi}}\) decomposes into a convex combination of well-separated lumps, with bottlenecks between them. When this is suitably formalised, it turns out that the generalised Curie-Weiss model exhibits such coexistence if and only if \(\beta>1\) and \(B=0\).
Chapter 2 of the article deals with the Ising model on sparse graphs that ‘converge locally to conditionally independent trees’: one makes this precise and shows that a sequence of sparse graphs \(G(n,p)\) with \(p=c/n\) do converge to one such tree, the Galton-Watson tree. In these circumstances one can prove results about the decay of correlations with increasing graph distance in the graphs. A (rigorous form of) Bethe-Peierls approximation for certain particular graph sequences now gives the limiting behaviour of the asymptotic free energy density \(\lim_{n\rightarrow\infty}\frac{1}{n}\log (Z_{n}(\beta,B)\), leading to (e.g.) the conclusion that the ferromagnetic Ising measures on random \(k\)-regular multigraphs from the configuration model exhibit coexistence if and only if \((k-1)\tanh(\beta)>1\).
Chapter 3 studies Bethe-Peierls approximation, which turns the computation of partition functions into solving (messy) non-linear equations: for mean field models (roughly, those without finite-dimensional geometric structure) physicists think this should be asymptotically exact. The main result is that the Bethe approximation does hold when the graph is tree-like and there is a suitable decay hypothesis on correlations, which generalises the ‘extremality condition’, in trees.
Chapter 4 is on proper \(q\)-colourings (\(q\) fixed). Now the canonical measure is \(\prod_{ij\in E(G)}I(x_{i}\neq x_{j})\) divided by the number \(Z_{G}\) of proper \(q\)-colourings. As the number of edges (assumed linear in the number of vertices) increases, there should be a threshold for the transition from \(q\)-colourable to not \(q\)-colourable but this is not proven yet. For random \((k+1)\)-regular graphs, \(\mu_{G}\) should exhibit co-existence (say the physicists) if and only if a certain fixed point equation admits a non-trivial solution when a certain parameter \(\epsilon\) is zero. This equation is also linked with solubility of a reconstruction problem for trees (the reconstruction threshold is, roughly, the point where the colour of the root of the tree moves from being uncorrelated with that of a distant point to being correlated), and (heuristically) with the growth rate of the number of ‘clusters’, into which \(\mu_{G}\) decomposes.
This leads into a discussion in Chapter 5 of reconstruction and extremality. The main result is that reconstruction on the real graph and on the tree approximating it are equivalent under a ‘sphericity’, condition. The reconstruction problem is linked to MCMC and random constraint satisfaction problems.

05C80 Random graphs (graph-theoretic aspects)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
82B26 Phase transitions (general) in equilibrium statistical mechanics
82B44 Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics
60K35 Interacting random processes; statistical mechanics type models; percolation theory
Full Text: DOI arXiv
[1] Achlioptas, D. and Coja-Oghlan, A. (2008). Algorithmic barriers from phase transitions. In, 49th Annual Symposium on Foundations of Computer Science . Philadelphia, PA.
[2] Achlioptas, D. and Friedgut, E. (1999). A sharp threshold for, k -colorability. Random Structures & Algorithms 14 63-70. · Zbl 0962.05055
[3] Achlioptas, D. and Friedgut, E. (1999). Sharp thresholds of graph properties and the, k -SAT Problem, with an appendix by J. Bourgain. Journal of the American Mathematical Society 12 1017-1054. JSTOR: · Zbl 0932.05084 · doi:10.1090/S0894-0347-99-00305-7 · links.jstor.org
[4] Achlioptas D. and Naor, A. (2004). The two possible values of the chromatic number of a random graph. In, Proceedings of the 36th Annual ACM Symposium on Theory of Computing 587-593. ACM, New York. · Zbl 1094.05048 · doi:10.4007/annals.2005.162.1335
[5] Achlioptas, D., Naor, A. and Peres, Y. (2005). Rigorous location of phase transitions in hard optimization problems., Nature 435 759.
[6] Achlioptas, D. and Ricci-Tersenghi, F. (2006). On the solution-space geometry of random constraint satisfaction problems. In, Proc. 38th ACM Symposium on Theory Of Computing, Seattle (USA) 130-139. ACM, New York. · Zbl 1301.68190
[7] Aizenman, M. and Warzel, S. (2007). The canopy graph and level statistics for random operators on tree., Mathematical Physics, Analysis and Geometry 9 291-333. · Zbl 1138.47032 · doi:10.1007/s11040-007-9018-3
[8] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In, Probability on Discrete Structures (H. Kesten, ed.) 1-27. Springer, Berlin. · Zbl 1037.60008
[9] Alon, N. and Spencer, J. (2000)., The Probabilistic Method . Wiley, New York. · Zbl 0996.05001
[10] Berger, N., Kenyon, C., Mossel, E. and Peres, Y. (2005). Glauber dynamics on trees and hyperbolic graphs., Probability Theory and Related Fields 131 311. · Zbl 1075.60003 · doi:10.1007/s00440-004-0369-4
[11] Bhamidi, S., Rajagopal, R. and Roch, S. (2009). Network delay inference from additive metrics. In, Random Structures Algorithms 35 . · Zbl 1201.90048
[12] Bhatnagar, N., Vera, J., Vigoda, E. and Weitz, D. (2009). Reconstruction for colorings on trees. In, SIAM Journal on Discrete Mathematics . · Zbl 1298.05060
[13] Bleher, P. M., Ruiz, J. and Zagrebnov, V. A. (1995). On the purity of limiting Gibbs state for the Ising model on the Bethe lattice., Journal of Statistical Physics 79 473-482. · Zbl 1081.82515 · doi:10.1007/BF02179399
[14] Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labeled regular graphs., European Journal of Combinatorics 1 311-316. · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8
[15] Borgs, C., Chayes, J., Mossel, E. and Roch, S. (2006). The Kesten-Stigum reconstruction bound is tight for roughly symmetric binary channels. In, Proc. of IEEE FOCS.
[16] Caracciolo, S., Parisi, G., Patarnello, S. and Sourlas, N. (1990). 3d Ising spin glass in a magnetic field and mean-field theory., Europhysics Letters 11 783.
[17] Cover, T. and Thomas, J. A. (1991)., Elements of Information Theory . Wiley, New York. · Zbl 0762.94001
[18] Daskalakis, C., Mossel, E. and Roch, S. (2006). Optimal phylogenetic reconstruction. In, STOC’06: Proceedings of the 38th Annual ACM Symposium on Theory of Computing 159-168. ACM, New York. · Zbl 1301.92054
[19] Dembo, A. and Montanari, A. (2010). Ising models on locally tree-like graphs., The Annals of Applied Probability . · Zbl 1191.82025 · doi:10.1214/09-AAP627
[20] Dembo, A. and Montanari, A. (2008). Bethe states for graphical models., · Zbl 1152.05051
[21] Dembo, A. and Montanari, A. (2008). Unpublished, manuscript.
[22] Dyer, M., Sinclair, A., Vigoda, E. and Weitz, D. (2004). Mixing in time and space for lattice spin systems: A combinatorial view., Random Structures & Algorithms 24 461-479. · Zbl 1126.82021
[23] Dyson, F. J. (1969). Existence of a phase-transition in a one-dimensional Ising ferromagnet., Communications in Mathematical Physics 12 91-107. · Zbl 1306.47082 · doi:10.1007/BF01645907
[24] Ellis, R. S. and Newman, C. M. (1978). The statistics of Curie-Weiss models., Journal of Statistical Physics 19 149-161. · doi:10.1007/BF01012508
[25] Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (2000). Broadcasting on trees and the Ising model., The Annals of Applied Probability 10 410-433. · Zbl 1052.60076 · doi:10.1214/aoap/1019487349
[26] Franz, S. and Parisi, G. (1995). Recipes for metastable states in spin glasses., J. Physique I 5 1401.
[27] Georgii, H.-O. (1988)., Gibbs Measures and Phase Transition . de Gruyter, Berlin. · Zbl 0657.60122 · doi:10.1515/9783110850147
[28] Gerschenfeld, A. and Montanari, A. (2007). Reconstruction for models on random graphs. In, 48nd Annual Symposium on Foundations of Computer Science . Providence, RI.
[29] Ginibre, J. (1970). General formulation of Griffiths’ inequalities., Communications in Mathematical Physics 16 310-328. · doi:10.1007/BF01646537
[30] Griffiths, R. B., Hurst, C. A. and Sherman, S. (1970). Concavity of magnetization of an Ising ferromagnet in a positive external field., Journal of Mathematical Physics 11 790-795. · doi:10.1063/1.1665211
[31] Grimmett, G. (1999)., Percolation . Springer, New York. · Zbl 0926.60004
[32] Guerra, F. and Toninelli, F. L. (2004). The high temperature region of the Viana-Bray diluted spin glass model., Journal of Statistical Physics 115 531-555. · Zbl 1157.82377 · doi:10.1023/B:JOSS.0000019815.11115.54
[33] Guionnet, A. and Zegarlinski, B. (2002). Lectures on logarithmic Sobolev inequalities., Séminaire de Probabilites de Strasbourg 36 1-134. · Zbl 1125.60111 · doi:10.1007/b10068 · numdam:SPS_2002__36__1_0 · eudml:114087
[34] Janson, S., Luczak, T. and Ruciński, A. (2000)., Random Graphs . Wiley, New York.
[35] Krzakala, F. and Zdeborova, L. (2007). Phase transitions in the coloring of random graphs., Physical Review E 76 031131.
[36] Krzakala, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G. and Zdeborova, L. (2007). Gibbs states and the set of solutions of random constraint satisfaction problems., Proceedings of the National Academy of Sciences of the United States of America 104 10318. · Zbl 1190.68031 · doi:10.1073/pnas.0703685104
[37] Liggett, T. (1985)., Interacting Particle Systems . Springer, New York. · Zbl 0559.60078
[38] Martinelli, F., Sinclair, A. and Weitz, D. (2003). The Ising model on trees: Boundary conditions and mixing time. In, Proc. of IEEE FOCS. · Zbl 1076.82010
[39] Mézard, M. and Montanari, A. (2009)., Information, Physics and Computation . Oxford Univ. Press, Oxford. · Zbl 1163.94001
[40] Mézard, M. and Montanari, A. (2006). Reconstruction on trees and spin glass transition., Journal of Statistical Physics 124 1317-1350. · Zbl 1113.82013 · doi:10.1007/s10955-006-9162-3
[41] Mézard, M., Mora, T. and Zecchina, R. (2005). Clustering of solutions in the random satisfiability problem., Physical Review Letters 94 197-205.
[42] Mézard, M. and Parisi, G. (1999). Thermodynamics of glasses: A first principles computation., Physical Review Letters 82 747-751.
[43] Mézard, M., Parisi, G. and Virasoro, M. A. (1987)., Spin Glass Theory and Beyond . World Scientific, Teaneck, NJ. · Zbl 0992.82500
[44] Mézard, M., Parisi, G. and Zecchina, R. (2002). Analytic and algorithmic solution of random satisfiability problems., Science 297 812-815.
[45] Montanari, A., Restrepo, R. and Tetali, P. (2009). Reconstruction and clustering in random constraint satisfaction problems., SIAM Journal on Discrete Mathematics . To appear. Available at . · Zbl 1223.68077 · arxiv.org
[46] Montanari, A. and Semerjian, G. (2006). Rigorous inequalities between length and time scales in glassy systems., Journal of Statistical Physics 125 23-54. · Zbl 1112.82051 · doi:10.1007/s10955-006-9175-y
[47] Mossel, E. and Peres, Y. (2003). Information flow on trees., The Annals of Applied Probability 13 817-844. · Zbl 1050.60082 · doi:10.1214/aoap/1060202828
[48] Mossel, E., Weitz, D. and Wormald, N. (2008). On the hardness of sampling independent sets beyond the tree threshold., Probability Theory and Related Fields 142 401-439. · Zbl 1165.60028 · doi:10.1007/s00440-007-0131-9
[49] Mulet, R., Pagnani, A., Weigt, M. and Zecchina, R. (2002). Coloring random graphs., Physical Review Letters 89 268701. · Zbl 1267.05121 · doi:10.1103/PhysRevLett.89.268701
[50] Pittel, B., Spencer, J. and Wormald, N. (1996). Sudden emergence of a giant, k -core in a random graph. Journal of Combinatorial Theory Series B 67 111-151. · Zbl 0860.05065 · doi:10.1006/jctb.1996.0036
[51] Richardson, T. and Urbanke, R. (2008)., Modern Coding Theory . Cambridge Univ. Press, Cambridge. · Zbl 1188.94001 · doi:10.1017/CBO9780511791338
[52] Simon, B. (1980). Correlation inequalities and the decay of correlations in ferromagnets., Communications in Mathematical Physics 77 111-126. · doi:10.1007/BF01982711
[53] Sly, A. (2008). Reconstruction of random colourings., Communications in Mathematical Physics 288 943-961. · Zbl 1274.60163 · doi:10.1007/s00220-009-0783-7
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.