} u \not= v, \\
    c       &\text{if } u = v.
    \end{cases}$

Then $X_{t+1}$ is the new state. We write $\mathcal{M}_{\mathrm{GD}} = \mathcal{M}_{\mathrm{GD}}(G,\lambda,q)$ for the Glauber dynamics as described above.

We say that $\mathcal{M}_{\mathrm{GD}}$ *mixes rapidly* if $\tau(\mathcal{M},\varepsilon)$ is polynomial in $\log{|\Omega|}$, that is, polynomial in $n$. If $\tau(\mathcal{M},\varepsilon)$ is exponential in $n$, then we say that $\mathcal{M}_{\mathrm{GD}}$ *mixes slowly*.

Results
-------

Our main results are stated below. In order to keep the presentation simple at this stage, we sometimes postpone giving the explicit relationships amongst constants and mixing times until later, but in each case, we direct the reader to where a more detailed statement can be found.

In Theorem \[th:main1\] we present our first, and simplest, bound on the number of colours, as a function of $\lambda$ and $\Delta$, that guarantees rapid mixing of Glauber dynamics. Although Theorem \[th:main1\] follows from a standard coupling argument, for completeness we prove it here, as we will need this result later to establish our improved bounds.

\[th:main1\] Let $\Delta,q\geq 2$ be integers and take $\lambda>1$ such that $q\geq \Delta\lambda^\Delta + 1$. Then the Glauber dynamics of the $q$-state Potts model at activity $\lambda$ mixes rapidly for the class of graphs of 