Take the 2-minute tour ×
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|improve this question
1  
Can I come to your class? –  Anthony Quas Jan 23 '12 at 16:40
1  
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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.