A Complementation Theorem for Perfect Matchings of Graphs Having a Cellular Completion
✍ Scribed by Mihai Ciucu
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 589 KB
- Volume
- 81
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
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.