### Abstract

*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 |
---|

### Cite this

*Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11)*(pp. 945-956). (SIAM Journal on Discrete Mathematics). Philadelphia: SIAM.

}

*Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11).*SIAM Journal on Discrete Mathematics, SIAM, Philadelphia, pp. 945-956.

**Phase transition for the Glauber dynamics for the independent sets on regular trees.** / Restrepo, R.; Stefankovic, D.; Vera, J.C.; Vigoda, E.; Yang, L.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

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 -