An exploration of the permanent-determinant method

MaRDI QIDQ1271415zbMATH OpenFDO

Authors Greg Kuperberg

Publication date 22 November 1998

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

Full work available at URL https://arxiv.org/abs/math/9810091, https://eudml.org/doc/119661, http://www.emis.de/journals/EJC/Volume_5/Abstracts/v5i1r46.html

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

zbMATH Keywords

Carlitz matricesperfect matchings of plane graphspermanent-determinant methodPfaffian methodplane partitions

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The permanent-determinant method and its generalization, the Hafnian-Pfaffian method, are methods to enumerate perfect matchings of plane graphs that was discovered by P. W. Kasteleyn. We present several new techniques and arguments related to the permanent-determinant with consequences in enumerative combinatorics. Here are some of the results that follow from these techniques: 1. If a bipartite graph on the sphere with 4n vertices is invariant under the antipodal map, the number of matchings is the square of the number of matchings of the quotient graph. 2. The number of matchings of the edge graph of a graph with vertices of degree at most 3 is a power of 2. 3. The three Carlitz matrices whose determinants count a x b x c plane partitions all have the same cokernel. 4. Two symmetry classes of plane partitions can be enumerated with almost no calculation.

Review text

Summary: The permanent-determinant method and its generalization, the Hafnian-Pfaffian method, are methods to enumerate perfect matchings of plane graphs that were discovered by P. W. Kasteleyn. We present several new techniques and arguments related to the permanent-determinant with consequences in enumerative combinatorics. Here are some of the results that follow from these techniques: (1) If a bipartite graph on the sphere with \(4n\) vertices is invariant under the antipodal map, the number of matchings is the square of the number of matchings of the quotient graph. (2) The number of matchings of the edge graph of a graph with vertices of degree at most 3 is a power of 2. (3) The three Carlitz matrices whose determinants count \(a\times b\times c\) plane partitions all have the same cokernel. (4) Two symmetry classes of plane partitions can be enumerated with almost no calculation.

Recommendations

• Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
• How to calculate the number of perfect matchings in finite sections of certain infinite plane graphs
• A note on the number of perfect matchings of bipartite graphs
• Symmetries of plane partitions and the permanent-determinant method

Cited in

(42)

• Dimers on surface graphs and spin structures. II
• Dimers on graphs in non-orientable surfaces
• (--1)-enumeration of plane partitions with complementation symmetry
• Generalized domino-shuffling.
• The number of rhombus tilings of a symmetric hexagon which contain a fixed rhombus on the symmetry axis. II
• Pfaff's method. I: The Mills-Robbins-Rumsey determinant.
• Kasteleyn cokernels
• Determinants and perfect matchings
• Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians
• Pólya convertibility problem for symmetric matrices
• Plane partitions of shifted double staircase shape
• The Z-Dirac and massive Laplacian operators in the Z-invariant Ising model
• Dimers on surface graphs and spin structures. I
• The Z-invariant Ising model via dimers
• Enumeration of spanning trees of graphs with rotational symmetry
• Pseudo-centrosymmetric matrices, with applications to counting perfect matchings
• A Schur function identity related to the \((-1)\)-enumeration of self-complementary plane partitions
• Advanced determinant calculus: a complement
• Chip removal for computing the number of perfect matchings
• Graph coverings and twisted operators
• Minimal bipartite dimers and higher genus Harnack curves
• A factorization theorem for lozenge tilings of a hexagon with triangular holes
• Dehn coloring and the dimer model for knots
• A Riccati differential equation and free subgroup numbers for lifts of \(\mathrm{PSL}_2(\mathbb Z)\) modulo prime powers
• Trivariate monomial complete intersections and plane partitions
• Discrete Dirac operators on Riemann surfaces and Kasteleyn matrices
• Discrete Dirac operators, critical embeddings and Ihara-Selberg functions
• Spin from defects in two-dimensional quantum field theory
• Symmetries of shamrocks. IV: The self-complementary case
• scientific article; zbMATH DE number 5057518 (Why is no real title available?)
• Enumeration of Lozenge tilings of hexagons with a central triangular hole
• Enumeration of perfect matchings in graphs with reflective symmetry
• Elliptic dimers on minimal graphs and genus 1 Harnack curves
• Isoradial immersions
• Kasteleyn cokernels and perfect matchings on planar bipartite graphs
• The Schwarzian octahedron recurrence (dSKP equation) I: explicit solutions
• The combinatorial formula for open gravitational descendents
• The critical Z-invariant Ising model via dimers: Locality property
• The Doob transform and the tree behind the forest, with application to near-critical dimers
• Miquel dynamics, Clifford lattices and the dimer model
• Quadri-tilings of the plane
• Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices

This page was built for publication: An exploration of the permanent-determinant method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1271415)