We give algorithms for approximating the partition function of the ferromagnetic Potts model on $d$-regular expanding graphs. We require much weaker expansion 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, using extremal graph theory and applications of Karger's algorithm to counting 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 believe that these methods can shed more light on other important problems such as sub-exponential algorithms for approximate counting problems.

翻译：我们给出了接近铁磁政器模型在 $d$ 常规扩张图形上的分割函数的算法。 我们要求的扩展比以往的工程要弱得多; 例如,超立方所展示的扩张就足够了。 主要改进来自于对标准聚合模型的更清晰分析, 使用极分图理论和Karger算法的运用来计算可能具有独立兴趣的削减值。 #BIS很难在约束度图形的低温中将分割函数相近, 因此我们的算法可以被视为证明 #BIS 的难例是罕见的。 我们相信, 这些方法可以更清楚地揭示其它重要问题, 比如用于估算问题的亚爆炸性算法 。