turns out that conductance for the Glauber dynamics is related to the expansion properties of the underlying graph, and so we prove that almost all $\Delta$-regular graphs have the relevant property. This argument alone gives a worse bound than that in Theorem \[th:main2\](ii), but combined with the solution of an interesting extremal problem (proved in Section \[se:extremal\]), which we believe may be of independent interest, we are able to obtain the required improvement.

Theorem \[th:main2\](i) is proved by first using a coupling argument to prove a rapid-mixing result for block dynamics (a more general form of dynamics than Glauber dynamics) and then using a Markov chain comparison argument to obtain rapid mixing for Glauber dynamics. In proving Theorem \[th:main2\](i), we derive a general combinatorial condition on graphs that guarantees rapid mixing of Glauber dynamics (Theorem \[se:grid\] combined with Corollary \[co:comparison\]). This condition can be used to improve the bounds of Theorem \[th:main2\](i) for graph classes of maximum degree $\Delta$ with “low expansion”. We illustrate this in Theorem \[th:main3\] below with the example of the toroidal grid.

\[th:main3\] For any $\eta\in (0,1)$ there are constants $c_3$, $c_4$ and $c_5$ (depending on $\eta$), such that for any positive integer $q$ and any 