The Mixing Time of Glauber Dynamics for Colouring Regular Trees

Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski

We consider Metropolis Glauber dynamics for sampling proper $q$-colourings of the $n$-vertex complete $b$-ary tree when $3\le q\le b/2\ln (b)$. We give both upper and lower bounds…