TY - GEN

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

AU - Restrepo, R.

AU - Stefankovic, D.

AU - Vera, J.C.

AU - Vigoda, E.

AU - Yang, L.

PY - 2011

Y1 - 2011

N2 - 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)).

AB - 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)).

M3 - Conference contribution

T3 - SIAM Journal on Discrete Mathematics

SP - 945

EP - 956

BT - Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11)

A2 - Randall, D.

PB - SIAM

CY - Philadelphia

ER -