Ising models on locally tree-like graphs

Abstract

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.

Published in at http://dx.doi.org/10.1214/09-AAP627 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Ising models on locally tree-like graphs
• Mean field dilute ferromagnet I. High temperature and zero temperature behavior
• Belief propagation : an asymptotically optimal algorithm for the random assignment problem

Cited by in corpus (74)

• Statistical physics of inference: Thresholds and algorithms
• Ising models on locally tree-like graphs
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Evolutionary potential games on lattices
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Exact thresholds for Ising-Gibbs samplers on general graphs
• The computational hardness of counting in two-spin models on d-regular graphs
• Ising models on power-law random graphs
• Factor models on locally tree-like graphs
• Examples in the entropy theory of countable group actions
• Which graphical models are difficult to learn?
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Universal transient behavior in large dynamical systems on networks
• Ising critical behavior of inhomogeneous Curie-Weiss models and annealed random graphs
• Harnessing the Bethe free energy
• Metastability of the Ising model on random regular graphs at zero temperature
• Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
• Quenched central limit theorems for the Ising model on random graphs
• Gradient Gibbs measures and fuzzy transformations on trees
• The random 2-SAT partition function
• Spin systems on Bethe lattices
• Exact Free Energies of Statistical Systems on Random Networks
• Metastability of the Potts ferromagnet on random regular graphs
• Zero-temperature dynamics in the dilute Curie-Weiss model
• High Dimensional Structure Learning of Ising Models on Sparse Random Graphs
• Antiferromagnetic Potts model on the Erdos-Renyi random graph
• The set of solutions of random XORSAT formulae
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Extremal regular graphs: the case of the infinite regular tree
• The Ising model on the random planar causal triangulation: bounds on the critical line and magnetization properties
• Gibbs Measures and Phase Transitions on Sparse Random Graphs
• Convergent sequences of sparse graphs: A large deviations approach
• Concentration of multi-overlaps for random ferromagnetic spin models
• New Understanding of the Bethe Approximation and the Replica Method
• The Mean-Field Approximation: Information Inequalities, Algorithms, and Complexity
• Random ordering formula for sofic and Rokhlin entropy of Gibbs measures
• Kawasaki dynamics beyond the uniqueness threshold
• The cavity method for counting spanning subgraphs subject to local constraints
• Large deviations for the annealed Ising model on inhomogeneous random graphs: spins and degrees
• Counting hypergraph matchings up to uniqueness threshold
• The weak limit of Ising models on locally tree-like graphs
• Approximating Partition Functions of Two-State Spin Systems
• Eigenvalue spectral tails and localization properties of asymmetric networks
• Random cluster model on regular graphs
• Spectral Bounds for the Ising Ferromagnet on an Arbitrary Given Graph
• Causal Structural Learning Via Local Graphs
• Free Energy, Gibbs Measures, and Glauber Dynamics for Nearest-neighbor Interactions on Trees
• Continuous spin models on annealed generalized random graphs
• The replica symmetric solution for Potts models on d-regular graphs
• A Generalized Bass Model for Product Growth in Networks
• On the trade-off between complexity and correlation decay in structural learning algorithms
• Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
• Statistical mechanics of clonal expansion in lymphocyte networks modelled with slow and fast variables
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• The Compulsive Gambler Process
• The Complexity of Approximating a Bethe Equilibrium
• Finite-size scaling functions of the phase transition in the ferromagnetic Ising model on random regular graphs
• Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
• Structure Learning in Inverse Ising Problems Using ${\ell }_2$-Regularized Linear Estimator
• Ising model on a Galton-Watson tree with a sparse random external field
• Non-robust phase transitions in the generalized clock model on trees
• Forest expansion of two-body partition functions for sparse interaction graphs
• Ising model on trees and factors of IID
• The giant in random graphs is almost local
• From random point processes to hierarchical Cavity Master Equations for the stochastic dynamics of disordered systems in Random Graphs: Ising models and epidemics
• Matchings on Random Regular Hypergraphs
• Fluctuations in the Ising spin model on a sparse random graph
• Entropy of fully-packed rigid rods on generalized Husimi trees: a route to the square lattice limit
• Dynamic Sampling from Graphical Models
• Asymptotics of the partition function of Ising model on inhomogeneous random graphs
• Exact statistical mechanics of the Ising model on networks
• Entropy inequalities and exponential decay of correlations for unique Gibbs measures on trees
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width