# Why is the “distributive lattice” structure of domino tilings significant?

In Conway's Tiling Groups Thurston shows that the set of tilings of a simply connected figure by dominoes forms a distributive lattice, with an order derived from his height function. It is also possible to define an order without a height function (and indeed this can be done for figures with holes too.) He uses it (as I roughly understand) to derive a tiling algorithm. (That is, an algorithm to find a tiling of a figure by dominoes if it exists).

Except for that algorithm, I am wondering why is it interesting that we can impose a distributive lattice structure on tilings of a figure? I am failing to understand the significance of this. The fact that they are connected is interesting (I think this makes many of the random tiling algorithms possible, for instance), but what is the difference between a set of tilings that are connected (through primitive operations) and has a lattice ordering, and moreover a distributive lattice ordering, and those that don't?

(One thing I noted from Wikipedia is that a distributive lattice does not have certain specific sublattices, which give rise to some identities, such as if $a \vee b = a \vee c$ and $a \wedge b = a \wedge c$, then $b = c$. But in tilings... is this useful to know?)

^ Orderings of various figures.

• What is a tilling algorithm? – Aqua Jan 29 '18 at 8:14
• @ChristianF An algorithm to find a tiling (by dominoes) of a given figure. (The algorithm uses the height function he defines, but I think it works because there is a "maximal" tiling. The details are not 100% clear to me at this stage.) I added that to the question too. – Herman Tulleken Jan 29 '18 at 8:18

I don't have a satisfying answer to this question yet, but here is one interesting consequence.

In Characterization of Domino Tilings of Squares with Prescribed Number of Nonoverlapping $2 \times 2$ Squares the author shows among other things, that for squares there is a unique tiling up to rotation that contains only one flippable pair (that is, a $2 \times 2$ square covered by two dominoes who share a long edge). He uses a special configuration (called a pyramid) to prove it, and it is rather elaborate.

We can use the lattice structure to prove a slightly stronger result:

Any tileable region without holes has at most 2 tilings with a single flippable pair. If there are two such tilings, and the figure has 90 degrees rotational symmetry, the two tilings are a 90 degrees rotation of each other, and the flippable pair's center is over the center of rotation.

The proof is roughly this: A tiling with a single flippable pair must either be minimal or maximal (because the only way to reduce or increase the rank is by performing a flip: if a tiling has only one flippable pair, it can only either go up or down; not both.) The minimal and maximal elements are unique, so in all there can only be two.

Now if the figure has 90 degrees symmetry, we can find another tiling from one tiling by rotating it 90 degrees. This new tiling is different because dominoes don't have 90 degree symmetry. Therefor, the new tiling must be the other tiling. If the flippable pair is not on the center, then we would be able to generate four distinct tilings, so because 2 is the max, the flippable pair must be in the center.

I think we can also say other things about the tilings if the figure has other symmetries, but I have not worked out exactly what.

(For example, if the figure has horizontal and vertical symmetry, the flippable pair must coincide with one of the axes of reflection.)

I think it is also interesting to consider the other theorems in that paper, and see how the lattice structure and symmetry conspire to get other results.

Update: The structure of a distributive lattice also makes it possible to assign a ranking function to tilings. This function tells us how many flips we need to get from the minimum tiling to any other tiling, and can be used to calculate the flip distance between any two tilings in a straightforward way. We can then also calculate the maximum flip distance between tilings of a region (see for example this: Distances in domino flip graphs).