Applications of graphical condensation for enumerating matchings and tilings

DOI10.1016/j.tcs.2004.02.022zbMath1043.05099arXivmath/0304090OpenAlexW2168654091MaRDI QIDQ596044

Eric H. Kuo

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Generating functionsPerfect matchingsPlane partitionsTilings

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of partitions of integers (05A17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items (85)

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 ⋮ Enumeration of domino tilings of an Aztec rectangle with boundary defects ⋮ Enumeration of antisymmetric monotone triangles and domino tilings of quartered Aztec rectangles ⋮ Proof of a conjecture of Kenyon and Wilson on semicontiguous minors ⋮ Variations on a theme of Kasteleyn, with application to the totally nonnegative Grassmannian ⋮ Enumeration of lozenge tilings of a hexagon with a shamrock missing on the symmetry axis ⋮ Generating function of the tilings of an Aztec rectangle with holes ⋮ Chip removal for computing the number of perfect matchings ⋮ A new simple proof of the Aztec diamond theorem ⋮ A quadratic identity for the number of perfect matchings of plane graphs ⋮ Twists of Plücker coordinates as dimer partition functions ⋮ Symmetries of shamrocks. II: Axial shamrocks ⋮ Double tangent method for two-periodic Aztec diamonds ⋮ Dimers, webs, and positroids ⋮ Replacing Pfaffians and applications ⋮ A \(q\)-enumeration of lozenge tilings of a hexagon with three dents ⋮ A generalization of Aztec dragons ⋮ Unnamed Item ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ Perfect matchings of trimmed Aztec rectangles ⋮ Perfect matchings and the octahedron recurrence ⋮ Toric mutations in the \(\mathrm{dp}_2\) quiver and subgraphs of the \(\mathrm{dp}_2\) brane tiling ⋮ Enumeration of Lozenge tilings of halved hexagons with a boundary defect ⋮ Beyond Aztec castles: toric cascades in the \(dP_3\) quiver ⋮ Augmented Aztec bipyramid and dicube tilings ⋮ The Space of Circular Planar Electrical Networks ⋮ Dungeons and dragons: combinatorics for the \(dP_3\) quiver ⋮ A generalization of Aztec diamond theorem. I ⋮ Symmetries of shamrocks. I. ⋮ Lozenge tilings of hexagons with removed core and satellites ⋮ The combinatorial PT-DT correspondence ⋮ Ratio of tiling generating functions of semi-hexagons and quartered hexagons with dents ⋮ A generalization of Aztec diamond theorem. II. ⋮ On λ-determinants and tiling problems ⋮ A factorization theorem for lozenge tilings of a hexagon with triangular holes ⋮ Lozenge tilings of hexagons with arbitrary dents ⋮ Lozenge tiling function ratios for hexagons with dents on two sides ⋮ Cluster algebras of type \(D\): pseudotriangulations approach ⋮ Laurent biorthogonal polynomials, \( q\)-Narayana polynomials and domino tilings of the Aztec diamonds ⋮ Multiply-refined enumeration of alternating sign matrices ⋮ Lozenge Tilings of a Halved Hexagon with an Array of Triangles Removed from the Boundary ⋮ Tilings of hexagons with a removed triad of bowties ⋮ Proof of Blum's conjecture on hexagonal dungeons ⋮ A graph theoretic expansion formula for cluster algebras of classical type ⋮ From dimers to webs ⋮ Lozenge tilings of a halved hexagon with an array of triangles removed from the boundary. II ⋮ Symmetries of shamrocks IV: The self-complementary case ⋮ From dimers to tensor invariants ⋮ Proof of a refinement of Blum's conjecture on hexagonal dungeons ⋮ Maximum matchings in scale-free networks with identical degree distribution ⋮ A dual of MacMahon’s theorem on plane partitions ⋮ Lambda-determinants and domino-tilings ⋮ Lozenge tilings with gaps in a \(90\degree\) wedge domain with mixed boundary conditions ⋮ An arctic circle theorem for groves ⋮ Graphical condensation for enumerating perfect matchings ⋮ Generalizing the divisibility property of rectangle domino tilings ⋮ Electroid varieties and a compactification of the space of electrical networks ⋮ A shuffling theorem for reflectively symmetric tilings ⋮ A simple explanation for the ``shuffling phenomenon for lozenge tilings of dented hexagons ⋮ The other dual of MacMahon's theorem on plane partitions ⋮ Tiling generating functions of halved hexagons and quartered hexagons ⋮ Channels, billiards, and perfect matching 2-divisibility ⋮ Colored BPS pyramid partition functions, quivers and cluster transformations ⋮ Pfaffian orientations and perfect matchings of scale-free networks ⋮ Plane partitions of shifted double staircase shape ⋮ Unnamed Item ⋮ Combinatorics of the double-dimer model ⋮ Combinatorics of the double-dimer model ⋮ Correlation of a macroscopic dent in a wedge with mixed boundary conditions ⋮ Boundary partitions in trees and dimers ⋮ Chip removal. Urban renewal revisited ⋮ Cyclically symmetric lozenge tilings of a hexagon with four holes ⋮ Cyclically symmetric lozenge tilings of a hexagon with four holes ⋮ Lozenge tilings of hexagons with central holes and dents ⋮ A short proof of two shuffling theorems for tilings and a weighted generalization ⋮ Lozenge tilings of doubly-intruded hexagons ⋮ Domino tilings of Aztec diamonds and squares ⋮ Lozenge tilings of hexagons with holes on three crossing lines ⋮ Frieze patterns for punctured discs ⋮ Lozenge tilings of a hexagon with a horizontal intrusion ⋮ Proof of two conjectures of Ciucu and Krattenthaler on the enumeration of lozenge tilings of hexagons with cut off corners ⋮ A generalization of Kuo condensation ⋮ A new proof for the number of Lozenge tilings of quartered hexagons ⋮ Graphical condensation of plane graphs: a combinatorial approach

Cites Work

• Unnamed Item
• Unnamed Item
• A bijective proof of Cassini's Fibonacci identity
• Binomial determinants, paths, and hook length formulae
• Odd symplectic groups
• Alternating-sign matrices and domino tilings. I
• Dodgon's determinant-evaluation rule proved by TWO-TIMING MEN and WOMEN
• Generalized domino-shuffling.
• Local statistics for random domino tilings of the Aztec diamond
• Reverend Charles to the Aid of Major Percy and Fields Medalist Enrico
• Rectangular arrays and plane partitions

This page was built for publication: Applications of graphical condensation for enumerating matchings and tilings