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

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 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
PublisherSIAM
Pages945-956
Publication statusPublished - 2011

Publication series

NameSIAM Journal on Discrete Mathematics

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). Philadelphia: SIAM.
Restrepo, R. ; Stefankovic, D. ; Vera, J.C. ; Vigoda, E. ; Yang, L. / Phase transition for the Glauber dynamics for the independent sets on regular trees. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11). editor / D. Randall. Philadelphia : SIAM, 2011. pp. 945-956 (SIAM Journal on Discrete Mathematics).
@inproceedings{a204db19f5eb44c0b65b86315b1452b4,
title = "Phase transition for the Glauber dynamics for the independent sets on regular trees",
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 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)).",
author = "R. Restrepo and D. Stefankovic and J.C. Vera and E. Vigoda and L. Yang",
year = "2011",
language = "English",
series = "SIAM Journal on Discrete Mathematics",
publisher = "SIAM",
pages = "945--956",
editor = "D. Randall",
booktitle = "Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11)",

}

Restrepo, R, Stefankovic, D, Vera, JC, 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). 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.

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11). ed. / D. Randall. Philadelphia : SIAM, 2011. p. 945-956 (SIAM Journal on Discrete Mathematics).

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-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 -

Restrepo R, Stefankovic D, Vera JC, Vigoda E, Yang L. Phase transition for the Glauber dynamics for the independent sets on regular trees. In Randall D, editor, Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA11). Philadelphia: SIAM. 2011. p. 945-956. (SIAM Journal on Discrete Mathematics).