This material has been published in Journal of Combinatorial Theory, Series B (volume 78 (2000), pages 198-231), the only definitive repository of the content that has been certified and accepted after peer review. Copyright and all rights therein are retained by Academic Press. This material may not be copied or reposted without explicit permission.

Authorized users may also access this article via IDEAL (the International Digital Electronic Access Library) at http://www.idealibrary.com or http://www.europe.idealibrary.com.


Glenn Tesler,
Matchings in Graphs on Non-orientable Surfaces,
Journal of Combinatorial Theory, Series B, 78 (2000), 198-231.

Download Postscript (454K)  PDF (393K)    Go to the publisher's site for this article (authorized users only).


Abstract

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 4g 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 22-\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 22g+1 (respectively, 22g+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 x n grid on a Möbius strip.

There is also an earlier 1992 writeup of this by the author that may be of interest, that was posted (1 May 1996) in the "domino" electronic mailing list archives, 96a. Contact propp@math.wisc.edu for access.