A problem in the domino shuffling algorithm

Question

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 partially, 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 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?

Answer 1

Propp redoes, clarifies and generalizes domino shuffling in the following lovely paper:

Propp, James. "Generalized domino-shuffling." Theoretical Computer Science 303, no. 2 (2003): 267-301. http://arxiv.org/abs/math/0111034

The redone explanation is a way of thinking of the domino shuffle map locally, using a graph transformation called urban renewal; these days people also call it the spider move. The move replaces a 4-cycle in a graph (the "square", we might call it) with an 8-vertex graph made of a 4-cycle with a pendant edge on each vertex (the "spider"); the feet of the spider get attached where the vertices of the square were.

Spider moves, when combined with a suitable reweighting of the edges in the graph, preserve the generating function for perfect matchings up to an explicit constant. The argument is much like the one in Elkies-Kuperberg-Larsen-Propp which you're asking about, but it is substantially streamlined because you only have to think about the square and the spider.

In answer to your question: once you understand this point of view, odd-deficiency is obvious. When you reconstruct the domino shuffle using spider moves (which Propp explains how to do in the same paper), the squares and the spiders comprise the odd blocks, and all the action happens within them. The even blocks do not enter into the picture at all.

As further evidence that the spider move is the correct point of view, Kenyon-Goncharov http://arxiv.org/abs/1107.5588 recently used the spider move to define a certain cluster integrable system for the dimer model.

Answer 2

It might help to start with a notion of arrangement (dominoes might overlap), note that the shuffle is an involution on the set of arrangements, and then do a tedious combinatorial argument to show it preserves odd-deficient tilings (odt).

To show an odt A maps to a nonoverlapping arrangement, note that s(A) producing an overlap either means an odd block of A or a nonblock tiling of the complement of A. To show an odt A maps to B whose complement is block-tilable, you might consider cases. Suppose a topmost domino of A is horizontal and moves up under S. This implies there is a domino to the left and the right of this domino, otherwise A is not odt Further, these dominoes either also move up, or they move in toward the first domino under S. This dynamic may tell you enough to deduce block tilability of the complement, although I do not see a clean finish to this.