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

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)