sufficiently large toroidal grids (with a mixing time exponential in $\beta$ and in $L$, the side length of the grid). This improved on the earlier result [@bor99].

Mixing time upper bounds {#se:rapid}
========================

Our goal in this section is to give good lower bounds on the number of colours needed for the Glauber dynamics to mix rapidly. We begin by describing the notions of coupling and path coupling, which are very useful tools in proving upper bounds on mixing times for Markov chains. In Section \[se:GD\], we apply path coupling directly to the Glauber dynamics of bounded-degree graphs to obtain our first lower bound on the number of colours needed for rapid mixing. In Section \[se:BD\], we consider block dynamics, a more general type of dynamics that can be used to sample from the Gibbs distribution. We give a general lower bound on the number of colours needed for rapid mixing of block dynamics (Theorem \[le:block\]). We illustrate how to apply Theorem \[le:block\] to bounded-degree graphs in Section \[se:grid\]. In Section \[se:comparison\], we relate the mixing times of Glauber dynamics to that of the block dynamics and show how this gives various improvements to the bounds obtained in Section \[se:GD\]. 