Glauber Dynamics on Trees: Boundary Conditions and Mixing Time.

We give the first comprehensive analysis of the effect of boundary conditions on the mixing time of the Glauber dynamics in the so-calledBethe approximation. Specifically, we show that the spectral gap and the log-Sobolev constant of the Glauber dynamics for the Ising model on ann-vertex regular tree with (+)-boundary are bounded below by a constant independent ofnat all temperatures and all external fields. This implies that the mixing time isO(logn) (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 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). [ABSTRACT FROM AUTHOR]