Phase transition for Glauber dynamics for independent sets on regular trees

DOI10.1137/120885498MaRDI QIDQ3192167zbMATH OpenOpenAlexFDO

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

Publication date 26 September 2014

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

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)

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)})$.

Recommendations

• Phase transition for Glauber dynamics for independent sets on regular trees
• Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
• scientific article; zbMATH DE number 6297817
• Fast mixing for independent sets, colorings, and other models on trees
• Glauber dynamics on trees and hyperbolic graphs

Cited in

(10)

• Zero-temperature Glauber dynamics on the 3-regular tree and the median process
• The Swendsen–Wang dynamics on trees
• Continuous phase transitions on Galton–Watson trees
• scientific article; zbMATH DE number 6297817 (Why is no real title available?)
• Phase transition thresholds for some Friedman-style independence results
• Reconstruction threshold for the hardcore model
• Glauber dynamics on trees and hyperbolic graphs
• Non-robust phase transitions in the generalized clock model on trees
• Phase transition for Glauber dynamics for independent sets on regular 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)