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)).
|Title of host publication||Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11)|
|Place of Publication||Philadelphia|
|Publication status||Published - 2011|
|Name||SIAM Journal on Discrete Mathematics|