the glauber dynamics on colourings of a graph with high girth and maximum degree
(MATH) We prove that the Glauber dynamics on the C -colourings of a graph G on n vertices with girth g and maximum degree $\D$ mixes rapidly if (i) $C=q\D$ and $q>q^*$ where $q^*=1.4890... $ is the root of $(1-\rme^{-1/q})^2+q\rme^{-1/q}=1$; and (ii) $\D\geq D\log n$ and $g\geq D\log\D$ for some constant $D=D(q)$. This improves the corresponding result with $q\geq1.763\D$ obtained by Dyer and Frieze [FOCS01] for the same class of graphs.
markov chain rapidly mixing