Minimum number of Pfaffians representing the Ising partition function of a non-planar graph

By Kasteleyn's theorem the Ising partition function of a planar graph is a single Pfaffian; for a graph of orientable genus $g$ the classical formulas use $4^g$ real Pfaffians, and Gobron's multicomplex formulation gives $2^{\tilde g}$ complex Pfaffians, where $\tilde g$ is the non-orientable genus. Gobron (2013) left open the minimum number of real or complex Pfaffians whose linear combination equals the partition function for all edge weights: any non-trivial lower bound depending on the genus, and whether the exponential genus-dependence can be reduced. Loebl and Masbaum (2011) proved that in the classical orientation-based framework (Pfaffians of the Fisher blow-up induced by a common admissible orientation) the minimum is exactly $4^g$. The open core concerns the strictly wider class in which Gobron's own results live - per-term matrices with arbitrary real or complex entries and complex Pfaffians - where the only known lower bound is $2$ for every non-planar graph in identities without real-part extraction (with real-part extraction allowed, the multicomplex construction with $\mathbb{C}_1=\mathbb{C}$ already gives a single complex Pfaffian for every graph of non-orientable genus $1$), no genus-dependent bound is known, and no subexponential improvement of $4^g$ or $2^{\tilde g}$ is established. The dimer analogue was resolved only in 2026 by exponential lower bounds of Pant and Singh, $(8/3)^g$, whose methods do not transfer to the Ising specialization.

Background

The Ising model on a finite graph $G=(V,E)$ assigns spins $\sigma_v\in\{+1,-1\}$ to vertices and interaction constants to edges; its partition function $Z_G(w)$, the sum of $\exp(\sum_e w_e\sigma_u\sigma_v)$ over all spin configurations with edge weights $w_e$, is the normalizing constant from which the thermodynamics of the model follows. By van der Waerden's high-temperature expansion, $Z_G$ equals a simple prefactor times the even-subgraph polynomial $E_G(x)=\sum_{H}\prod_{e\in H}x_e$, where the sum runs over subgraphs $H\subseteq E$ in which every vertex has even degree; computing $Z_G$ and computing $E_G$ are equivalent.

The Pfaffian of a $2n\times 2n$ skew-symmetric matrix $A$ is the signed sum $\mathrm{Pf}(A)=\sum_{M}\pm\prod_{\{i,j\}\in M}A_{ij}$ over the perfect matchings $M$ of the index set, where the sign is determined by the permutation structure of $M$; it satisfies $\mathrm{Pf}(A)^2=\det A$ and is computable in polynomial time. Fisher observed that each vertex of $G$ can be replaced by a small planar gadget (a 'blow-up') so that the perfect matchings of the resulting graph are in bijection with the even subgraphs of $G$; with the gadget-edge weights set to $1$, its dimer (perfect-matching) partition function then equals $E_G$. Gobron works with an edge-indexed version of this construction, the dart graph $D(G)$: it has one vertex per incidence (dart) of $G$ - the gadget at each vertex is the complete graph on its darts, and one edge per edge of $G$ joins its two darts - and the constants carried by the gadget entries are tuned rather than set to $1$. Kasteleyn proved that for planar $G$ the edges can be oriented so that all perfect matchings contribute with the same sign in the Pfaffian expansion - a Pfaffian orientation - yielding $Z_G$ as a single Pfaffian of a skew-symmetric matrix with entries $\pm x_e$, the combinatorial root of the exact solvability of two-dimensional Ising models. He also asserted, and Galluccio-Loebl and Tesler proved, that for a graph embedded in an orientable surface of genus $g$ - the minimum number of handles of a surface into which $G$ embeds without edge crossings - the partition function is a linear combination of $4^g$ such Pfaffians. Cimasoni-Reshetikhin and Tesler interpreted the $4^g=2^{2g}$ terms as a sum over the spin structures of the surface, that is, the equivalence classes of quadratic forms on the homology group $H_1(\Sigma;\mathbb{Z}_2)$ distinguished by their Arf invariant (a $\mathbb{Z}_2$-valued invariant of a quadratic form), and extended the formula to non-orientable surfaces of crosscap number $\tilde g$ - a crosscap being an orientation-reversing feature, obtained by removing a disk and identifying opposite points of the boundary circle - where each crosscap contributes a twist; the two genera satisfy $\tilde g\le 2g+1$.

Within this framework Gobron established two things. First, recording Kasteleyn's classical theorem with an independent proof: a single-Pfaffian representation - by real or complex skew-symmetric matrices supported on the dart graph whose entries are constants times $x_e^{\pm 1}$ (edge entries) or constants (gadget entries) - exists if and only if $G$ is planar, so every non-planar graph needs at least two Pfaffians in identities without real-part extraction. Second, a single matrix over the multicomplex algebra $\mathbb{C}_{\tilde g}$ (a commutative algebra with $\tilde g$ independent generators squaring to $-1$) encodes $E_G$ as the real part of one Pfaffian - for $\tilde g=1$ the algebra $\mathbb{C}_1$ is just $\mathbb{C}$, so every graph of non-orientable genus $1$ is already represented by a single complex Pfaffian with real-part extraction - which expands to $2^{\tilde g}$ complex Pfaffians and, by further algebraic reduction, recovers the $4^g$ real ones. He noted that the number of terms remains exponential in the genus and stated that finding a sensible lower bound on it is an open problem.

A complexity-theoretic constraint frames any answer: by the Tutte-polynomial dichotomy of Jaeger-Vertigan-Welsh, exact evaluation of $Z_G$ on arbitrary graphs is #P-hard (the counting analogue of NP-hardness), while for every fixed genus it is polynomial-time via the $4^g$ formula; hence, unless FP=#P (that is, unless the counting problems of the class #P are all solvable in polynomial time), no representation by polynomially many Pfaffians with efficiently computable entries can hold for all graphs - a conditional statement that yields no unconditional bound depending on the genus. For the related problem of representing the perfect-matching polynomial itself (the dimer model), the analogous parameter - Norine's Pfaffian number $\mathrm{pf}(G)$, the least number of orientations whose real-weighted Pfaffians combine to the matching polynomial - received its first exponential lower bounds in the genus only in 2026. The Ising question studied here differs from that dimer question in two ways that matter: the polynomial is the even-subgraph polynomial, a specialization of the matching polynomial of the blow-up with all gadget weights fixed to $1$, and the matrices may carry arbitrary real or complex constants rather than only orientation signs.

Problem Statement

Let $G$ be a finite connected simple graph with real edge weights $w=(w_e)_{e\in E}$, let $E_G(w)=\sum_{H}\prod_{e\in H}w_e$ (the sum over all even subgraphs $H\subseteq E$, that is, subgraphs in which every vertex has even degree, the empty subgraph included) be its even-subgraph polynomial, equivalent to the Ising partition function by van der Waerden's identity, and let $D(G)$ be the dart graph of $G$, whose vertices are the incidences (darts) of $G$, whose gadget edges join the darts at each vertex, and which has one edge per edge of $G$ joining its two darts. Fix a reference perfect matching $M_0$ of $D(G)$, and let $c(w)=\prod_{e}w_e$, the product running over the edges $e$ of $G$ whose dart-graph edge belongs to $M_0$. Following Gobron's framework of weighted incidence matrices, consider identities valid for all weights $w$ with $w_e\neq 0$ for every $e$ (the source takes weights in the positive reals; since $c(w)\,\mathrm{Pf}(A^i(w))$ is polynomial in $w$, an identity for all nonzero weights and one for all positive weights are equivalent), of the form $E_G(w)=c(w)\sum_{i=1}^{k}\lambda_i\,\mathrm{Pf}(A^i(w))$, or the same identity with the real part of the right-hand side, where each $A^i(w)$ is obtained from a skew-symmetric matrix $A^i$ supported on the edges of $D(G)$ (zero entries elsewhere) with arbitrary real, respectively complex, constant entries, by multiplying the entry on the dart-graph edge corresponding to an edge $e$ of $G$ by $w_e^{-1}$ if that dart-graph edge lies in $M_0$ and by $w_e$ otherwise, leaving the gadget entries constant, and where the $\lambda_i$ are nonzero real, respectively complex, constants. Determine the minimum number $k$ of Pfaffians, as a function of $G$ - in particular of its orientable embedding genus $g$ and non-orientable genus $\tilde g$ - separately for real and for complex entries. Concrete targets: (1) any lower bound on $k$ growing with $g$ or $\tilde g$, beyond the known baseline - $k\ge 2$ for every non-planar $G$ in identities without real-part extraction, while with real-part extraction allowed the multicomplex construction with $\mathbb{C}_1=\mathbb{C}$ gives $k=1$ for every graph of non-orientable genus $1$, so no uniform $k\ge 2$ bound holds in that form; (2) whether the best known upper bounds - $4^g$ real Pfaffians and $2^{\tilde g}$ complex Pfaffians - can be asymptotically improved, for example made subexponential in the genus, in this class, or whether exponential genus-dependence is unavoidable here as it is in the orientation-admissible subclass (where the exact minimum is $4^g$ by Loebl-Masbaum) and for the perfect-matching polynomial (where the minimum is at least $(8/3)^g$ by Pant-Singh); (3) exact values of $k$ for natural graph families, such as complete graphs, or graphs of non-orientable genus 2 - for non-planar projective-planar graphs the complex-entry minimum is exactly 2 in identities without real-part extraction, and exactly 1 when real-part extraction is allowed. The mandatory core is target (1) - a nontrivial lower bound on $k$ growing with the genus - and a complete resolution of the task is achieved by settling it; targets (2) and (3) are optional supporting directions (a sharpness question about the known upper bounds, and illustrative computations on the named families, whose list is meant as examples rather than an exhaustive requirement).

References

1. Thierry Gobron, Graph theory and Pfaffian representations of Ising partition function, arXiv:1312.7289 (2013). https://arxiv.org/abs/1312.7289
2. P. W. Kasteleyn, Dimer statistics and phase transitions, Journal of Mathematical Physics 4 (1963) 287-293, doi:10.1063/1.1703953. https://doi.org/10.1063/1.1703953
3. Michael E. Fisher, On the dimer solution of planar Ising models, Journal of Mathematical Physics 7 (1966) 1776-1781, doi:10.1063/1.1704825. https://doi.org/10.1063/1.1704825
4. Anna Galluccio, Martin Loebl, On the theory of Pfaffian orientations. I. Perfect matchings and permanents, The Electronic Journal of Combinatorics 6 (1999) R6, doi:10.37236/1438. https://doi.org/10.37236/1438
5. Glenn Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory, Series B 78 (2000) 198-231, doi:10.1006/jctb.1999.1941. https://doi.org/10.1006/jctb.1999.1941
6. David Cimasoni, Nicolai Reshetikhin, Dimers on surface graphs and spin structures. I, Communications in Mathematical Physics 275 (2007) 187-208, doi:10.1007/s00220-007-0302-7. https://doi.org/10.1007/s00220-007-0302-7
7. David Cimasoni, Dimers on graphs in non-orientable surfaces, Letters in Mathematical Physics 87 (2009) 149-179, doi:10.1007/s11005-009-0299-2. https://doi.org/10.1007/s11005-009-0299-2
8. Serguei Norine, Drawing 4-Pfaffian graphs on the torus, Combinatorica 29 (2009) 109-119, doi:10.1007/s00493-009-2354-0. https://doi.org/10.1007/s00493-009-2354-0
9. Martin Loebl, Gregor Masbaum, On the optimality of the Arf invariant formula for graph polynomials, Advances in Mathematics 226 (2011) 332-349, doi:10.1016/j.aim.2010.06.021; arXiv:0908.2925. https://arxiv.org/abs/0908.2925
10. F. Jaeger, D. L. Vertigan, D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Mathematical Proceedings of the Cambridge Philosophical Society 108 (1990) 35-53, doi:10.1017/s0305004100068936. https://doi.org/10.1017/s0305004100068936
11. Anh Minh Pham, A Pfaffian formula for the Ising partition function of surface graphs, Journal of Statistical Mechanics: Theory and Experiment (2020) 083103, doi:10.1088/1742-5468/aba1e4; arXiv:2003.02967. https://arxiv.org/abs/2003.02967
12. M. N. Vyalyi, Counting the Number of Perfect Matchings, and Generalized Decision Trees, Problems of Information Transmission 57 (2021) 143-160, doi:10.1134/S0032946021020046. https://doi.org/10.1134/S0032946021020046
13. Anh Minh Pham, A Kac-Ward formula for the Ising partition function of surface graphs, Indian Journal of Pure and Applied Mathematics (2025), doi:10.1007/s13226-025-00902-6. https://doi.org/10.1007/s13226-025-00902-6
14. Enrique Junchaya, Alberto Alexandre Assis Miranda, Claudio L. Lucchesi, Lower bounds for the Pfaffian number of graphs, Leibniz International Proceedings in Informatics (LIPIcs), Volume 376 (WG 2026), Article 28, doi:10.4230/LIPIcs.WG.2026.28. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.28 ; preprint arXiv:2603.00334. https://arxiv.org/abs/2603.00334
15. Priyanshu Pant, Ranveer Singh, Exponential lower bounds for the Pfaffian number of graphs, arXiv:2605.21077 (2026). https://arxiv.org/abs/2605.21077