Matchings in graphs on nonoriented surfaces
Glenn P Tesler
Univeristy of California, San Diego
March 12,
4:15pm
refreshments at 3:45pm
2338
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 nonorientable 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 2manifolds.
As an application, we count the perfect matchings in an $m\times n$
grid on a M\"obius strip.

Speaker's Contact Info: gptesler(atsign)euclid.ucsd.edu
Return to seminar home page
Page loaded on January 28, 1999 at 11:40 AM.

Copyright © 199899, Sara C. Billey.
All rights reserved.

