Graphical condensation for enumerating perfect matchings

DOI10.1016/j.jcta.2004.10.005zbMath1059.05087MaRDI QIDQ1775549

Weigen Yan, Fu Ji Zhang

Publication date: 4 May 2005

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcta.2004.10.005

zbMATH Keywords

Aztec diamond; Perfect matching; Symmetric graph; Graphical condensation; Plane partition

Mathematics Subject Classification ID

05A15: Exact enumeration problems, generating functions

05A18: Partitions of sets

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Related Items

On the rank of a real skew symmetric matrix described by an oriented graph, A \(q\)-enumeration of lozenge tilings of a hexagon with three dents, The characteristic polynomial and the matchings polynomial of a weighted oriented graph, Proof of a refinement of Blum's conjecture on hexagonal dungeons, Maximum matchings in scale-free networks with identical degree distribution, Generalizing the divisibility property of rectangle domino tilings, Graphical condensation of plane graphs: a combinatorial approach, Proof of a conjecture of Kenyon and Wilson on semicontiguous minors, Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs, Beyond Aztec castles: toric cascades in the \(dP_3\) quiver, Tiling enumeration of hexagons with off-central holes, Lozenge tilings of hexagons with central holes and dents, Proof of two conjectures of Ciucu and Krattenthaler on the enumeration of lozenge tilings of hexagons with cut off corners, A \(q\)-enumeration of lozenge tilings of a hexagon with four adjacent triangles removed from the boundary, A quadratic identity for the number of perfect matchings of plane graphs, Replacing Pfaffians and applications, Perfect matchings on a type of lattices with toroidal boundary, A new simple proof of the Aztec diamond theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Applications of graphical condensation for enumerating matchings and tilings
• Alternating-sign matrices and domino tilings. I
• Dodgon's determinant-evaluation rule proved by TWO-TIMING MEN and WOMEN
• A complementation theorem for perfect matchings of graphs having a cellular completion
• Generalized domino-shuffling.
• Perfect matchings of cellular graphs
• Enumeration of perfect matchings in graphs with reflective symmetry