Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees - Mathematics > ProbabilityReport as inadecuate

Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees - Mathematics > Probability - Download this document for free, or read online. Document in PDF available to download.

Abstract: We study the effect of boundary conditions on the relaxation time of theGlauber dynamics for the hard-core model on the tree. The hard-core model isdefined on the set of independent sets weighted by a parameter $\lambda$,called the activity. The Glauber dynamics is the Markov chain that updates arandomly chosen vertex in each step. On the infinite tree with branching factor$b$, the hard-core model can be equivalently defined as a broadcasting processwith a parameter $\omega$ which is the positive solution to$\lambda=\omega1+\omega^b$, and vertices are occupied with probability$\omega-1+\omega$ when their parent is unoccupied. This broadcasting processundergoes a phase transition between the so-called reconstruction andnon-reconstruction regions at $\omega r\approx \ln{b}-b$. Reconstruction hasbeen of considerable interest recently since it appears to be intimatelyconnected 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 ofthe Glauber dynamics on regular $b$-ary trees $T h$ of height $h$ and $n$vertices, undergoes a phase transition around the reconstruction threshold. Inparticular, we construct a boundary condition for which the relaxation timeslows 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$\Omegan$ and $On^{1+o b1}$. In contrast, above the reconstructionthreshold 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 $On^{1+\delta +o b1}$, and we construct a boundary condition where the relaxation time is$\Omegan^{1+\delta-2 - o b1}$.

Author: Ricardo Restrepo, Daniel Stefankovic, Juan C. Vera, Eric Vigoda, Linji Yang


Related documents