Perfect matchings and perfect powers. (English) Zbl 1020.05052

Ciucu, Mihai

J. Algebr. Comb. 17, No. 3, 335-375 (2003).

Summary: 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. Algebr. Comb. 1, 111-132 (1992; Zbl 0779.05009); B.-Y. Yang, Three enumeration problems concerning Aztec diamonds, Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA, 1991; J. Propp, Enumeration of matchnings: Problems and progress, in: New perspectives in algebraic combinatorics, Cambridge University Press, Math. Sci. Res. Inst. Publ. 38, 255-291 (1999; Zbl 0937.05065)]. 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.

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05A15	Exact enumeration problems, generating functions
05B45	Combinatorial aspects of tessellation and tiling problems

Keywords:

perfect matchings; tilings; exact enumeration

Citations:

Zbl 0779.05009; Zbl 0937.05065

References:

[1]	M. Ciucu, “Enumeration of perfect matchings in graphs with reflective symmetry,” J. Combin. Theory Ser. A77 (1997), 67-97. · Zbl 0867.05055
[2]	M. Ciucu, “A complementation theorem for perfect matchings of graphs having a cellular completion,” J. Combin. Theory Ser. A81 (1998), 34-68. · Zbl 0897.05063
[3]	M. Ciucu and C. Krattenthaler, “Enumeration of lozenge tilings of hexagons with cut off corners,” J. Combin. Theory Ser. A100 (2002), 201-231. · Zbl 1015.05006
[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/ 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. · Zbl 0779.05009
[6]	G. Kuperberg, “Symmetries of plane partitions and the permanent-determinant method,” J. Combin. Theory Ser. A68 (1994), 115-151. · Zbl 0819.05007
[7]	P.A. MacMahon, Combinatory Analysis, Cambridge, 1916, reprinted by Chelsea, New York, 1960, Vols. 1/2. · JFM 46.0118.07
[8]	J. Propp, “Enumeration of matchings: Problems and progress,” NewPerspectives in Geometric Combinatorics, edited by Billera et al., Cambridge University Press, 1999. · Zbl 0937.05065
[9]	J. Propp, “Generalized domino-shuffling,” Theoretical Computer Science to appear in special issue on tilings. · Zbl 1052.68095
[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.