Perfect Matchings of Cellular Graphs
Mihai Ciucu
DOI: 10.1023/A:1022408900061
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.
Pages: 87–103
Keywords: perfect matching; alternating sign pattern; ferrers diagram
Full Text: PDF
References
1. H.S.M. Coxeter, Regular Poly topes, Methuen & Co. Ltd., London, pp. 69-70, 1948.
2. N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, "Alternating-sign matrices and domino tilings (Part I)," J Alg. Combin. 1 (1992), 111-132.
3. P.W. Kasteleyn, "The statistics of dimers on a lattice, I: the number of dimer arrangements on a quadratic lattice," Physica 27 (1961), 1209-1255.
4. W.H. Mills, D.P. Robbins, and H. Rumsey Jr., "Alternating sign matrices and descending plane partitions," J. Combin. Theory Ser. A 34 (1983), 340-359.
5. D. Randall, Private Communication.
6. D.P. Robbins and H. Rumsey Jr., "Determinants and alternating sign matrices," Adv. Math. 62 (1986), 169- 184.
7. H. Sachs and H. Zemitz, "Remark on the dimer problem," Discrete Appl. Math. 51 (1994), 171-179.
8. L.W. Shapiro and A.B. Stephens, "Bootstrap percolation, the Schroder numbers, and the W-kings problem," SIAMJ. Discrete Math. 4 (1991), 275-280.
9. E. Schroder, "Vier combinatorische probleme," Zeitschrifljur Mathematik and Physik 15 (1870), 361-376.
2. N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, "Alternating-sign matrices and domino tilings (Part I)," J Alg. Combin. 1 (1992), 111-132.
3. P.W. Kasteleyn, "The statistics of dimers on a lattice, I: the number of dimer arrangements on a quadratic lattice," Physica 27 (1961), 1209-1255.
4. W.H. Mills, D.P. Robbins, and H. Rumsey Jr., "Alternating sign matrices and descending plane partitions," J. Combin. Theory Ser. A 34 (1983), 340-359.
5. D. Randall, Private Communication.
6. D.P. Robbins and H. Rumsey Jr., "Determinants and alternating sign matrices," Adv. Math. 62 (1986), 169- 184.
7. H. Sachs and H. Zemitz, "Remark on the dimer problem," Discrete Appl. Math. 51 (1994), 171-179.
8. L.W. Shapiro and A.B. Stephens, "Bootstrap percolation, the Schroder numbers, and the W-kings problem," SIAMJ. Discrete Math. 4 (1991), 275-280.
9. E. Schroder, "Vier combinatorische probleme," Zeitschrifljur Mathematik and Physik 15 (1870), 361-376.