Abstract Polymer Models and the Cluster Expansion
Talkat Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019) · 2019-03-18..03-22
summary
Gives an FPTAS and efficient sampler for the ferromagnetic Q‑state Potts partition function on max‑degree Δ, α‑expander graphs when β ≥ C·(log(QΔ))/α (C constant), by mapping low‑temperature colorings to an abstract polymer model, proving Kotecký–Preiss convergence, truncating the cluster expansion at size O(log n/ε), and enumerating connected clusters in bounded‑degree graphs; implementation cost is polynomial in n and 1/ε (exponential only in cluster size).
AI-written summary · about