• Abstract:   We improve rapid mixing results for the simple Glauber dynamics designed to generate a random k-coloring of a bounded-degree graph.

  For a graph with maximum degree  Δ = Ω(log n)  and girth at least 6, we prove the Glauber dynamics has mixing time O(n log n)  when k > β Δ, where β is approximately 1.489. When the girth is only 5 our result holds for β approximately 1.763. This improves previous work of Molloy, who proved the same conclusion under the stronger assumptions that  Δ = Ω(log n)  and girth  Ω(log Δ). Our work suggests that rapid mixing results for high girth and degree graphs may extend to general graphs.

  Analogous results hold for random graphs of average degree up to n^1/4, compared with polylog(n), which was the best previously known.

  Some of our proofs rely on a new Chernoff-Hoeffding type bound, which only requires the random variables to be well-behaved with high probability. This tail inequality may be of independent interest.

Versions available:

STOC Proceedings version, last modified March 2003.

PDF

Postscript

DVI