Glauber dynamics on trees and hyperbolic graphs

DOI10.1007/S00440-004-0369-4MaRDI QIDQ1780979zbMATH OpenOpenAlexFDO

Authors Noam Berger, Elchanan Mossel, Yuval Peres, Claire Kenyon

Publication date 15 June 2005

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

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

zbMATH Keywords

graphrandom configurations

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with $n$ vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap $|lambd{a}_1-lambd{a}_2|$) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in $n$. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that if the relaxation time $a{u}_2$ satisfies $a{u}_2=O(1)$, then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.

Recommendations

• Phase transition for Glauber dynamics for independent sets on regular trees
• Glauber dynamics on trees: Boundary conditions and mixing time
• Phase transition for Glauber dynamics for independent sets on regular trees
• The Glauber dynamics for colorings of bounded degree trees
• The Glauber Dynamics for Colourings of Bounded Degree Trees

Cites work

• scientific article; zbMATH DE number 1188961 (Why is no real title available?)
• scientific article; zbMATH DE number 54069 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 193576 (Why is no real title available?)
• scientific article; zbMATH DE number 3459477 (Why is no real title available?)
• scientific article; zbMATH DE number 1069282 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1559584 (Why is no real title available?)
• scientific article; zbMATH DE number 1380585 (Why is no real title available?)
• scientific article; zbMATH DE number 1418384 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Analyzing Glauber dynamics by comparison of Markov chains
• Approximating the Permanent
• Broadcasting on trees and the Ising model.
• Correlation inequalities on some partially ordered sets
• Glauber dynamics on the cycle is monotone
• Glauber dynamics on trees: Boundary conditions and mixing time
• Graph minors. I. Excluding a forest
• Information flow on trees
• On Markov Chains for Independent Sets
• On the extremality of the disordered state for the Ising model on the Bethe lattice
• On the purity of the limiting Gibbs state for the Ising model on the Bethe lattice.
• Polynomial-Time Approximation Algorithms for the Ising Model
• Reconstruction on trees: Beating the second eigenvalue
• The vertex separation number of a graph equals its path-width

Cited in

(68)

• Glauber dynamics for Ising model on convergent dense graph sequences
• Robust reconstruction on trees is determined by the second eigenvalue.
• Mixing time of critical Ising model on trees is polynomial in the height
• Global alignment of molecular sequences via ancestral state reconstruction
• A remark on monotonicity for the Glauber dynamics on finite graphs
• The mixing time of Glauber dynamics for coloring regular trees
• The Swendsen-Wang Dynamics on Trees
• The Swendsen–Wang dynamics on trees
• The Ising partition function: zeros and deterministic approximation
• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• Glauber dynamics on the cycle is monotone
• Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree
• Sub-critical exponential random graphs: concentration of measure and some applications
• Glauber dynamics on trees: Boundary conditions and mixing time
• Dynamics of Ising models near zero temperature: real-space renormalization approach
• Convergence to equilibrium of logit dynamics for strategic games
• Can extra updates delay mixing?
• The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations
• On the hardness of sampling independent sets beyond the tree threshold
• Exact thresholds for Ising-Gibbs samplers on general graphs
• A law of large numbers for weighted majority
• A manifold of pure Gibbs states of the Ising model on the Lobachevsky plane
• The critical Ising model on trees, concave recursions and nonlinear capacity
• The majority vote process and other consensus processes on trees
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects
• Mixing time for the solid-on-solid model
• Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
• Metastability of logit dynamics for coordination games
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Dynamical barriers for the random ferromagnetic Ising model on the Cayley tree: traveling-wave solution of the real space renormalization flow
• A new correlation inequality for Ising models with external fields
• Comparison of Swendsen-Wang and heat-Bath dynamics
• Critical Ising on the square lattice mixes in polynomial time
• Glauber dynamics for the quantum Ising model in a transverse field on a regular tree
• Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
• Glauber dynamics on nonamenable graphs: boundary conditions and mixing time
• Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture
• Decentralized dynamics for finite opinion games
• Phase transition of the reconstructability of a general model with different in-community and out-community mutations on an infinite tree
• Non-reversible stationary states for majority voter and Ising dynamics on trees
• Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
• Tight bounds for mixing of the Swendsen-Wang algorithm at the Potts transition point
• Logit dynamics with concurrent updates for local interaction potential games
• Glauber dynamics on the cycles: spectral distribution of the generator
• Sampling in uniqueness from the Potts and random-cluster models on random regular graphs
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)
• Information flow on trees
• Slow emergence of cooperation for win-stay lose-shift on trees
• Majority dynamics on trees and the dynamic cavity method
• Glauber dynamics for the mean-field Potts model
• Gibbs measures and phase transitions on sparse random graphs
• Rates of convergence for Gibbs sampling in the analysis of almost exchangeable data
• Sampling biased monotonic surfaces using exponential metrics
• Reconstructibility of a general DNA evolution model
• Rigorous inequalities between length and time scales in glassy systems
• On systematic scan for sampling \(H\)-colorings of the path
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Metastability of logit dynamics for coordination games
• Reconstruction for the Potts model
• A branch-and-bound algorithm for the minimum cut linear arrangement problem
• Learning loosely connected Markov random fields
• The Glauber dynamics for edge-colorings of trees
• Randomly coloring graphs of logarithmically bounded pathwidth
• Glued trees algorithm under phase damping
• Phase transition for Glauber dynamics for independent sets on regular trees
• A thermodynamic formalism for continuous time Markov chains with values on the Bernoulli space: entropy, pressure and large deviations

This page was built for publication: Glauber dynamics on trees and hyperbolic graphs

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