Deterministic counting from coupling independence
Xiaoyu Chen, Weiming Feng, Heng Guo, Xinyuan Zhang, Zongrui Zou · arXiv (Cornell University) · 2024
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 $Δ\ge 3$, when $q\ge (11/6-\varepsilon_0)Δ$ for some small $\varepsilon_0\approx 10^{-5}$, or when $Δ\ge 125$ and $q\ge 1.809Δ$, and on graphs with sufficiently large (but constant) girth, when $q\geqΔ+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.