Extending det-easy planar graphical models beyond the binary planar case: q-ary alphabets, surface graphs of nonzero genus, k-Pfaffian graphs, and variational WBG approximation

Chernyak and Chertkov (arXiv:0902.0320; J. Stat. Mech. 2010 P11007) identified a broad class of binary-variable statistical models on planar graphs — Wick binary graph (WBG) models, equivalent to Gaussian Grassmann (free-fermion) models — whose partition functions reduce to a single Pfaffian, and posed five open directions: (1) characterize det-easy planar graphical models over q-ary alphabets with $q > 2$ and the gauge transformations reducing them to binary WBG/dimer Pfaffian evaluations; (2) build variational approximations of hard planar and non-planar models on the hierarchy of easy planar models, with controlled perturbative corrections; (3) extend the WBG/Grassmann formalism to surface graphs of nonzero genus with an explicit account of the $2^{2g}$ spinor-structure (Kasteleyn-class) Pfaffian decomposition; (4) analyze Wick Gaussian models on non-planar Pfaffian- or k-Pfaffian-orientable graphs; (5) formulate and solve the variational principle selecting the best WBG approximation of a general edge-binary graphical model. Of these, the dimer and Ising cores of the genus direction are classical (Galluccio-Loebl, Tesler, Cimasoni-Reshetikhin, Cimasoni's generalized Kac-Ward formula); the q-ary characterization (only homomorphism-type dichotomies and holographic basis-collapse constraints are known), the k-Pfaffian characterization (Pfaffian recognition for general graphs unresolved; 2026 results prove Pfaffian numbers unbounded and exponentially large), and the variational WBG projection remain open.

Background

A graphical model assigns weights to local configurations of variables placed on the vertices and edges of a graph; its partition function — the sum of all configuration weights — is the basic object of equilibrium statistical mechanics and of exact probabilistic inference. Computing it exactly is in general #P-hard (the counting analogue of NP-hardness), and already so for Ising spin models on general non-planar graphs, as Barahona showed in 1982. The celebrated exception is planarity. A dimer (perfect-matching) model on a planar graph, and likewise the planar Ising model, has a partition function equal to a Pfaffian — the square root of the determinant of a skew-symmetric matrix, computable in polynomial time — provided the edges are oriented so that every face boundary carries an odd number of clockwise-oriented edges. Such an orientation is called a Kasteleyn orientation; Kasteleyn-type orientations exist on graphs embedded in arbitrary surfaces, but a single such orientation yielding a one-Pfaffian evaluation is the planar special case. In modern language these solvable models are free-fermion models, because the Pfaffian identity is Wick's theorem for Gaussian integrals over Grassmann (anticommuting) variables.

Chernyak and Chertkov (2010) unified and extended this planar solvability. They work with edge-binary graphical (EBG) models — models whose binary variables sit on the directed half-edges of a planar graph — and single out the Wick binary graph (WBG) models, in which the weight of every even-degree vertex is built from the incident edge weights by Wick's pairing rules, with signs tracking crossings of the paired half-edges. Their central theorem (Theorem II.7) states that a model is a WBG model if and only if it is gauge-equivalent to a Gaussian Grassmann model (which they call a VG3 model) on the same graph; consequently the partition function equals the Pfaffian of a matrix of size twice the number of edges. Gauge transformations are invertible linear reparametrizations of local configuration spaces that leave the partition function invariant; they are also the mechanism behind Valiant's holographic algorithms, which solve seemingly intractable counting problems by linearly transforming them into planar perfect-matching counts computed by matchgates (gadgets whose weighted matchings encode local constraints). Chernyak and Chertkov show that the dimer models underlying holographic algorithms are exactly gauge-equivalent WBG models, and illustrate the formalism on Valiant's #X-matching problem, a 3-ary edge model reduced to a dimer computation. Models reducible to Pfaffian or determinant evaluation in polynomial time are called det-easy.

Three bodies of knowledge delimit what is known beyond the plane. First, on a graph embedded in an orientable surface of genus $g$ (a sphere with $g$ handles), single Kasteleyn orientations no longer suffice: the dimer partition function becomes an alternating sum of at most $4^g$ Pfaffians indexed by the $2^{2g}$ spin structures on the surface — the equivalence classes of Kasteleyn-type orientations (Galluccio and Loebl 1999; Tesler 2000; the coefficients computed via discrete spin structures by Cimasoni and Reshetikhin 2007-2008; and Cimasoni's 2010 generalized Kac-Ward formula — the Kac-Ward formula being a determinant expression for the Ising partition function of a graph — gives the corresponding statement for the Ising model). Second, in graph theory a graph is called Pfaffian if one orientation makes every relevant even cycle oddly oriented so that the perfect-matching generating polynomial is a single Pfaffian; recognition is polynomial for bipartite and near-bipartite graphs but unresolved for general graphs, and a graph is k-Pfaffian if its perfect-matching polynomial is a linear combination of k Pfaffians, the minimum such k being its Pfaffian number. Recent 2026 work proves Pfaffian numbers are unbounded and in fact can grow exponentially in the number of vertices. Third, algorithmically, exact planar inference for binary models is practical (Schraudolph and Kamenetsky 2008; Karandashev and Malsagov 2016), and loop-calculus methods — exact expansions of the partition function as a sum over loops of the graph, whose truncations yield systematic approximations — provide practical approximations (Gómez, Kappen and Chertkov 2009); but no variational principle projecting a general hard model onto the WBG class is known. The unresolved target is how far the det-easy class extends beyond planar binary models — to larger alphabets, higher genus, and non-planar Pfaffian-orientable graphs — and how to use the easy class as an approximation basis for hard models.

Problem Statement

The common objective, as posed in Section VI of Chernyak and Chertkov (2010), is to extend the det-easy (Pfaffian/free-fermion) tractability class of planar binary graphical models beyond its original setting, along the following directions:

(1) q-ary alphabets: determine and characterize broad classes of det-easy planar graphical models defined over alphabets of size $q > 2$, and identify which q-ary local gauge transformations permit reductions to binary WBG/dimer Pfaffian evaluations (the paper's Subsection V.E exhibits one such class: a 3-ary formulation of #X-matching reduced to a dimer model).

(2) Variational approximation: use the hierarchy of easy planar (WBG-based) models as a basis for efficient variational approximation of planar — and possibly non-planar — models that are hard, and then, on the next level, build controlled perturbative corrections to the variational result.

(3) Surface graphs: extend the WBG/VG3 (Gaussian Grassmann) correspondence to graphs embedded in surfaces of nonzero genus $g$, giving an explicit account of the $2^{2g}$ spinor-structure (Kasteleyn-class) contributions and their Pfaffian decomposition, including the claim that Kasteleyn orientations on the extended graph generate all $2^{2g}$ spinor structures on the embedding surface. The underlying $2^{2g}$-Pfaffian decomposition for dimer and Ising models being classical (Galluccio-Loebl, Tesler, Cimasoni-Reshetikhin), the open content is the formulation for general Wick Gaussian models with arbitrary Wick vertex weights.

(4) Non-planar Pfaffian orientability: characterize and analyze Wick Gaussian models on non-planar graphs that are Pfaffian-orientable or k-Pfaffian-orientable (any dimer model on a genus-$g$ surface graph being $2^{2g}$-Pfaffian orientable), determining how the present Grassmann/gauge techniques generalize to such settings.

(5) Variational projection of general EBG models: for a general edge-binary graphical model, formulate and solve the statistical variational principle that selects the best approximating WBG model, and devise efficient methods to account for the corrections.

The five directions are facets of one objective rather than independently sufficient sub-problems. Directions (2) and (5) are two levels of one variational program — (2) builds the approximation basis and its perturbative corrections, (5) formulates the selection principle and the correction accounting.

A complete answer would delineate which graphical models beyond the planar binary setting admit polynomial-time exact evaluation via Pfaffian/determinant reductions — across alphabet size, genus, and Pfaffian-orientability of the underlying graph — and would supply the corresponding approximation methodology, built on the easy-model hierarchy, for models outside the class.

References

1. V. Y. Chernyak and M. Chertkov, Planar Graphical Models which are Easy, Journal of Statistical Mechanics (2010) P11007, DOI 10.1088/1742-5468/2010/11/P11007, https://doi.org/10.1088/1742-5468/2010/11/P11007 (arXiv:0902.0320)
2. L. G. Valiant, Holographic algorithms, SIAM Journal on Computing 37 (2008) 1565-1594, DOI 10.1137/070682575, https://doi.org/10.1137/070682575
3. F. Barahona, On the computational complexity of Ising spin glass models, Journal of Physics A: Mathematical and General 15 (1982) 3241-3253, DOI 10.1088/0305-4470/15/10/028, https://doi.org/10.1088/0305-4470/15/10/028
4. 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
5. A. Galluccio and M. Loebl, On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents, Electronic Journal of Combinatorics 6(1) (1999) Research Paper R6, DOI 10.37236/1438, https://doi.org/10.37236/1438
6. G. 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
7. D. Cimasoni and N. 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 (arXiv:math-ph/0608070)
8. D. Cimasoni and N. Reshetikhin, Dimers on surface graphs and spin structures. II, Communications in Mathematical Physics 281 (2008) 445-468, DOI 10.1007/s00220-008-0488-3, https://doi.org/10.1007/s00220-008-0488-3 (arXiv:0704.0273)
9. D. Cimasoni, A generalized Kac-Ward formula, Journal of Statistical Mechanics (2010) P07023, DOI 10.1088/1742-5468/2010/07/P07023, https://doi.org/10.1088/1742-5468/2010/07/P07023, arXiv:1004.3158, https://arxiv.org/abs/1004.3158
10. D. 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, arXiv:0804.4772, https://arxiv.org/abs/0804.4772
11. R. Thomas, A survey of Pfaffian orientations of graphs, Proceedings of the International Congress of Mathematicians, Madrid 2006, Vol. III, European Mathematical Society, 2006, pp. 963-984, DOI 10.4171/022-3/47, https://doi.org/10.4171/022-3/47
12. S. Norine and R. Thomas, Minimally non-Pfaffian graphs, Journal of Combinatorial Theory, Series B 98 (2008) 1038-1055, DOI 10.1016/j.jctb.2007.12.005, https://doi.org/10.1016/j.jctb.2007.12.005
13. A. A. A. Miranda and C. L. Lucchesi, Recognizing near-bipartite Pfaffian graphs in polynomial time, Discrete Applied Mathematics 158 (2010) 1275-1278, DOI 10.1016/j.dam.2009.01.008, https://doi.org/10.1016/j.dam.2009.01.008
14. S. 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
15. A. A. A. Miranda and C. L. Lucchesi, On the Pfaffian number of graphs, Electronic Notes in Discrete Mathematics 35 (2009) 145-150, DOI 10.1016/j.endm.2009.11.025, https://doi.org/10.1016/j.endm.2009.11.025
16. E. Junchaya, A. A. A. Miranda and C. L. Lucchesi, Lower Bounds for the Pfaffian Number of Graphs, arXiv:2603.00334 (2026), https://arxiv.org/abs/2603.00334
17. P. Pant and R. Singh, Exponential Lower Bounds for the Pfaffian Number of Graphs, arXiv:2605.21077 (2026), https://arxiv.org/abs/2605.21077
18. M. Gorsky and C. Kuske, On non-planar, cycle-conformal graphs, arXiv:2602.07331 (2026), https://arxiv.org/abs/2602.07331
19. J.-Y. Cai and Z. Fu, A Collapse Theorem for Holographic Algorithms with Matchgates on Domain Size at Most 4, arXiv:1305.1409 (2013), https://arxiv.org/abs/1305.1409
20. S. Chen, Basis Collapse for Holographic Algorithms Over All Domain Sizes, arXiv:1511.00778 (2015), https://arxiv.org/abs/1511.00778
21. Z. Fu and J.-Y. Cai, Holographic Algorithms on Domains of General Size, Theory of Computing Systems 67 (2022) 417-436, DOI 10.1007/s00224-022-10088-7, https://doi.org/10.1007/s00224-022-10088-7
22. J.-Y. Cai and A. Maran, The complexity of counting planar graph homomorphisms of domain size 3, arXiv:2302.08570 (2023), https://arxiv.org/abs/2302.08570
23. V. Gómez, H. J. Kappen and M. Chertkov, Approximate inference on planar graphs using Loop Calculus and Belief Propagation, Proceedings of the 25th Conference on Uncertainty in Artificial Intelligence (UAI 2009), arXiv:0901.0786, https://arxiv.org/abs/0901.0786
24. N. N. Schraudolph and D. Kamenetsky, Efficient Exact Inference in Planar Ising Models, arXiv:0810.4401 (2008), https://arxiv.org/abs/0810.4401
25. Y. M. Karandashev and M. Yu. Malsagov, Polynomial algorithm for exact calculation of partition function for binary spin model on planar graphs, arXiv:1611.00922 (2016), https://arxiv.org/abs/1611.00922
26. M. Chertkov, V. Chernyak and Y. Maximov, Gauges, Loops, and Polynomials for Partition Functions of Graphical Models, arXiv:1811.04713 (2018), https://arxiv.org/abs/1811.04713
27. T. Gobron, Graph theory and Pfaffian representations of Ising partition function, arXiv:1312.7289 (2013), https://arxiv.org/abs/1312.7289
28. A. M. Pham, A Pfaffian formula for the monomer-dimer model on surface graphs, arXiv:1705.00992 (2017), https://arxiv.org/abs/1705.00992