Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, 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 ≤ qb/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
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope