The Glauber Dynamics for Colourings of Bounded Degree Trees
- Brendan Lucier ,
- Michael Molloy ,
- Yuval Peres
12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009. Proceedings |
Published by Springer Berlin Heidelberg
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 n O(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.