On the optimality of the Arf invariant formula for graph polynomials

Abstrakt

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.

Klíčová slova

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