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

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2009 Copyright 2009 Universität Bonn, Institut für Informatik, Abt. V
85306

07.10.2009

The Mixing Time of Glauber Dynamics for Colouring Regular Trees (Revised Version)
Leslie Ann Goldberg, Mark Jerrum and Marek Karpinski
[Download PostScript] [Download PDF]

We consider Metropolis Glauber dynamics for samplingproper 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. 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/08/09 at 12:32:24
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope