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 ω a 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+ ob (1) ) for any ω ≤ ln  b/b . In the reconstruction region, for all boundary conditions, we prove τ =  O  ( n  1+Δ+ob(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+Δ-ob(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.
['Ricardo Restrepo', 'Daniel Štefankovič', 'Juan Carlos Vera', 'Eric Vigoda', 'Linji Yang']
Phase transition for Glauber dynamics for independent sets on regular trees