Deterministic counting from coupling independence

Abstract

We show that spin systems with bounded degrees and coupling independence admit fully polynomial time approximation schemes (FPTAS). We design a new recursive deterministic counting algorithm to achieve this. As applications, we give the first FPTASes for $q$-colourings on graphs of bounded maximum degree $\hat{I}”\ge 3$, when $q\ge (11/6-{\epsilon }_0)\hat{I}”$ for some small ${\epsilon }_0\approx 10^{-5}$, or when $\hat{I}”\ge 125$ and $q\ge 1.809\hat{I}”$, and on graphs with sufficiently large (but constant) girth, when $q\ge \hat{I}”+3$. These bounds match the current best randomised approximate counting algorithms by Chen, Delcourt, Moitra, Perarnau, and Postle (2019), Carlson and Vigoda (2024), and Chen, Liu, Mani, and Moitra (2023), respectively.