Randomly coloring graphs of girth at least five

We improve rapid mixing results for the simple Glauber dynamics designed to generate a random k-coloring of a bounded-degree graph. Let G be a graph with maximum degree Δ = ω(log n), and girth ≥ 5. We prove that if k > αΔ, where α ≈ 1.763 then Glauber dynamics has mixing time O(n log n). If girth(G)≥ 6 and k > βΔ, where β ≈ 1.489 then Glauber dynamics has mixing time O(n log n). This improves a recent result 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 wellbehaved with high probability. This tail inequality may be of independent interest.