The Glauber Dynamics for Colourings of Bounded Degree Trees
- Brendan Lucier ,
- Mike Molloy
SIAM (Society for Industrial and Applied Mathematics) Journal on Discrete Mathematics 2011 | , Vol 25: pp. 827-853
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 the complete tree is nƟ(1+/(k log ∆)). For k >= 4 we extend our analysis to show that the mixing time on any tree is at most nO(1+/(k log ∆)). Our proof uses a weighted canonical paths analysis and introduces a variation of the block dynamics that exploits the di ffering relaxation times of blocks.