Approximating the partition function of planar two-state spin systems

作者:

Highlights:

• We study approximation of the hard-core partition function.

• Our graphs are planar with degree at most 4.

• We show that the problem is intractable for sufficiently high activity.

• However, the logarithm of the partition function can be approximated.

摘要

•We study approximation of the hard-core partition function.•Our graphs are planar with degree at most 4.•We show that the problem is intractable for sufficiently high activity.•However, the logarithm of the partition function can be approximated.

论文关键词:Counting complexity,Independent sets,Hard-core model,Planar graphs,Phase transition

论文评审过程:Received 3 October 2013, Revised 22 May 2014, Accepted 14 June 2014, Available online 28 June 2014.

论文官网地址:https://doi.org/10.1016/j.jcss.2014.06.007