SODA Conference 2011 Conference Paper
Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees
- Ricardo Restrepo
- Daniel Stefankovic
- Juan Vera 0001
- Eric Vigoda
- Linji Yang
We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hardcore lattice gas model on the n -vertex regular b -ary tree of height h. The hard-core model is defined on independent sets weighted by an activity (or fugacity) Λ on trees. Reconstruction studies the effect of a ‘typical’ boundary condition, i. e. , fixed assignment to the leaves, on the root. The threshold for when reconstruction occurs (and a typical boundary influences the root in the limit h → ∞) has been of considerable recent interest since it appears to be connected to the efficiency of certain local algorithms on locally tree-like graphs. The reconstruction threshold occurs at ω ≈ ln b/b where Λ = ω(1 + ω) b is a convenient re-parameterization of the model. We prove that for all boundary conditions, the relaxation time τ in the non-reconstruction region is fast, namely τ = O ( n 1+ o b (1) ) for any ω ≤ ln b/b. In the reconstruction region, for all boundary conditions, we prove τ = O ( n 1+δ+ o b (1) ) for ω = (1 + δ) ln b/b, for every δ > 0. In contrast, we construct a boundary condition, for which the Glauber dynamics slows down in the reconstruction region, namely τ = Ω( n 1+δ/2− o b (1) ) for ω = (1 + δ) ln b/b, for every δ > 0. The interesting part of our proof is this lower bound result, which uses a general technique that transforms an algorithm to prove reconstruction into a set in the state space of the Glauber dynamics with poor conductance.