Perfect matchings and perfect powers

DOI10.1023/A:1025005023573zbMATH Open1020.05052arXivmath/0501521OpenAlexW1695430876MaRDI QIDQ1408261FDOQ1408261

Authors: Mihai Ciucu 

Publication date: 15 September 2003

Published in: Journal of Algebraic Combinatorics (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0501521

Recommendations

• Perfect matchings of trimmed Aztec rectangles
• Perfect matchings and applications
• scientific article; zbMATH DE number 1405497
• Graphical condensation for enumerating perfect matchings
• Perfect matchings and perfect squares

zbMATH Keywords

perfect matchingsexact enumerationtilings

Mathematics Subject Classification ID

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

Cites Work

• Alternating-sign matrices and domino tilings. I
• Generalized domino-shuffling.
• Enumeration of perfect matchings in graphs with reflective symmetry
• Title not available (Why is that?)
• Symmetries of plane partitions and the permanent-determinant method
• A complementation theorem for perfect matchings of graphs having a cellular completion
• Enumeration of Lozenge tilings of hexagons with cut-off corners

Cited In (20)

• The Schwarzian octahedron recurrence (dSKP equation) I: explicit solutions
• On the dimer problem of the vertex-edge graph of a cubic graph
• Proof of Blum's conjecture on hexagonal dungeons
• 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_3\) 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)