Matchings in graphs on non-oriented surfaces

ABSTRACT

P.W. Kasteleyn gave an algorithm to count the perfect matchings in a planar graph and a graph on a torus using Pfaffians (similar to determinants) of a modified adjacency matrix of the graph. He stated that perfect matchings in a graph embedding on a $g$-holed torus could be enumerated by a linear combination of $4^g$ Pfaffians of differently modified adjacency matrices, but did not give the complete construction. We give an explicit construction that not only does this, but also does it for graphs embedding on non-orientable surfaces. If a graph embeds on the connected sum of a $g$-holed torus with a projective plane (respectively, Klein bottle), the number of perfect matchings can be computed by a linear combination of $2^{2g+1}$ (respectively, $2^{2g+2}$) Pfaffians. Together with the $g$-holed torus, these comprise all the compact boundaryless 2-manifolds. As an application, we count the perfect matchings in an $m\times n$ grid on a M\"obius strip.

Speaker's Contact Info: gptesler(at-sign)euclid.ucsd.edu