scientific article; zbMATH DE number 1405497
Exact enumeration problems, generating functions (05A15) Combinatorial aspects of tessellation and tiling problems (05B45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)
A perfect matching of a graph \(G\) is a subset of the edges of \(G\) with the property that each vertex in \(G\) belongs to precisely one edge in the subset. This comprehensive paper is concerned with the problem of counting and enumerating the perfect matchings in a graph. This problem has important applications in physics and chemistry, and was first studied by researchers in these areas in the 1930s. For general graphs it is computationally hard to answer this problem. However, for many infinite families of special graphs the number of perfect matchings is given by compellingly simple formulae. In particular, over the past ten years a great many families of this kind have been discovered, and while there is no single unified result that encompasses all of them, many of these families resemble one another, both in terms of the form of the results and in terms of the methods that have been useful in proving them. The paper focuses on a list of thirty-two problems in enumeration of perfect matchings, the first twenty of which were presented in a lecture by the author at the Mathematical Sciences Research Unit in 1996. The author summarises progress on these problems and includes pointers to both the printed and on-line literature relating to them. Roughly half of the original twenty problems were solved by participants in the MSRI Workshop on Combinatorics, their students, and others, between 1996 and 1999. Many of the problems are stated in terms of tilings of various regions in the plane. The paper concludes with a set of twelve new open problems. Updates on the status of these problems can be found at \url{http://math.wisc.edu/~propp/update.ps.gz}. For the entire collection see [Zbl 0927.00011].
- The enumeration of perfect matchings in two types of graphs
- Counting matchings in graphs
- Matchings and Hadwiger's conjecture
- Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs
- Matching, matroids, and extensions
- On k-match problems
- Enumeration of matchings in families of self-similar graphs
- The computational strength of matchings in countable graphs
- Matchings in Graphs Variations of the Problem
- A note on divisibility of the number of matchings of a family of graphs
- Exact and asymptotic enumeration of perfect matchings in self-similar graphs
- Enumeration of lozenge tilings of punctured hexagons
- The number of rhombus tilings of a ``punctured hexagon and the minor summation formula
- Combinatorics of perfect matchings in plane bipartite graphs and application to tilings.
- Perfect matchings and perfect powers
- The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis. II
- Enumeration of lozenge tilings of a hexagon with a shamrock missing on the symmetry axis
- Interactions between interleaving holes in a sea of unit rhombi
- Beyond Aztec castles: toric cascades in the dP₃ quiver
- Domino tilings of the expanded Aztec diamond
- State matrix recursion method and monomer-dimer problem
- Graphical condensation for enumerating perfect matchings
- Singular polynomials of generalized Kasteleyn matrices
- On the number of perfect matchings of line graphs
- Domino tilings for augmented Aztec rectangles and their chains
- Channels, billiards, and perfect matching 2-divisibility
- Lozenge tilings of a hexagon with a horizontal intrusion
- On the number of perfect matchings in the line graph of a traceable graph
- Tiling enumeration of hexagons with off-central holes
- An extension of the Lindström-Gessel-Viennot theorem
- Dimer coverings of 1-slab cubic lattices
- Dungeons and dragons: combinatorics for the \(dP_3\) quiver
- Billiards, channels, and perfect matching 2-divisibility
- On the asymptotic enumeration of restricted strip arrangements of a chessboard
- Lozenge tilings of hexagons with central holes and dents
- Lozenge tilings of doubly-intruded hexagons
- Enumeration of hybrid domino-lozenge tilings
- Flag arrangements and triangulations of products of simplices
- Perfect matchings of trimmed Aztec rectangles
- Perfect matchings on a type of lattices with toroidal boundary
- Proof of Blum's conjecture on hexagonal dungeons
- A periodicity theorem for the octahedron recurrence
- Pseudo-centrosymmetric matrices, with applications to counting perfect matchings
- Perfect matchings of generalized polyomino graphs
- Pfaffian orientations and perfect matchings of scale-free networks
- Advanced determinant calculus: a complement
- Enumeration of perfect matchings of a type of Cartesian products of graphs
- The weak Lefschetz property for monomial ideals of small type
- Domino tilings of Aztec octagons
- Enumeration of hybrid domino-lozenge tilings. II: Quasi-octagonal regions
- Perfect matchings in random polyomino chain graphs
- A direct encoding of Stoimenow's matchings as ascent sequences
- A q-enumeration of lozenge tilings of a hexagon with three dents
- A generalization of Aztec dragons
- Enumerating perfect matchings in n-cubes
- New aspects of regions whose tilings are enumerated by perfect powers
- A lower bound on the number of elementary components of essentially disconnected generalized polyomino graphs
- scientific article; zbMATH DE number 2053249 (Why is no real title available?)
- Convergence of graphs with intermediate density
- Counting domineering positions
- Signed lozenge tilings
- The Smith normal form of a specialized Jacobi-Trudi matrix
- Enumeration of hybrid domino-lozenge tilings. III: centrally symmetric tilings
- Proof of a refinement of Blum's conjecture on hexagonal dungeons
- Maximum matchings in scale-free networks with identical degree distribution
- Three interactions of holes in two dimensional dimer systems
- Counting tilings by taking walks
- Cyclically symmetric lozenge tilings of a hexagon with four holes
- Enumeration of Lozenge tilings of hexagons with a central triangular hole
- Counting domino tilings of rectangles via resultants
- Applications of graphical condensation for enumerating matchings and tilings
- On the dimer problem of the vertex-edge graph of a cubic graph
- Augmented Aztec bipyramid and dicube tilings
- scientific article; zbMATH DE number 7732126 (Why is no real title available?)
- Enumeration of perfect matchings of the middle graph of a graph \(G\) with \(\triangle (G) \leq 4\)
- On the weighted enumeration of alternating sign matrices and descending plane partitions
- Honeycomb-lattice monomer-dimer mixtures
- Round Aztec windows, a dual of the Aztec diamond theorem and a curious symmetry of the correlation of diagonal slits
- Further results on enumeration of perfect matchings of Cartesian product graphs
- On the number of perfect matchings of middle graphs
- Enumeration of spanning trees containing a perfect matching in saturated non-covered graphs
- Generalizing the divisibility property of rectangle domino tilings
- Matching extendability in Cartesian product of hypercubes and paths
- Enumerating perfect matchings in line graphs of graphs with pendent edges
- Smith normal form in combinatorics
- Solving (large scale) matching problems combinatorially
- Decompositions of amplituhedra
- Domino tiling congruence modulo 4
- Selberg integrals, Askey-Wilson polynomials and lozenge tilings of a hexagon with a triangular hole
- Local move connectedness of domino tilings with diagonal impurities
- A bijection theorem for domino tilings with diagonal impurities
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4938474)
