×

Ising models on locally tree-like graphs. (English) Zbl 1191.82025

Summary: We consider ferromagnetic Ising models on graphs that converge locally to trees. Examples include random regular graphs with bounded degree and uniformly random graphs with bounded average degree. We prove that the “cavity” prediction for the limiting free energy per spin is correct for any positive temperature and external field. Further, local marginals can be approximated by iterating a set of mean field (cavity) equations. Both results are achieved by proving the local convergence of the Boltzmann distribution on the original graph to the Boltzmann distribution on the appropriate infinite random tree.

MSC:

82B44 Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics
82B23 Exactly solvable models; Bethe ansatz
60F10 Large deviations
60K35 Interacting random processes; statistical mechanics type models; percolation theory
05C80 Random graphs (graph-theoretic aspects)
05C05 Trees
82D40 Statistical mechanics of magnetic materials
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508 (electronic). · Zbl 1131.60003
[2] 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.). Encyclopaedia Math. Sci. 110 1-72. Springer, Berlin. · Zbl 1037.60008
[3] Bandyopadhyay, A. and Gamarnik, D. (2007). Counting without sampling. New algorithms for enumeration problems using statistical physics. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms 890-899. ACM, New York. · Zbl 1192.82038
[4] Bollobás, B. (1980). A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European J. Combin. 1 311-316. · Zbl 0457.05038 · doi:10.1016/S0195-6698(80)80030-8
[5] Dembo, A., Gerschenfeld, A. and Montanari, A. (2010). Spin glasses on locally tree-like graphs. · Zbl 1191.82025
[6] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Applications of Mathematics ( New York ) 38 . Springer, New York. · Zbl 0896.60013
[7] De Sanctis, L. and Guerra, F. (2008). Mean field dilute ferromagnet: High temperature and zero temperature behavior. J. Stat. Phys. 132 759-785. · Zbl 1151.82434 · doi:10.1007/s10955-008-9575-2
[8] Dorogovtsev, S. N., Goltsev, A. V. and Mendes, J. F. F. (2002). Ising model on networks with an arbitrary distribution of connections. Phys. Rev. E 66 016104.
[9] Ellis, R. S. and Newman, C. M. (1978). The statistics of Curie-Weiss models. J. Statist. Phys. 19 149-161. · doi:10.1007/BF01012508
[10] Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (2000). Broadcasting on trees and the Ising model. Ann. Appl. Probab. 10 410-433. · Zbl 1052.60076 · doi:10.1214/aoap/1019487349
[11] Gerschenfeld, A. and Montanari, A. (2007). Reconstruction for models on random graphs. In Proceedings of the 48 th Annual Symposium on Foundations of Computer Science 194-204. IEEE, New York.
[12] Griffiths, R. B., Hurst, C. A. and Sherman, S. (1970). Concavity of magnetization of an Ising ferromagnet in a positive external field. J. Math. Phys. 11 790-795. · doi:10.1063/1.1665211
[13] Janson, S., Łuczak, T. and Rucinski, A. (2000). Random Graphs . Wiley, New York.
[14] Jerrum, M. and Sinclair, A. (1990). Polynomial-time approximation algorithms for the Ising model. In Automata , Languages and Programming. Lecture Notes in Computer Science 443 462-475. Springer, New York. · Zbl 0764.65091
[15] Johnston, D. A. and Plecháč, P. (1998). Equivalence of ferromagnetic spin models on trees and random graphs. J. Phys. A 31 475-482. · Zbl 0953.82038 · doi:10.1088/0305-4470/31/2/009
[16] Jonasson, J. and Steif, J. E. (1999). Amenability and phase transition in the Ising model. J. Theoret. Probab. 12 549-559. · Zbl 0940.60093 · doi:10.1023/A:1021690414168
[17] Krząkała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G. and Zdeborová, L. (2007). Gibbs states and the set of solutions of random constraint satisfaction problems. Proc. Natl. Acad. Sci. USA 104 10318-10323 (electronic). · Zbl 1190.68031 · doi:10.1073/pnas.0703685104
[18] Leone, M., Vázquez, A., Vespignani, A. and Zecchina, R. (2002). Ferromagnetic ordering in graphs with arbitrary degree distribution. Eur. Phys. J. B 28 191-197.
[19] Liggett, T. M. (1985). Interacting Particle Systems. Grundlehren der Mathematischen Wissenschaften [ Fundamental Principles of Mathematical Sciences ] 276 . Springer, New York. · Zbl 0559.60078
[20] Lyons, R. (2000). Phase transitions on nonamenable graphs. J. Math. Phys. 41 1099-1126. · Zbl 1034.82014 · doi:10.1063/1.533179
[21] Mézard, M. and Montanari, A. (2009). Information , Physics , and Computation . Oxford Univ. Press, Oxford. · Zbl 1163.94001
[22] Mooij, J. M. and Kappen, H. J. (2005). On the properties of the Bethe approximation and loopy belief propagation on binary networks. J. Stat. Mech. P11012.
[23] Salez, J. and Shah, D. (2009). Belief propagation: An asymptotically optimal algorithm for the random assignment problem. Available at · Zbl 1230.68183 · doi:10.1287/moor.1090.0380
[24] Sudderth, E., Wainwright, M. and Willsky (2008). Loop series and Bethe variational bounds in atractive graphical models. In Advances in Neural Information Processing Systems 1425-1432. MIT Press, Cambridge, MA.
[25] Simon, B. (1980). Correlation inequalities and the decay of correlations in ferromagnets. Comm. Math. Phys. 77 111-126. · doi:10.1007/BF01982711
[26] Tatikonda, S. and Jordan, M. I. (2002). Loopy belief propagation and Gibbs measures. In Proccedings of the 18 th Conference on Uncertainty in Artificial Intelligence 493-450. Morgan Kaufmann, San Francisco, CA.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.