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.

Review text

Summary: The purpose of this paper 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.

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)

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

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)