question is: for what classes of graphs and what ranges of $q$ and $\lambda$ is there a fully polynomial randomised approximation scheme (FPRAS) for computing the partition function?

In the anti-ferromagnetic case, $\lambda<1$, there can be no FPRAS for the partition function unless NP=RP, except when $q=1$ (for all $\lambda$) and when $q=2$ and $\lambda=0$ [@gol08]. For the ferromagnetic region, $\lambda>1$, there is only known to be an FPRAS when $q=2$ (the Ising model) for general graphs at any temperature [@jer93]. There is also an FPRAS for the entire ferromagnetic region (no restriction on $q$) if we restrict the underlying graphs to the class of dense graphs (those having minimum degree $\Omega(n)$ [@alo95], or having edge connectivity at least $\Omega(\log n)$ [@kar99]). In terms of approximation complexity, approximating the partition function of the ferromagnetic Potts model is equivalent to \#BIS, which is the problem of approximating the number of independent sets in a bipartite graph [@gol12]. This puts it in an interesting class of approximation problems, namely, those which are \#BIS-equivalent: no such problem is known to be hard, but none have been shown to exhibit an FPRAS [@dye03b].

[**Glauber dynamics.**]{}A standard approach to approximating the partition function is to 