Matchings in graphs on non-orientable surfaces
type: Item
instance of: scholarly article
title: Matchings in graphs on non-orientable surfaces
zbMATH Open document ID: 1025.05052
author: Glenn Tesler
published in: Journal of Combinatorial Theory. Series B
publication date: 2000-06-25T00:00:00Z
review text: P. W. Kasteleyn stated that the number of perfect matchings in a graph embedding on a surface of genus \(g\) is given by a linear combination of \(4^g\) Pfaffians of modified adjacency matrices of the graph, but didn't actually give the matrices or the linear combination. We generalize this to enumerating the perfect matchings of a graph embedding on an arbitrary compact boundaryless 2-manifold \(S\) with a linear combination of \(2^{2-\chi(S)}\) Pfaffians. Our explicit construction proves Kasteleyn's assertion, and additionally treats graphs embedding on non-orientable surfaces. If a graph embeds on the connected sum of a genus \(g\) surface with a projective plane (respectively, Klein bottle), the number of perfect matchings can be computed as a linear combination of \(2^{2g+1}\) (respectively, \(2^{2g+2}\)) Pfaffians. We also introduce ``crossing orientations,'' the analogue of Kasteleyn's ``admissible orientations'' in our context, describing how the Pfaffian of a signed adjacency matrix of a graph gives the sign of each perfect matching according to the number of edge-crossings in the matching. Finally, we count the perfect matchings of an \(m\times n\) grid on a Möbius strip.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1464305
zbMATH Keywords: dimer
zbMATH Keywords: Kasteleyn
zbMATH Keywords: perfect matchings
zbMATH Keywords: surface
zbMATH Keywords: genus
zbMATH Keywords: Pfaffians
zbMATH Keywords: signed adjacency matrix
zbMATH Keywords: edge-crossings
zbMATH Keywords: Möbius strip
MaRDI profile type: Publication
OpenAlex ID: W2077319040
cites work: Q4001359
cites work: On the theory of Pfaffian orientations. I: Perfect matchings and permanents
cites work: Second Order Polynomial Recursions
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Q5605168
cites work: Matching theory
cites work: Q4064159
cites work: Q3827224
cites work: Q3851094
DOI: 10.1006/JCTB.1999.1941
description: scientific article; zbMATH DE number 1464305