The Glauber Dynamics for Colourings of Bounded Degree Trees
- Brendan Lucier ,
- Mike Molloy ,
- Yuval Peres
International Workshop on Randomization and Computation 2009 |
We study the Glauber dynamics Markov chain for k-colourings of trees with maximum degree ∆. For k >= 3, we show that the mixing time on every tree is at most nO(1+∆/(k log∆)). This bound is tight up to the constant factor in the exponent, as evidenced by the complete tree. Our proof uses a weighted canonical paths analysis and a variation of the block dynamics that exploits the differing relaxation times of blocks.