Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees

DOI10.1137/120885498zbMATH Open1301.60086arXiv1007.2255OpenAlexW2568997022MaRDI QIDQ3192167FDOQ3192167

D. Štefankovič, Ricardo L. Restrepo, Juan Vera, Linji Yang, Eric Vigoda

Publication date: 26 September 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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 $lambda$, 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 $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 non-reconstruction regions at $omeg{a}_{r}approxlnb/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_h$ 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 $omegalelnb/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)lnb/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)})$.

Full work available at URL: https://arxiv.org/abs/1007.2255

zbMATH Keywords

phase transitionmixing timeGlauber dynamicsindependent setsMarkov chain Monte Carlo hard-core model

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cited In (7)

• The Swendsen–Wang dynamics on trees
• Zero-temperature Glauber dynamics on the 3-regular tree and the median process
• Continuous phase transitions on Galton–Watson trees
• Title not available (Why is that?)
• Phase transition thresholds for some Friedman-style independence results
• Non-robust phase transitions in the generalized clock model on trees
• Generalized Farey trees, transfer operators and phase transitions

This page was built for publication: Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192167)