Gibbs measures and phase transitions on sparse random graphs

DOI10.1214/09-BJPS027zbMATH Open1205.05209arXiv0910.5460OpenAlexW2963994072MaRDI QIDQ985984FDOQ985984

Authors: Amir Dembo, Andrea Montanari 

Publication date: 9 August 2010

Published in: Brazilian Journal of Probability and Statistics (Search for Journal in Brave)

Abstract: Many problems of interest in computer science and information theory can be phrased in terms of a probability distribution over discrete variables associated to the vertices of a large (but finite) sparse graph. In recent years, considerable progress has been achieved by viewing these distributions as Gibbs measures and applying to their study heuristic tools from statistical physics. We review this approach and provide some results towards a rigorous treatment of these problems.

Full work available at URL: https://arxiv.org/abs/0910.5460

Recommendations

• Limits of discrete distributions and Gibbs measures on random graphs
• Charting the replica symmetric phase
• Harnessing the Bethe free energy
• Phase transitions for the cavity approach to the clique problem on random graphs

zbMATH Keywords

Ising modelphase transitionssparse graphsGibbs measureslocal weak convergencerandom graphsspin models

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Phase transitions (general) in equilibrium statistical mechanics (82B26) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Percolation
• On the hardness of sampling independent sets beyond the tree threshold
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Sudden emergence of a giant \(k\)-core in a random graph
• Existence of a phase-transition in a one-dimensional Ising ferromagnet
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Séminaire de Probabilités XXXVI
• Title not available (Why is that?)
• The two possible values of the chromatic number of a random graph
• Ising models on locally tree-like graphs
• Gibbs measures and phase transitions
• Broadcasting on trees and the Ising model.
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Coloring random graphs
• Information flow on trees
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• Information, Physics, and Computation
• Glauber dynamics on trees and hyperbolic graphs
• Sharp thresholds of graph properties, and the $k$-sat problem
• Title not available (Why is that?)
• On the solution-space geometry of random constraint satisfaction problems
• The Canophy graph and level statistics for random operators on trees
• Optimal phylogenetic reconstruction
• The high temperature region of the Viana-Bray diluted spin glass model
• Glauber dynamics on trees: Boundary conditions and mixing time
• Mixing in time and space for lattice spin systems: A combinatorial view
• Modern Coding Theory
• Finite size scaling for the core of large random hypergraphs
• Reconstruction on trees and spin glass transition
• Rigorous inequalities between length and time scales in glassy systems
• Reconstruction for Colorings on Trees
• Reconstruction and clustering in random constraint satisfaction problems
• Reconstruction of random colourings
• Network delay inference from additive metrics

Cited In (63)

• Signal detection in degree corrected ERGMs
• Spectral large deviations of sparse random matrices
• Matchings on trees and the adjacency matrix: A determinantal viewpoint
• Sparse reconstruction in spin systems. I: iid spins
• Ising model on a Galton-Watson tree with a sparse random external field
• Nonbacktracking Spectral Clustering of Nonuniform Hypergraphs
• Subcritical epidemics on random graphs
• Some rigorous results for the diluted multi-species SK model
• Interacting stochastic processes on sparse random graphs
• Detecting structured signals in Ising models
• Gibbs Random Fields with Unbounded Spins on Unbounded Degree Graphs
• Emergence of extended states at zero in the spectrum of sparse random graphs
• Maximum independent sets on random regular graphs
• On local weak limit and subgraph counts for sparse random graphs
• Spin systems on Bethe lattices
• Bethe states of random factor graphs
• Solution of the monomer-dimer model on locally tree-like graphs. Rigorous results
• Random Graphs, Phase Transitions, and the Gaussian Free Field
• Error bounds in local limit theorems using Stein's method
• A short survey on stable polynomials, orientations and matchings
• Annealed Ising model on configuration models
• Fluctuations of the magnetization in the \(p\)-spin Curie-Weiss model
• Mean quantum percolation
• The Hopfield model on a sparse Erdös-Renyi graph
• Decay of correlations for the hardcore model on the \(d\)-regular random graph
• Marginal dynamics of interacting diffusions on unimodular Galton-Watson trees
• Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
• Factor models on locally tree-like graphs
• Random sparse sampling in a Gibbs weighted tree and phase transitions
• Finite size scaling functions of the phase transition in the ferromagnetic Ising model on random regular graphs
• Limits of discrete distributions and Gibbs measures on random graphs
• Universality of the mean-field for the Potts model
• Mean-field monomer-dimer models. A review
• The condensation phase transition in random graph coloring
• Ising critical behavior of inhomogeneous Curie-Weiss models and annealed random graphs
• Survival and extinction of epidemics on random graphs with general degree
• Ising models on power-law random graphs
• On the phase transition in random simplicial complexes
• Statistical Matching Theory
• The set of solutions of random XORSAT formulae
• Load balancing in hypergraphs
• Weighted enumeration of spanning subgraphs in locally tree-like graphs
• Majority dynamics on trees and the dynamic cavity method
• Harnessing the Bethe free energy
• The set of solutions of random XORSAT formulae
• Phase growth with heat diffusion in a stochastic lattice model
• Fluctuations for the partition function of Ising models on Erdös-Rényi random graphs
• Title not available (Why is that?)
• On Dependency Graphs and the Lattice Gas
• Large deviations for the annealed Ising model on inhomogeneous random graphs: spins and degrees
• Glauber dynamics for Ising models on random regular graphs: cut-off and metastability
• The replica symmetric solution for Potts models on \(d\)-regular graphs
• Local weak convergence for sparse networks of interacting processes
• Examples in the entropy theory of countable group actions
• Fluctuations of the magnetization for Ising models on Erdős-Rényi random graphs -- the regimes of low temperature and external magnetic field
• Joint estimation of parameters in Ising model
• Fluctuations of the magnetization for Ising models on dense Erdős-Rényi random graphs
• Fluctuations of the magnetization for Ising models on Erdős–Rényi random graphs—the regimes of small p and the critical temperature ^*
• Fluctuations in mean-field Ising models
• Critical value asymptotics for the contact process on random graphs
• Zero-temperature dynamics in the dilute Curie-Weiss model
• A note on dynamical models on random graphs and Fokker-Planck equations
• Ising critical exponents on random trees and graphs

This page was built for publication: Gibbs measures and phase transitions on sparse random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q985984)