Spatial mixing and the connective constant: Optimal bounds

DOI10.1137/1.9781611973730.102zbMath1372.05102arXiv1410.2595OpenAlexW2949783835MaRDI QIDQ5363052

Piyush Srivastava, Yitong Yin, Alistair Sinclair, Daniel Štefanković

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1410.2595

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (5)

Unnamed Item ⋮ Approximation via Correlation Decay When Strong Spatial Mixing Fails ⋮ Faster exponential-time algorithms for approximately counting independent sets ⋮ Improved Bounds on the Phase Transition for the Hard-Core Model in 2-Dimensions ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model

This page was built for publication: Spatial mixing and the connective constant: Optimal bounds