Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|cite|improve this question
Can I come to your class? – Anthony Quas Jan 23 '12 at 16:40
Anyone in with an interest in these topics is welcome to attend my UC Berkeley class "Topics in Random Spatial Processes", which meets in 5 Evans Hall from 9:30 to 11:00 on Tuesdays and Thursdays, with the proviso that if the room fills up, registered students have precedent over auditors. – James Propp Jan 23 '12 at 18:38
This is just me rambling, but isn't tilings related to non-inttersecting paths, and then, you can use Gessel-Vienot-Lindelöf theorem. – Per Alexandersson Aug 8 '14 at 9:31

1 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.

share|cite|improve this answer
So, so, so cool. – John Wiltshire-Gordon Mar 9 at 16:05
Nice; I'll definitely include this proof the next time I teach a course on perfect matchings! (Though I am a bit fuzzy on how one would prove the topological lemma that asserts that these four kinds of singularities are all that can happen.) – James Propp Mar 10 at 12:25
If all edges are straight line segments then it isn't too bad (and only types 1 and 4 occur). If $G$ has $n$ vertices, then all maps from $G$ to $\mathbb{R}^2$ can be parametrized by $\mathbb{R}^{2n}$. The immersions form a dense open subset, separated by hyperplane corresponding to singularities of types 1 and 4. The points corresponding to worse singularities are finitely many codimension two polytopes, so we can avoid them. – David Speyer Mar 10 at 13:19
If you allow curvy edges (which I'd definitely prefer) then I have to admit that I don't exactly know how you make these transversality arguments either. The analogous claim for knot diagrams is that the Reidemester moves are enough. – David Speyer Mar 10 at 13:21
The proof of Reidemeister's Theorem is famously incomplete; Reidemeister is sketchy in the original paper, and most other sources don't bother going through it. It's much easier to prove it for PL edges, and then approximate smooth edges by PL edges. – Dylan Thurston Mar 10 at 17:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.