Matchings in graphs on non-orientable surfaces (Q1569077)

P. W. Kasteleyn stated that the number of perfect matchings in a graph embedding on a surface of genus \(g\) is given by a linear combination of \(4^g\) Pfaffians of modified adjacency matrices of the graph, but didn't actually give the matrices or the linear combination. We generalize this to enumerating the perfect matchings of a graph embedding on an arbitrary compact boundaryless 2-manifold \(S\) with a linear combination of \(2^{2-\chi(S)}\) Pfaffians. Our explicit construction proves Kasteleyn's assertion, and additionally treats graphs embedding on non-orientable surfaces. If a graph embeds on the connected sum of a genus \(g\) surface with a projective plane (respectively, Klein bottle), the number of perfect matchings can be computed as a linear combination of \(2^{2g+1}\) (respectively, \(2^{2g+2}\)) Pfaffians. We also introduce ``crossing orientations,'' the analogue of Kasteleyn's ``admissible orientations'' in our context, describing how the Pfaffian of a signed adjacency matrix of a graph gives the sign of each perfect matching according to the number of edge-crossings in the matching. Finally, we count the perfect matchings of an \(m\times n\) grid on a Möbius strip.