Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole
Mihai Ciucu
Indiana University Department of Mathematics Bloomington IN 47405 USA
DOI: 10.1007/s10801-007-0099-7
Abstract
We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD n - 1 of order n - 1 with the path P n (2) on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P( G n )=P( P n (2))[P( QAD n - 1)] 2. On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid-i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds.
We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases-graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls.
Pages: 493–538
Keywords: keywords perfect matchings; domino tilings; spanning trees; similar matrices; exact enumeration; product formulas; symmetry classes
Full Text: PDF
References
1. Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge University Press, Cambridge (1993)
2. Ciucu, M.: Enumeration of perfect matchings in graphs with reflective symmetry. J. Comb. Theory Ser. A 77, 67-97 (1997)
3. Ciucu, M.: Enumeration of spanning trees of the quartered Aztec diamond. In: Special Session on Combinatorics and Enumerative Geometry, AMS Meeting #931, University of Louisville, Louisville, KY, March 21, 1998 (Abstract Issue: 19/2)
4. Cvetković, D., Doob, M., Gutman, I., Torgašev, A.: Recent results in the theory of graph spectra. Ann. Discret. Math. 36 (1988)
5. Kenyon, R.W., Propp, J.G., Wilson, D.B.: Trees and matchings. Electron. J. Comb. 7 (2000). Research Paper 25, 34 pp
6. Knuth, D.E.: Aztec diamonds, checkerboard graphs, and spanning trees. J. Algebr. Comb. 6, 253-257 (1997)
7. Kreweras, G.: Complexité et circuits eulériens dans les sommes tensorielles de graphes. J. Comb.
2. Ciucu, M.: Enumeration of perfect matchings in graphs with reflective symmetry. J. Comb. Theory Ser. A 77, 67-97 (1997)
3. Ciucu, M.: Enumeration of spanning trees of the quartered Aztec diamond. In: Special Session on Combinatorics and Enumerative Geometry, AMS Meeting #931, University of Louisville, Louisville, KY, March 21, 1998 (Abstract Issue: 19/2)
4. Cvetković, D., Doob, M., Gutman, I., Torgašev, A.: Recent results in the theory of graph spectra. Ann. Discret. Math. 36 (1988)
5. Kenyon, R.W., Propp, J.G., Wilson, D.B.: Trees and matchings. Electron. J. Comb. 7 (2000). Research Paper 25, 34 pp
6. Knuth, D.E.: Aztec diamonds, checkerboard graphs, and spanning trees. J. Algebr. Comb. 6, 253-257 (1997)
7. Kreweras, G.: Complexité et circuits eulériens dans les sommes tensorielles de graphes. J. Comb.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition