Phase transition for the Glauber dynamics for the independent sets on regular trees

R. Restrepo, D. Stefankovic, J.C. Vera, E. Vigoda, L. Yang

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

4 Citations (Scopus)


We study the effect of boundary conditions on the relaxation time of the Glauber dynamics for the hard-core model on the tree. The hard-core model is defined on the set of independent sets weighted by a parameter λ, called the activity. The Glauber dynamics is the Markov chain that updates a randomly chosen vertex in each step. On the infinite tree with branching factor b, the hard-core model can be equivalently defined as a broadcasting process with a parameter ω which is the positive solution to λ=ω(1+ω)b, and vertices are occupied with probability ω/(1+ω) when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and non-reconstruction regions at ωr≈ln b/b. Reconstruction has been of considerable interest recently since it appears to be intimately connected to the efficiency of local algorithms on locally tree-like graphs, such as sparse random graphs. In this paper we show that the relaxation time of the Glauber dynamics on regular b-ary trees Th of height h and n vertices, undergoes a phase transition around the reconstruction threshold. In particular, we construct a boundary condition for which the relaxation time slows down at the reconstruction threshold. More precisely, for any ω≤ln b/b, for Th with any boundary condition, the relaxation time is Ω(n) and O(n1+ob(1)). In contrast, above the reconstruction threshold we show that for every δ>0, for ω=(1+δ)ln b/b, the relaxation time on Th with any boundary condition is O(n1+δ+ob(1)), and we construct a boundary condition where the relaxation time is Ω(n1+δ/2−ob(1)).
Original languageEnglish
Title of host publicationProceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11)
EditorsD. Randall
Place of PublicationPhiladelphia
Publication statusPublished - 2011

Publication series

NameSIAM Journal on Discrete Mathematics


Dive into the research topics of 'Phase transition for the Glauber dynamics for the independent sets on regular trees'. Together they form a unique fingerprint.

Cite this