The mixing time of Glauber dynamics for coloring regular trees |
| |
| Authors: | Leslie Ann Goldberg Mark Jerrum Marek Karpinski |
| |
| Affiliation: | 1. Department of Computer Science, University of Liverpool, Liverpool L69 3BX, UK;2. School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, UK;3. Department of Computer Science and the Hausdorff Center for Mathematics, University of Bonn, Bonn 53117, Germany |
| |
| Abstract: | We consider Metropolis Glauber dynamics for sampling proper q‐colorings of the n‐vertex complete b‐ary tree when 3 ≤ q ≤ b/(2lnb). 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. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010 |
| |
| Keywords: | Glauber dynamics coloring trees mixing time |
|
|
