Deterministic Counting from Coupling Independence

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 $\Delta \geq 3$, when $q \geq\left(11 / 6-\varepsilon_{0}\right) \Delta$ for some small $\varepsilon_{0} \approx 10^{-5}$, or when $\Delta \geq 125$ and $q \geq 1. 809 \Delta$, and on graphs with sufficiently large (but constant) girth, when $q \geq \Delta+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.

Authors

• Xiaoyu Chen
• Weiming Feng 0001
• Heng Guo 0001
• Xinyuan Zhang
• Zongrui Zou

Keywords

• Couplings
• Computer science
• Spin systems
• Approximation algorithms
• Linear programming
• Polynomials
• Estimation Algorithm
• Spin System
• Maximum Degree
• Recursive Algorithm
• Counting Algorithm
• Lower Bound
• Markov Chain
• Efficient Algorithm
• Constant Factor
• Leaf Node
• Strong Results
• Marginal Probability
• Hamming Distance
• Binary Search
• Marginal Estimates
• Alternative Metrics
• Rapid Mixing
• Decay Of Correlations
• Partial Configuration
• Wasserstein Distance
• Deterministic Approximation
• Recursive Step
• deterministic counting
• coupling independence
• graph colouring
• Markov chains