Mathematics – Combinatorics
Scientific paper
2005-01-28
J. Algebraic Combin. 17 (2003), 335-375
Mathematics
Combinatorics
Corrected journal reference
Scientific paper
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. 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.
No associations
LandOfFree
Perfect matchings and perfect powers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Perfect matchings and perfect powers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Perfect matchings and perfect powers will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-392081