FPTAS for hardcore and Ising models on hypergraphs

DOI10.4230/LIPICS.STACS.2016.51zbMATH Open1388.68309arXiv1509.05494OpenAlexW2964304407MaRDI QIDQ4601903FDOQ4601903

Authors: Pinyan Lu, Kuan Yang, Chihao Zhang 

Publication date: 24 January 2018

Abstract: Hardcore and Ising models are two most important families of two state spin systems in statistic physics. Partition function of spin systems is the center concept in statistic physics which connects microscopic particles and their interactions with their macroscopic and statistical properties of materials such as energy, entropy, ferromagnetism, etc. If each local interaction of the system involves only two particles, the system can be described by a graph. In this case, fully polynomial-time approximation scheme (FPTAS) for computing the partition function of both hardcore and anti-ferromagnetic Ising model was designed up to the uniqueness condition of the system. These result are the best possible since approximately computing the partition function beyond this threshold is NP-hard. In this paper, we generalize these results to general physics systems, where each local interaction may involves multiple particles. Such systems are described by hypergraphs. For hardcore model, we also provide FPTAS up to the uniqueness condition, and for anti-ferromagnetic Ising model, we obtain FPTAS where a slightly stronger condition holds.

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

Recommendations

• Approximating the partition function of planar two-state spin systems
• Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The computational complexity of two‐state spin systems
• Approximate counting via correlation decay in spin systems

zbMATH Keywords

Ising modelhard-core modelhypergraphcorrelation decayspatial mixing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Hypergraphs (05C65) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Cited In (5)

• The Ising partition function: zeros and deterministic approximation
• Counting hypergraph matchings up to uniqueness threshold
• More on zeros and approximation of the Ising partition function
• Approximation via Correlation Decay When Strong Spatial Mixing Fails
• An FPTAS for the hardcore model on random regular bipartite graphs

This page was built for publication: FPTAS for hardcore and Ising models on hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601903)