Perfect matchings of cellular graphs
type: Item
instance of: scholarly article
title: Perfect matchings of cellular graphs
zbMATH Open document ID: 0856.05080
DOI: 10.1023/A:1022408900061
author: Mihai Ciucu
published in: Journal of Algebraic Combinatorics
publication date: 1996-06-11T00:00:00Z
review text: Let \(S\) be the graph whose vertex set consists of the lattice points \(\{(i,j) \in \mathbb{Z}^2 \mid i + j\) even\}, with edges between nearest neighbors. A cell is any square formed by a 4-cycle of \(S\) whose center has even \(x\)-coordinate. A finite subgraph \(G\) of \(S\) is called cellular if its edges can be partitioned into cells. Given a cellular graph \(G\), horizontal chains and vertical chains are defined to be maximal connected horizontal and connected vertical, respectively, sequences of cells of \(G\). Let \(h(G)\) and \(v(G)\) denote the numbers of horizontal and vertical chains, respectively, of \(G\). The endpoints of a chain \(L\) are the leftmost and rightmost vertices of a horizontal chain, and the uppermost and lowermost vertices of a vertical chain. The core of \(G\) is the graph \(G'\) obtained from \(G\) by deleting the endpoints of all chains together with any edges incident with the endpoints. Let \(g\) and \(g'\) denote the number of perfect matchings of \(G\) and \(G'\), respectively. The main result of the paper is that for a cellular graph \(G\), \(g = 0\) unless \(h(G) = v(G)\). If the latter condition holds, then \(g = 2^{h (G)}g'\). As a corollary, this proves that the number of perfect matchings in the Aztec diamond of order \(n\) is \(2^{n (n + 1)/2}\).
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 887235
zbMATH Keywords: cell
zbMATH Keywords: cellular graph
zbMATH Keywords: horizontal chains
zbMATH Keywords: vertical chains
zbMATH Keywords: endpoints
zbMATH Keywords: core
zbMATH Keywords: perfect matchings
zbMATH Keywords: Aztec diamond
reviewed by: Brian Alspach
MaRDI profile type: Publication
cites work: Q5787302
cites work: Alternating-sign matrices and domino tilings. I
cites work: The statistics of dimers on a lattice. I: The number of dimer arrangements on a quadratic lattice
cites work: Alternating sign matrices and descending plane partitions
cites work: Determinants and alternating sign matrices
cites work: Remark on the dimer problem
cites work: Bootstrap Percolation, the Schröder Numbers, and theN-Kings Problem
full work available at URL: a:1022408900061
OpenAlex ID: W2109934391
Recommended article: A complementation theorem for perfect matchings of graphs having a cellular completion
Recommended article: Perfect matchings of polyomino graphs
Recommended article: Perfect matchings in pruned grid graphs
Recommended article: Exact Perfect Matching in Complete Graphs
Recommended article: Perfect matchings and derangements on graphs
Recommended article: Perfect matchings of generalized polyomino graphs
Recommended article: Graphs of triangulations and perfect matchings
Recommended article: Perfect Matchings of Regular Bipartite Graphs
Recommended article: Perfect matchings in highly cyclically connected regular graphs
Recommended article: Q3150020
description: scientific article; zbMATH DE number 887235