Graphical condensation, overlapping Pfaffians and superpositions of matchings

MaRDI QIDQ976742zbMATH OpenFDO

Authors Markus Fulmek

Publication date 16 June 2010

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

Full work available at URL https://arxiv.org/abs/0906.4236, https://eudml.org/doc/222559, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r83.html

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

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)

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.

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

Cited in

(18)

• A generalization of Kuo condensation
• Variations on a theme of Kasteleyn, with application to the totally nonnegative Grassmannian
• Applications of graphical condensation for enumerating matchings and tilings
• Proof of a conjecture of Kenyon and Wilson on semicontiguous minors
• 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
• A q-enumeration of lozenge tilings of a hexagon with three dents
• Lozenge tilings of hexagons with intrusions. I: Generalized intrusion
• Graphical condensation of plane graphs: a combinatorial approach
• Beyond Aztec castles: toric cascades in the dP₃ 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)