Phase transition for the mixing time of the Glauber dynamics for coloring regular trees
arXiv:0908.2665 · doi:10.1214/11-AAP833
Abstract
We prove that the mixing time of the Glauber dynamics for random k-colorings of the complete tree with branching factor b undergoes a phase transition at . Our main result shows nearly sharp bounds on the mixing time of the dynamics on the complete tree with n vertices for colors with constant C. For we prove the mixing time is . On the other side, for the mixing time experiences a slowing down; in particular, we prove it is and . The critical point C=1 is interesting since it coincides (at least up to first order) with the so-called reconstruction threshold which was recently established by Sly. The reconstruction threshold has been of considerable interest recently since it appears to have close connections to the efficiency of certain local algorithms, and this work was inspired by our attempt to understand these connections in this particular setting.
arXiv commentPublished in at http://dx.doi.org/10.1214/11-AAP833 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (10)
- Algorithmic barriers from phase transitions
- Glauber dynamics on trees:Boundary conditions and mixing time
- Coupling with the stationary distribution and improved sampling for colorings and independent sets
- Reconstruction of Random Colourings
- Markov chain comparison
- A general lower bound for mixing of single-site dynamics on graphs
- Mixing time of critical Ising model on trees is polynomial in the height
- Randomly coloring planar graphs with fewer colors than the maximum degree
- The Mixing Time of Glauber Dynamics for Colouring Regular Trees
- Gibbs Rapidly Samples Colorings of G(n,d/n)
Cited by in corpus (4)
- Large Degree Asymptotics and the Reconstruction Threshold of the Asymmetric Binary Channels
- The Tightness of the Kesten-Stigum Reconstruction Bound of Symmetric Model with Multiple Mutations
- Big Data Information Reconstruction on an Infinite Tree for a -state Asymmetric Model with Community Effects
- Making mean-estimation more efficient using an MCMC trace variance approach: DynaMITE