discuss some background on the antiferromagnetic region below. We regard $e^{\beta J}$ as a single parameter $\lambda \geq 0$, which we will call the *activity*; thus $\lambda>1$ gives the ferromagnetic region and $\lambda<1$ gives the antiferromagnetic region. Setting $\mu(\sigma)$ to be the number of monochromatic edges in a configuration $\sigma$ (that is, $\mu(\sigma)=\sum_{(i,j)\in E} \delta(\sigma_i, \sigma_j)$), we obtain the formula $$Z(G,\lambda,q)=\sum_{\sigma\in [q]^V} \lambda^{\mu(\sigma)}.$$

[**Computing the partition function.**]{}When $q=1$ the evaluation of the partition function is trivial. It is also trivial when $q=2, \lambda=0$, which is the antiferromagnetic Ising model at zero temperature: here the partition function counts the number of proper 2-colourings of $G$. In all other cases it is \#P-hard to compute the partition function exactly, and thus there can be no efficient algorithm (running in time polynomial in the size of the underlying graph) assuming P$\neq$NP. (Note that the related Tutte polynomial has three additional points on the real plane at which it can be efficiently evaluated [@jae90], but these do not correspond to the ferromagnetic Potts model at physically meaningful points, *i.e.* where $q\geq 1$ and $ \lambda\geq 0$.) As a result of the hardness of exact evaluation, attention has been focused on approximation algorithms. The specific 