Approximating the partition function of planar two-state spin systems

• 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 consider the problem of approximating the partition function of the hard-core model on planar graphs of degree at most 4. We show that when the activity λ   is sufficiently large, there is no fully polynomial randomised approximation scheme for evaluating the partition function unless NP=RPNP=RP. The result extends to a nearby region of the parameter space in a more general two-state spin system with three parameters. We also give a polynomial-time randomised approximation scheme for the logarithm of the partition function.