Previous chapter Next chapter Full AccessProceedings Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Phase Transition for Glauber Dynamics for Independent Sets on Regular TreesRicardo Restrepo, Daniel Stefankovic, Juan C. Vera, Eric Vigoda, and Linji YangRicardo Restrepo, Daniel Stefankovic, Juan C. Vera, Eric Vigoda, and Linji Yangpp.945 - 956Chapter DOI:https://doi.org/10.1137/1.9781611973082.73PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract 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(n1+ob(1)) for any ω ≤ ln b/b. In the reconstruction region, for all boundary conditions, we prove τ = O(n1+δ+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 τ = Ω(n1+δ/2−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. Previous chapter Next chapter RelatedDetails Published:2011ISBN:978-0-89871-993-2eISBN:978-1-61197-308-2 https://doi.org/10.1137/1.9781611973082Book Series Name:ProceedingsBook Code:PR138Book Pages:xviii-1788