|
|
| |
| University of Bonn -> Department of Computer Science -> Chair V | ||
| CS-Reports 2009 | Copyright 2009 University of Bonn, Department of Computer Science, 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
|
University of Bonn -> Department of Computer Science -> Chair V | |