Algorithms for the ferromagnetic Potts model on expanders

We give algorithms for approximating the partition function of the ferromagnetic qcolor Potts model on graphs of maximum degree d. Our primary contribution is a fully polynomialtime approximation scheme for d-regular graphs with an expansion condition at low temperatures (that is, bounded away from the order-disorder threshold). The expansion condition is much weaker than in previous works; for example, the expansion exhibited by the hypercube suffices. The main improvements come from a significantly sharper analysis of standard polymer models; we use extremal graph theory and applications of Karger's algorithm to count cuts that may be of independent interest. It is #BIS-hard to approximate the partition function at low temperatures on bounded-degree graphs, so our algorithm can be seen as evidence that hard instances of #BIS are rare. We also obtain efficient algorithms in the Gibbs uniqueness region for bounded-degree graphs. While our high temperature proof follows more standard polymer model analysis, our result holds in the largest known range of parameters d and q.