Approximation of planar hard-core partition functions
Follow the latest progress by email.
For a planar graph G at fixed hard-core activity λ>0, can its independent-set partition function be approximated efficiently without bounding the maximum degree?
Why it matters and what counts as progress
Why it matters: A degree-independent activity interval would cover planar graphs excluded by correlation-decay results whose admissible activity shrinks with degree.
What counts as progress: A randomized polynomial-time approximation scheme for all planar graphs at a stated constant activity range, with relative-error and success guarantees.
How the problem developed
- 2006 · Algorithm [1]
Doron Weitz Established correlation-decay approximation for hard-core partition functions below the tree uniqueness threshold on graphs with bounded maximum degree.
- 2015 · Hardness result [2]
Leslie Ann Goldberg, Mark Jerrum and Colin McQuillan Showed approximation hardness on planar graphs at activity above 312, even with maximum degree four.
- 6 Aug 2026 · Reported claim [3]
Heng Guo and Xinyuan Zhang Gave an FPRAS on arbitrary planar graphs for sufficiently small constant activity, with 1/1443 as a sufficient threshold.
AI contribution
Approximating spin systems on planar graphs
For planar graphs at sufficiently small fixed hard-core activity, including λ≤1/1443, Guo and Zhang give a randomized polynomial-time approximation scheme for the partition function without a maximum-degree bound.
Sources
Website timeline
Publication dates and editorial changes.
GPT-origin ideas yield a planar hard-core approximation scheme