Perfect matchings of cellular graphs (Q1915154)

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}\).