@inproceedings{lucier2009the,
author = {Lucier, Brendan and Molloy, Mike and Peres, Yuval},
title = {The Glauber Dynamics for Colourings of Bounded Degree Trees},
booktitle = {International Workshop on Randomization and Computation 2009},
year = {2009},
month = {January},
abstract = {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.},
url = {http://approjects.co.za/?big=en-us/research/publication/glauber-dynamics-colourings-bounded-degree-trees-2/},
edition = {International Workshop on Randomization and Computation 2009},
}