A Complementation Theorem for Perfect Matchings of Graphs Having a Cellular Completion

A cellular graph is a graph whose edges can be partitioned into 4-cycles (called cells) so that each vertex is contained in at most two cells. We present a “Complementation Theorem” for the number of matchings of certain subgraphs of cellular graphs. This generalizes the main result of M. Ciucu (J. Algebraic Combin.5(1996), 87–103). As applications of the Complementation Theorem we obtain a new proof of Stanleyʹs multivariate version of the Aztec diamond theorem, a weighted generalization of a result of Knuth (J. Algebraic Combin.6(1997), 253–257) concerning spanning trees of Aztec diamond graphs, a combinatorial proof of Yangʹs enumeration (“Three Enumeration Problems Concerning Aztec Diamonds,” Ph.D. thesis, M.I.T., 1991) of matchings of fortress graphs and direct proofs for certain identities of Jockusch and Propp.