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 n1/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.
|STOC Proceedings version, last modified March 2003.||Postscript||DVI|