Glauber dynamics on trees:Boundary conditions and mixing time

Abstract

We give the first comprehensive analysis of the effect of boundary conditions on the mixing time of the Glauber dynamics in the so-called Bethe approximation. Specifically, we show that spectral gap and the log-Sobolev constant of the Glauber dynamics for the Ising model on an n-vertex regular tree with plus-boundary are bounded below by a constant independent of n at all temperatures and all external fields. This implies that the mixing time is O(log n) (in contrast to the free boundary case, where it is not bounded by any fixed polynomial at low temperatures). In addition, our methods yield simpler proofs and stronger results for the spectral gap and log-Sobolev constant in the regime where there are multiple phases but the mixing time is insensitive to the boundary condition. Our techniques also apply to a much wider class of models, including those with hard-core constraints like the antiferromagnetic Potts model at zero temperature (proper colorings) and the hard--core lattice gas (independent sets).

References in corpus (1)

• Phase Transitions on Nonamenable Graphs

Cited by in corpus (20)

• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Elementary bounds on Poincare and log-Sobolev constants for decomposable Markov chains
• Exact thresholds for Ising-Gibbs samplers on general graphs
• Majority dynamics on trees and the dynamic cavity method
• Robust reconstruction on trees is determined by the second eigenvalue
• On the uniqueness of Gibbs measure in the Potts model on a Cayley tree with external field
• The critical Ising model on trees, concave recursions and nonlinear capacity
• Mixing time of critical Ising model on trees is polynomial in the height
• On the mixing time of the 2D stochastic Ising model with "plus" boundary conditions at low temperature
• The Ising Partition Function: Zeros and Deterministic Approximation
• Rapid thermalization of dissipative many-body dynamics of commuting Hamiltonians
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• Kinetically constrained spin models on trees
• Dynamics of Ising models near zero temperature : Real Space Renormalization Approach
• Kawasaki dynamics beyond the uniqueness threshold
• Glauber dynamics for the quantum Ising model in a transverse field on a regular tree
• Dynamical barriers for the random ferromagnetic Ising model on the Cayley tree : traveling-wave solution of the real space renormalization flow
• The $S_k$ shuffle block dynamics