Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
Abstract
We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant D, we establish strong spatial mixing and a fully polynomial-time approximation scheme (\textbf{FPTAS}) whenever Dc<1, where c bounds the Birkhoff contraction coefficients of the interactions. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed η∈(0,1), sufficiently large fixed d, and fixed integer q≥(2+η)d, we obtain an \textbf{FPTAS} for counting proper q-colorings of G∼𝒢(n,d/n) with high probability over G. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).
Related
- Diffuse Gaussian Truncation For Deterministic Approximate Counting
- Log-concavity and Approximate Counting for Totally Unimodular Polytopes
- Counting curves with bounded intersection
- Approximate Counting for Mixed p-Spin Glasses in Weak External Fields via Cluster Expansion
- Deterministic Causal Quantization with Representative States and Bounded Error
BibTeX
@misc{li2026spatial,
title = {{Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs}},
author = {Zhidan Li and Kuan Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.12352},
eprint = {2609.12352},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.12352},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
AU - Zhidan Li
AU - Kuan Yang
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.12352
UR - https://arxiv.org/abs/2609.12352
AB - We develop a framework for deterministic approximate counting of multi-spin systems beyond bounded-degree graphs. The algorithm recursively constructs rational polytopes containing the true marginal vectors and uses linear-fractional programming to obtain certified bounds on marginal ratios. For positive interactions on graphs of polynomial connective constant D, we establish strong spatial mixing and a fully polynomial-time approximation scheme (\textbf{FPTAS}) whenever Dc<1, where c bounds the Birkhoff contraction coefficients of the interactions. We further extend the framework to proper colorings of sparse Erdős-Rényi random graphs using recursion on permissive blocks. For every fixed η∈(0,1), sufficiently large fixed d, and fixed integer q≥(2+η)d, we obtain an \textbf{FPTAS} for counting proper q-colorings of G∼𝒢(n,d/n) with high probability over G. This improves the leading constant $3$ in the earlier counting guarantee of Yin and Zhang (APPROX/RANDOM, 2016) to $2$, and asymptotically matches the spatial mixing regime established by Yin (ICALP, 2014).
ER -