On the optimality of the Arf invariant formula for graph polynomials

Abstract

We prove optimality of the Arf invariant formula for the generating function of even subgraphs, or, equivalently, the Ising partition function, of a graph. It is shown that the Ising partition function has an exponential additive determinantal complexity.

This provides one of the first exponential complexity lower bounds.

Keywords

• Ising partition function
• Arf invariant formula
• Graph embedding
• Pfaffian
• Complexity