Group Theoretic Origin of the Domino Height Functions

In order to learn about domino shuffling, I have asked around various times for implementations of the domino shuffling algorithm.

The original program was implemented by Sameera Iyengar who was a student at MIT in the mid 90’s and has since gone into theater. Programming has changed a bit in the past 20 years, and I have posted my own python implementation on the internet.

The height of the domino goes up and down around each tiling. What happens when we join some tiles together?

1-0-1-0-1-0-1-0
|   | | |   | |
2-3-2 I 2-3-2 I
|   | | |   | |
1-0-1-0-1-0-1-0

Here I means -1 (so as to only take up one space in the ASCII art).

Tilings and 3D surfaces

If you tile a rectangle with dominos, the height function defines a surface over the edges of the tiling.
Here are pictures of 3D surfaces you can get with the domino tiling projected to various angles.

3D partitions ------ Lozenge tilings

How do we get height functions in the first place?

The domino group is: \langle x,y: xy^2x^{-1}y^{-2}= yx^2y^{-1}x^{-2} = 1 \rangle
The lozenge group is: \langle x,y,z: xy = yx, xz = zx, zy = yz \rangle  = \mathbb{Z}^3

These were calculated by William Thurston in his math monthly article. Cayley graphs are graphical ways of drawing the elements of a group presentation. Thurston takes it a step further and draws Cayley 2-complexes.

Tilings by T-tetraminos were analyzed by Korn and Pak.

 _ _ _ _
|_   _| |
| |_|_  |
|  _| |_|
|_|_ _ _|

Are there any other cases with interesting height functions?  It seems very difficult to solve the group equations outside the realm of domino’s or lozenges.

Example: Tri-ominos

At one point I tried to work out the relation for the L-triomino in the plane. Any lattice polygons can be presented in a group with two generators.
\langle x, y |  y^{-2}x^2yx^{-1}yx^{-1}=   xyxyx^{-2}y^{-2}  = x^2y^2x^{-1}y^{-1}x^{-1}y^{-1} =y^{-1}xy^{-1}xy^2x^{-2} = 1\rangle

 _                             _ _                   
| |_                          |  _|                  
|_ _| y^(-2)x^2yx^(-1)yx^(-1) |_|   xyxyx^(-2)y^(-2) 
   _                                  _ _
 _| |                                |_  |
|_ _| x^2y^2x^(-1)y^(-1)x^(-1)y^(-1)   |_| y^(-1)xy^(-1)xy^2x^(-2)

Manipulating the group words looks very difficult. Instead, we can visually merge two triominos to get

 _                                      _
|_|                                   _|_|
|_| yxyx^{-1}y^{-1}xy^{-1}x^{-1} = 1 |_|   xy^2xy^{-1}x^{-2}y^{-1} = 1

Then taking three of these pieces we can show a loop has order 3, xyx^{-1}^{-1})^3=1. The resulting group is \mathbb{Z}/3\mathbb{Z}.

This non-commutative loop model looks very interesting… maybe a way of studying non-abelian cohomology of \mathbb{R}^2.

Further Reading

About these ads

About this entry