### Abstract

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*T*of height_{h}*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*T*with any boundary condition, the relaxation time is Ω(_{h}*n*) and*O*(*n*^{1+ob(1)}). In contrast, above the reconstruction threshold we show that for every δ>0, for ω=(1+δ)ln*b/b*, the relaxation time on*T*with any boundary condition is_{h}*O*(*n*^{1+δ+ob(1)}), and we construct a boundary condition where the relaxation time is Ω(n^{1+δ/2−ob(1)}).Original language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11) |

Editors | D. Randall |

Place of Publication | Philadelphia |

Publisher | SIAM |

Pages | 945-956 |

Publication status | Published - 2011 |

### Publication series

Name | SIAM Journal on Discrete Mathematics |
---|

## Fingerprint 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

Restrepo, R., Stefankovic, D., Vera, J. C., Vigoda, E., & Yang, L. (2011). Phase transition for the Glauber dynamics for the independent sets on regular trees. In D. Randall (Ed.),

*Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11)*(pp. 945-956). (SIAM Journal on Discrete Mathematics). SIAM. http://dl.acm.org/citation.cfm?id=2133109