Graphical condensation for enumerating perfect matchings

DOI10.1016/j.jcta.2004.10.005zbMath1059.05087OpenAlexW1978581879MaRDI 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 diamondPerfect matchingSymmetric graphGraphical condensationPlane partition

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (18)

Tiling enumeration of hexagons with off-central holes ⋮ A \(q\)-enumeration of lozenge tilings of a hexagon with four adjacent triangles removed from the boundary ⋮ Proof of a conjecture of Kenyon and Wilson on semicontiguous minors ⋮ A new simple proof of the Aztec diamond theorem ⋮ A quadratic identity for the number of perfect matchings of plane graphs ⋮ Replacing Pfaffians and applications ⋮ A \(q\)-enumeration of lozenge tilings of a hexagon with three dents ⋮ 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 ⋮ Perfect matchings on a type of lattices with toroidal boundary ⋮ The characteristic polynomial and the matchings polynomial of a weighted oriented graph ⋮ On the rank of a real skew symmetric matrix described by an 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 ⋮ 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 ⋮ Graphical condensation of plane graphs: a combinatorial approach

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Graphical condensation for enumerating perfect matchings