The domino shuffling algorithm first appeared in the following paper by Propp and Kuperberg:

Alternating-sign matrices and domino tilings

They used this algorithm to give a fourth proof that the number of domino tilings of the $n$th aztec diamond is $2^{\frac{n(n+1)}{2}}$.

Now the domino shuffling has been a powerful tool in the combinatorics of domino tilings. The algorithm is quite simple, but its correctness is very subtle to illustrate.

Consider the infinite chessboard on the lattice $\mathbb{Z}^2$, color the cells black or white such that adjacent cells get different colors. Then any $1\times2$ domino (if placed on the chessboard) will cover exactly one white cell and one black cell.

Now suppose some dominos (the number of the dominos may be infinite) are placed on the chessboard with out overlapping with each other, they cover the whole chessboard partilly, so we call it a partial tiling $T$.

A $2\times2$ square is called odd block with respect to $T$ (following Propp's convention), if it contains exactly two parralle dominos of $T$, and has a black cell in its upper left-hand corner. Any $2\times2$ square with a black cell in its upper left-hand will be called a block.

The partial tiling $T$ is called odd-deficient, if it has no odd blocks, and it's free region (cells not covered by $T$) can be tiled with disjoint blocks.

The domino shuffling algorothm states that, given any odd-deficient partial tiling $T$, one can produce a new partial tiling $S(T)$ which is also odd-deficient, and the mapping $T\to S(T)$ is an involution. ($S(S(T))=T$)

The algorithm goes as follows: for every domino $A$ in $T$, we find the unique block $B$ contains $A$, then we move $A$ to the oppsite position in $B$.

It's easy to see that $S(T)$ would not contain any odd block, because odd blocks are unchanged under the shuffling procedure, and since $T$ contains no odd blocks, $S(T)$ would not either.

But the crucial point is that the free region of $S(T)$ can also be tiled by disjoint blocks. This is a very subtle problem in the algorithm, the The original proof in Propp's paper did not explain much in this direction, which puzzled me for quite a long time.

In Aigner's book "A course in Enumeration", he used a 2-coloring method to handle this problem,but I think his wany is still too involved.

My question is: is there any easy way to deduce that $S(T)$ is also odd-deficient?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.