Algorithms for the ferromagnetic Potts model on expanders

Abstract

We give algorithms for approximating the partition function of the ferromagnetic $q$-color Potts model on graphs of maximum degree $d$. Our primary contribution is a fully polynomial-time 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$.

v3: 30 pages, minor revisions incorporating referee comments, to appear in Combinatorics, Probability, and Computing; extended abstract of an earlier version appeared in FOCS

References in corpus (7)

• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Approximating the partition function of the ferromagnetic Potts model
• On replica symmetry of large deviations in random graphs
• Independent sets in the hypercube revisited
• Metastability of the Potts ferromagnet on random regular graphs
• Random-cluster dynamics on random regular graphs in tree uniqueness
• Optimal Bounds for the $k$-cut Problem

Cited by in corpus (1)

• Efficient Algorithms for Weakly-Interacting Quantum Spin Systems