Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1405497 (Why is no real title available?)
- A complementation theorem for perfect matchings of graphs having a cellular completion
- Alternating-sign matrices and domino tilings. I
- Enumeration of Lozenge tilings of hexagons with cut-off corners
- Enumeration of perfect matchings in graphs with reflective symmetry
- Generalized domino-shuffling.
- Symmetries of plane partitions and the permanent-determinant method
Cited in
(20)- Proof of Blum's conjecture on hexagonal dungeons
- The Schwarzian octahedron recurrence (dSKP equation) I: explicit solutions
- On the dimer problem of the vertex-edge graph of a cubic graph
- Enumeration of hybrid domino-lozenge tilings. III: centrally symmetric tilings
- Enumeration of hybrid domino-lozenge tilings. II: Quasi-octagonal regions
- New aspects of regions whose tilings are enumerated by perfect powers
- Solutions to the T-systems with principal coefficients
- Perfect matchings and applications
- Channels, billiards, and perfect matching 2-divisibility
- Enumeration of hybrid domino-lozenge tilings
- A note on divisibility of the number of matchings of a family of graphs
- A generalization of Aztec dragons
- Domino tilings of Aztec diamonds and squares
- Perfect matchings and the octahedron recurrence
- Beyond Aztec castles: toric cascades in the dP₃ quiver
- Dungeons and dragons: combinatorics for the \(dP_3\) quiver
- Counting tilings by taking walks
- Perfect matchings of trimmed Aztec rectangles
- Perfect matching and polymatroids
- Proof of a refinement of Blum's conjecture on hexagonal dungeons
This page was built for publication: Perfect matchings and perfect powers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1408261)
