Approximating the partition function of planar two-state spin systems

DOI10.1016/J.JCSS.2014.06.007zbMath1401.05279arXiv1208.4987OpenAlexW2032098252MaRDI QIDQ743131

Leslie Ann Goldberg, Colin McQuillan, Mark R. Jerrum

Publication date: 22 September 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionplanar graphsindependent setshard-core modelcounting complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (3)

\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region ⋮ Counting in two-spin models on \(d\)-regular graphs ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits

Cites Work

• Random generation of combinatorial structures from a uniform distribution
• Some observations on the probabilistic algorithms and NP-hard problems
• Some simplified NP-complete graph problems
• Correlation inequalities on some partially ordered sets
• A partial k-arboretum of graphs with bounded treewidth
• Percolation and the hard-core lattice gas model
• Improved mixing condition on the grid for counting and sampling independent sets
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The problem of uniqueness of a Gibbsian random field and the problem of phase transitions
• Boundary-to-Boundary Flows in Planar Graphs
• Improved inapproximability results for counting independent sets in the hard-core model
• Counting independent sets up to the tree threshold
• Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities
• Polynomial-Time Approximation Algorithms for the Ising Model
• Slow mixing of glauber dynamics via topological obstructions
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• The computational complexity of two‐state spin systems
• Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models
• Correlation Decay up to Uniqueness in Spin Systems

This page was built for publication: Approximating the partition function of planar two-state spin systems