### Abstract

Original language | English |
---|---|

Pages (from-to) | 835-861 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 28 |

Issue number | 2 |

DOIs | |

Publication status | Published - 2014 |

### Fingerprint

### Keywords

- phase transition
- mixing time
- Glauber dynamics
- Markov chain
- Monte Carlo hard-core model
- independent sets

### Cite this

*SIAM Journal on Discrete Mathematics*,

*28*(2), 835-861. https://doi.org/10.1137/120885498

}

*SIAM Journal on Discrete Mathematics*, vol. 28, no. 2, pp. 835-861. https://doi.org/10.1137/120885498

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

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

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

AU - Restrepo, R.

AU - Stefankovic, D.

AU - Vera Lizcano, J.C.

AU - Vigoda, E.

AU - Yang, L.

PY - 2014

Y1 - 2014

N2 - We study the effect of boundary conditions on the relaxation time (i.e., inverse spectral gap) 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 $\lambda$, called the activity or fugacity. 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 $\omega$ which is the positive solution to $\lambda=\omega(1+\omega)^b$, and vertices are occupied with probability $\omega/(1+\omega)$ when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and nonreconstruction regions at $\omega_r\approx \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 trees $T_h$ of height $h$ with branching factor $b$ 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 $\omega \le \ln{b}/b$, for $T_h$ with any boundary condition, the relaxation time is $\Omega(n)$ and $O(n^{1+o_b(1)})$. In contrast, above the reconstruction threshold we show that for every $\delta>0$, for $\omega=(1+\delta)\ln{b}/b$, the relaxation time on $T_h$ with any boundary condition is $O(n^{1+\delta + o_b(1)})$, and we construct a boundary condition where the relaxation time is $\Omega(n^{1+\delta/2 - o_b(1)})$. To prove this lower bound in the reconstruction region we introduce a general technique that transforms a reconstruction algorithm into a set with poor conductance.

AB - We study the effect of boundary conditions on the relaxation time (i.e., inverse spectral gap) 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 $\lambda$, called the activity or fugacity. 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 $\omega$ which is the positive solution to $\lambda=\omega(1+\omega)^b$, and vertices are occupied with probability $\omega/(1+\omega)$ when their parent is unoccupied. This broadcasting process undergoes a phase transition between the so-called reconstruction and nonreconstruction regions at $\omega_r\approx \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 trees $T_h$ of height $h$ with branching factor $b$ 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 $\omega \le \ln{b}/b$, for $T_h$ with any boundary condition, the relaxation time is $\Omega(n)$ and $O(n^{1+o_b(1)})$. In contrast, above the reconstruction threshold we show that for every $\delta>0$, for $\omega=(1+\delta)\ln{b}/b$, the relaxation time on $T_h$ with any boundary condition is $O(n^{1+\delta + o_b(1)})$, and we construct a boundary condition where the relaxation time is $\Omega(n^{1+\delta/2 - o_b(1)})$. To prove this lower bound in the reconstruction region we introduce a general technique that transforms a reconstruction algorithm into a set with poor conductance.

KW - phase transition

KW - mixing time

KW - Glauber dynamics

KW - Markov chain

KW - Monte Carlo hard-core model

KW - independent sets

U2 - 10.1137/120885498

DO - 10.1137/120885498

M3 - Article

VL - 28

SP - 835

EP - 861

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -