The Glauber dynamics on colorings of a graph with high girth and maximum degree
We prove that the Glauber dynamics on the C-colorings of a graph G on n vertices with girth g and maximum degree Delta mixes rapidly if (i) C=qDelta and q>q*, where q*=1.4890... is the root of (1-e(-1/q))(2) + qe(-1)/(q)=1; and (ii) Deltagreater than or equal toD log n and ggreater than or equal toD log Delta for some constant D=D(q). This improves the bound of roughly 1.763Delta obtained by Dyer and Frieze [Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 2001] for the same class of graphs. Our bound on this class of graphs is lower than the bound of 11Delta/6approximate to1.833Delta obtained by Vigoda [J. Math. Phys., 41 (2000), pp. 1555-1569] for general graphs.
glauber dynamics colorings rapidly mixing markov chains