Perfect Matchings of Cellular Graphs |
| |
Authors: | Mihai Ciucu |
| |
Institution: | (1) Department of Mathematics, University of Michigan, Ann Arbor, MI, 48109-1003 |
| |
Abstract: | We introduce a family of graphs, called cellular, and consider the problem of enumerating their perfect matchings. We prove that the number of perfect matchings of a cellular graph equals a power of 2 times the number of perfect matchings of a certain subgraph, called the core of the graph. This yields, as a special case, a new proof of the fact that the Aztec diamond graph of order n introduced by Elkies, Kuperberg, Larsen and Propp has exactly 2
n(n+1)/2 perfect matchings. As further applications, we prove a recurrence for the number of perfect matchings of certain cellular graphs indexed by partitions, and we enumerate the perfect matchings of two other families of graphs called Aztec rectangles and Aztec triangles. |
| |
Keywords: | perfect matching alternating sign pattern Ferrers diagram |
本文献已被 SpringerLink 等数据库收录! |
|