Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given a domino tiling of a rectangle, we can transform it to a new tiling by the following move: pick two dominos that share a long edge, and rotate them in place 90 degrees. Is it possible to change any domino tiling to any other domino tiling by repeating this move?

share|improve this question

2 Answers 2

up vote 8 down vote accepted

This is supposedly proved by Bill Thurston in his classic paper Conway's tiling groups.

Edit: Here is some more information from this paper and that paper. To follow the explanation, please open the first paper at page 2 and look at Figure 2.

Given a domino tiling, there is a way to assign heights to vertices (right part of Figure 2). Pick your favorite $2\times 2$ rectangle covered by two dominoes. Notice that the heights of all four corners are the same, say $h$, and the point at the center has height $h \pm 2$. Moreover, the point in the center is a local extremum. The move (also called a domino flip) changes the sign: see Figure 1 on page 5 of the second paper.

Apply repeatedly the following algorithm: While the function has a local minimum, flip it into a local maximum. The algorithm increases heights of points, so must converge. Moreover, it is not hard to show that there is a unique local maximum: the corresponding heights can be determined explicitly subject to the constraints. The corresponding tiling appears in Thurston's paper, Figures 4.4 and 4.5 on pages 14 and 15 (769 and 770), respectively.

Since any tiling can be flipped into this tiling of maximal height, flips can transform any given tiling to any other given tiling.

Edit: Eric Rémila explains everything in the paper "The lattice structure of the set of domino tilings of a polygon", which is unfortunately not freely available. He shows that there is a unique maximal tiling by proving that the pointwise maximum of two height functions is also a height function; he does that by showing that every edge comes from one of the tilings.

He also provides an optimal algorithm to flip from one tiling to another. This algorithm goes through the pointwise maximum of the height functions of both tilings, and changes each vertex in only one direction. Therefore the number of flips needed is exactly one fourth of the total height difference (L1 distance), a formula he attributes to an earlier 1995 paper, "Spaces of domino tilings".

The latter paper, by Saldanha, Tomei, Casarin and Romualdo, may be the first to which proves this result. Still, usually the result is attributed to (Bill) Thurston's paper.

share|improve this answer
1  
Could you, please, give more precise reference -- or better yet, sketch of the proof? –  Grigory M May 1 '11 at 8:27
    
@Grigory: It seems like the theorem is only implied by Thurston's paper - I now included a proof sketch adapted from two other papers. –  Yuval Filmus May 2 '11 at 1:56
    
interesting, thank you –  Grigory M May 2 '11 at 20:43

A generalization of this result appears in Dylan Thurston's paper "From dominoes to hexagons".

share|improve this answer

Your Answer

 
discard

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.