Glauber dynamics on trees and hyperbolic graphs

DOI10.1007/S00440-004-0369-4zbMATH Open1075.60003arXivmath/0308284OpenAlexW2135481845MaRDI QIDQ1780979FDOQ1780979

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)

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.

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

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

zbMATH Keywords

graphrandom configurations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (67)

• Robust reconstruction on trees is determined by the second eigenvalue.
• Phase Transition of the Reconstructability of a General Model with Different In-Community and Out-Community Mutations on an Infinite Tree
• 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
• Rapid mixing of Swendsen-Wang dynamics in two dimensions
• The Ising partition function: zeros and deterministic approximation
• Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree
• Glauber dynamics on the cycle is monotone
• The Glauber dynamics for edge‐colorings of trees
• Glauber dynamics on trees: Boundary conditions and mixing time
• Dynamics of Ising models near zero temperature: real-space renormalization approach
• Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs
• Convergence to equilibrium of logit dynamics for strategic games
• The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations
• Exact thresholds for Ising-Gibbs samplers on general graphs
• On the hardness of sampling independent sets beyond the tree threshold
• Can extra updates delay mixing?
• A manifold of pure Gibbs states of the Ising model on the Lobachevsky plane
• A law of large numbers for weighted majority
• 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
• Gibbs rapidly samples colorings of \(G(n, d/n)\)
• Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects
• Gibbs measures over locally tree-like graphs and percolative entropy over infinite regular trees
• Metastability of logit dynamics for coordination games
• Mixing time for the solid-on-solid model
• A new correlation inequality for Ising models with external fields
• Comparison of Swendsen-Wang and heat-Bath dynamics
• Glauber dynamics for the quantum Ising model in a transverse field on a regular tree
• Critical Ising on the square lattice mixes in polynomial time
• Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels
• Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
• Title not available (Why is that?)
• 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
• 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
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)
• Slow emergence of cooperation for win-stay lose-shift on trees
• Information flow on trees
• Rates of convergence for Gibbs sampling in the analysis of almost exchangeable data
• Sampling biased monotonic surfaces using exponential metrics
• 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
• Reconstructibility of a general DNA evolution model
• Rigorous inequalities between length and time scales in glassy systems
• Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width
• Learning loosely connected Markov random fields
• Reconstruction for the Potts model
• A branch-and-bound algorithm for the minimum cut linear arrangement problem
• 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
• The Swendsen-Wang Dynamics on Trees
• The Swendsen–Wang dynamics on trees
• Sub-critical exponential random graphs: concentration of measure and some applications
• Dynamical barriers for the random ferromagnetic Ising model on the Cayley tree: traveling-wave solution of the real space renormalization flow
• Non-reversible stationary states for majority voter and Ising dynamics on trees
• Title not available (Why is that?)
• Glauber dynamics on the cycles: spectral distribution of the generator
• On systematic scan for sampling \(H\)-colorings of the path

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)