Graphical condensation, overlapping Pfaffians and superpositions of matchings

zbMATH Open1215.05131arXiv0906.4236MaRDI QIDQ976742FDOQ976742

Authors: Markus Fulmek 

Publication date: 16 June 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The purpose of this note is to exhibit clearly how the "graphical condensation" identities of Kuo, Yan, Yeh and Zhang follow from classical Pfaffian identities by the Kasteleyn-Percus method for the enumeration of matchings. Knuth termed the relevant identities "overlapping Pfaffian" identities and the key concept of proof "superpositions of matchings". In our uniform presentation of the material, we also give an apparently unpublished general "overlapping Pfaffian" identity of Krattenthaler. A previous version of this paper contained an erroneous application of the Kasteleyn-Percus method, which is now corrected.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Graphical condensation for enumerating perfect matchings
• A generalization of Kuo condensation
• Graphical condensation of plane graphs: a combinatorial approach
• Applications of graphical condensation for enumerating matchings and tilings
• A quadratic identity for the number of perfect matchings of plane graphs

Mathematics Subject Classification ID

Combinatorial identities, bijective combinatorics (05A19) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Algebraic combinatorics (05E99)

Cited In (18)

• A generalization of Kuo condensation
• Variations on a theme of Kasteleyn, with application to the totally nonnegative Grassmannian
• Proof of a conjecture of Kenyon and Wilson on semicontiguous minors
• Applications of graphical condensation for enumerating matchings and tilings
• Calculation of Pfaffians by a chip removal
• Chip removal for computing the number of perfect matchings
• A \(q\)-enumeration of lozenge tilings of a hexagon with four adjacent triangles removed from the boundary
• Lozenge tilings of a hexagon with a horizontal intrusion
• Lozenge tilings of hexagons with central holes and dents
• A simple explanation for the ``shuffling phenomenon for lozenge tilings of dented hexagons
• Tiling enumeration of hexagons with off-central holes
• Lozenge tilings of hexagons with intrusions. I: Generalized intrusion
• A \(q\)-enumeration of lozenge tilings of a hexagon with three dents
• Graphical condensation of plane graphs: a combinatorial approach
• Beyond Aztec castles: toric cascades in the \(dP_3\) quiver
• Graphical condensation for enumerating perfect matchings
• Algebraic/combinatorial proofs of Cayley-type identities for derivatives of determinants and Pfaffians
• Proof of a refinement of Blum's conjecture on hexagonal dungeons

This page was built for publication: Graphical condensation, overlapping Pfaffians and superpositions of matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976742)