Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2008 Copyright 2008 University of Bonn, Department of Computer Science, Abt. V
85291

06.06.2008

Mixing Rate of Glauber Dynamics for Sampling Colourings
of Regular Trees with Few Colours
Leslie Ann Goldberg, Mark Jerrum and Marek Karpinski
[Download PostScript] [Download PDF]

We consider Metropolis Glauber dynamics for sampling proper q-colourings of the n-vertex complete b-ary tree when 3 ≤ q ≤ b/2 ln(b). We give both upper and lower bounds on the mixing time. For fixed q and b, our upper bound is nO(b/log(b)) and our lower bound is nΩ(b/q log(b)), where the constants implicit in the O() and Ω() notation do not depend upon n, q or b.

Last Change: 10/10/08 at 13:23:33
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V