Algorithms for the ferromagnetic Potts model on expanders (Q6632817)

In this paper the authors present algorithms for approximating partition functions of $q$-state Potts models on various expander graphs of degree $d$. The authors strengthen the regime of $q$'s and $d$'s for which they obtain results, and their main tool are polymer and cluster expansion arguments. They obtain a polynomial-time approximation for $d$-regular graphs satisfying some expansion condition. They show that, although in general for bounded-degree graphs the problem is \#BIS-hard at low temperatures, in some sense for most graphs this is not the case,