slick-proof-of-trick-for-counting-domino-tilings

Question

The trick for rewriting the number of domino tilings of a simply-connected finite lattice region as the absolute value of the determinant of a matrix (due I believe to Kasteleyn and Percus, but if Fisher deserves credit for this too please set me straight!) hinges on a combinatorial lemma relating the number of vertical dominos in a tiling to the parity of the permutation-matrix associated with the tiling.

What's the most direct way to see this?

My favorite approach is to set up a distributive lattice structure on the set of tilings, and use it to show that every tiling may be obtained from every other by rotating 2-by-2 blocks, and then use this last fact to prove the lemma, but this is a bit indirect. I've seen a way to do it with Pick's Theorem, but I suspect that there's a simpler way. Right now I'm thinking about an approach that involves superimposing matchings to get unions of cycles, and arguing that the retiling associated with such a cycle can always be achieved by a succession of retilings of 2-by-2 blocks, but maybe there's an even simpler way.

The trick applies more generally to all bipartite planar graphs, and Kasteleyn showed that you could handle arbitrary planar graphs by this method (using Pfaffians), but for right now I'll be satisfied with an argument that applies in the case of dominos on a square grid. (As you might guess, the motivation behind my question is pedagogical; I'll be teaching a class on this material tomorrow.)

Answer 1

$\def\RR{\mathbb{R}}$This isn't the right answer for your class, because it works for a level of generality you don't need, but last summer I found what I think is the right way to prove this result for a general bipartite planar graph or, working harder, for any planar graph and I thought I'd record it here. I'm sure this isn't original, but I didn't find it in a quick literature search.

Let $G$ be a bipartite graph. We'll define an immersion of $G$ to $\RR^2$ to be a map $\phi: G \to \RR^2$ which is injective except that $\phi$ is allowed to make edges cross transversely in their interiors; $\phi$ is not permitted to create triple crossings. For example, we can send the vertices of $G$ to generic points of $\RR^2$ and join them by line segments.

Assign a weight $x_e$ to each edge of $G$. For a perfect matching $M$ of $G$, define $\mathrm{cross}(M, \phi)$ to be the number of places where edges of $M$ cross. Define the matching polynomial of $(G, \phi)$ to be $$\mu(G, \phi) = \sum_M (-1)^{\mathrm{cross}(M, \phi)} \prod_{e \in M} x_e$$ where the sum is over all perfect matchings of $G$.

We claim that there is a way to take the adjacency matrix of $G$ and replace the entry corresponding to $e$ by $\pm x_e$ to make a matrix $A$ with $\mu(G, \phi) = \det A$. In particular, if $G$ is a planar graph, we can get the generating function for matchings with no signs.

Proof First, suppose that all of the black vertices lie on the line $y=0$ and all the white vertices lie on the line $y=1$, in the same order as the rows and columns of the matrix, and joined by line segments. Then we can put $x_e$ in all positions of $A$, and $(-1)^{\mathrm{cross}(\phi, M)}$ is the sign of the permutation $M$.

Now, consider varying $\phi$ while preserving $G$ and we claim that the result stays true. If we vary $\phi$ generically, we can get from any immersion to any other while passing through singularities of the following sorts:

• A triple crossing of edges. The same signs work on both sides of the triple crossing.

• Two edges become tangent. On one side of the singularity, they cross $m$ times, on the other side they cross $m+2$ times. The same signs work on both sides of the tangency.

• An edge $e$ forms a cusp. On one side of the cusp, it passes through itself, on the other side it doesn't. Negate the sign of $x_e$.

• $\phi$ sends a vertex into the interior of an edge $e$. Negate the sign of $x_e$.

So in every case, as the topology of $\phi$ changes, we can change the signs in the matrix. $\square$

The analogous argument works with general graphs and Pfaffians, starting with the vertices all lying on a circle.