JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 17, No 3 (2003)

Mihai Ciucu

In the last decade there have been many results about special families of graphs whose number of perfect matchings is given by perfect or near perfect powers (N. Elkies et al., J. Algebraic Combin. 1 (1992), 111-132; B.-Y. Yang, Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA, 1991; J. Propp, New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999). In this paper we present an approach that allows proving them in a unified way. We use this approach to prove a conjecture of James Propp stating that the number of tilings of the so-called Aztec dungeon regions is a power (or twice a power) of 13. We also prove a conjecture of Matt Blum stating that the number of perfect matchings of a certain family of subgraphs of the square lattice is a power of 3 or twice a power of 3. In addition we obtain multi-parameter generalizations of previously known results, and new multi-parameter exact enumeration results. We obtain in particular a simple combinatorial proof of Bo-Yin Yang”s multivariate generalization of fortresses, a result whose previously known proof was quite complicated, amounting to evaluation of the Kasteleyn matrix by explicit row reduction. We also include a new multivariate exact enumeration of Aztec diamonds, in the spirit of Stanley”s multivariate version.

1. M. Ciucu, “Enumeration of perfect matchings in graphs with reflective symmetry,” J. Combin. Theory Ser. A 77 (1997), 67-97.
2. M. Ciucu, “A complementation theorem for perfect matchings of graphs having a cellular completion,” J. Combin. Theory Ser. A 81 (1998), 34-68.
3. M. Ciucu and C. Krattenthaler, “Enumeration of lozenge tilings of hexagons with cut off corners,” J. Combin. Theory Ser. A 100 (2002), 201-231.
4. C. Douglas, “An illustrative study of the enumeration of tilings: Conjecture discovery and proof techniques,” Electronic manuscript dated August 1996 (available at the time of submission at www.math.wisc.edu/\sim propp/tiling/www/douglas.ps).
5. N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, “Alternating-sign matrices and domino tilings (Part I),” J. Algebraic Combin. 1 (1992), 111-132.
6. G. Kuperberg, “Symmetries of plane partitions and the permanent-determinant method,” J. Combin. Theory Ser. A 68 (1994), 115-151.
7. P.A. MacMahon, Combinatory Analysis, Cambridge, 1916, reprinted by Chelsea, New York, 1960, Vols. 1/2.
8. J. Propp, “Enumeration of matchings: Problems and progress,” New Perspectives in Geometric Combinatorics, edited by Billera et al., Cambridge University Press, 1999.
9. J. Propp, “Generalized domino-shuffling,” Theoretical Computer Science to appear in special issue on tilings.
10. R.P. Stanley, Private communication.
11. B.-Y. Yang, “Three enumeration problems concerning Aztec diamonds,” Ph.D. thesis, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA, 1991.