Graphical Condensation Generalizations Involving Pfaffians and Determinants

Abstract

Graphical condensation is a technique used to prove combinatorial identities among numbers of perfect matchings of plane graphs. Propp and Kuo first applied this technique to prove identities for bipartite graphs. Yan, Yeh, and Zhang later applied graphical condensation to nonbipartite graphs to prove more complex identities. Here we generalize some of the identities of Yan, Yeh, and Zhang. We also describe the latest generalization of graphical condensation in which the number of perfect matchings of a plane graph is expressed as a Pfaffian or a determinant where the entries are also numbers of perfect matchings of subgraphs.

12 pages

Cited by in corpus (10)

• Beyond Aztec Castles: Toric Cascades in the $d{P}_3$ Quiver
• Lozenge tilings of hexagons with central holes and dents
• Proof of a conjecture of Kenyon and Wilson on semicontiguous minors
• A $q$-enumeration of lozenge tilings of a hexagon with three dents
• Tiling Enumeration of Hexagons with Off-central Holes
• Discrete integrable systems and condensation algorithms for Pfaffians
• Correlations in totally symmetric self-complementary plane partitions
• Combinatorics of Tripartite Boundary Connections for Trees and Dimers
• Planar flows and Plücker's type quadratic relations over semirings
• Graphical condensation, overlapping Pfaffians and superpositions of matchings