Rhombus Tilings and a Nice Bijection

I want to write a short post giving an example of what seems to me to be a rather nice proof without words. Like all the best proofs without words, they require some words to set everything up, and then even the proof itself is enhanced with a few words.

The goal is a bijection between two combinatorial objects. The first is the family of rhombus tilings. Perhaps the easiest way to define these is to give an example.

As you can see, we have tiled a hexagon with rhombi. The tiles are allowed to be in any of the three possible orientations. It matters that the angles of the hexagon are 120, as we want it to be possible to squeeze rhombi into a corner in two different ways (ie either a single tile or two tiles together), and thus the rhombi should also have angles 120 and 60. The hexagon does not have to be equilateral, as in this example, but obviously all the side lengths should be an integer multiple of the side length of the rhombus, which without loss of generality we may take to be 1.

The other combinatorial object is the class of plane partitions. We again give an example:

4 3 3 2 1
4 2 2 2
3 2 2 1
2 1 1

Notice that all the rows and columns are weakly decreasing. One observation worth making is that the diagonals gives a family of so-called interlaced partitions. In any case, we want to establish this bijection. First I show the idea, that is the proof without words bit. Then I’ll clarify exactly how to make the bijection work.

The first step is to colour a rhombus tiling with a different colour for each orientation, as shown.

The next step is the proof without words bit. We now look at the diagram as if we were looking into a stack of cubes arranged in the positive orthant of R^3. The colouring makes this much more visually arresting. Black rhombi correspond to the (visible) top sides of cubes, while blue and red faces point out in the x and y directions respectively. The key observation is that a rhombus tiling means we can see at least one face of every cube. Otherwise we would need some smaller rhombi to account for the way that some cubes will be partially hidden between taller but closer piles. So if make a note of the heights of all the piles, we should get a plane partition.

After reordering our definition of plane partition, so it is weakly increasing left-right and down-up, corresponding to the x and y axes drawn on the above diagram, the given rhombus tiling should give the following plane partition:

1 2 3
0 1 3
0 0 2

The only thing we need to sort out is precisely how the dimensions of the hexagon restrict the choice of plane partition. Note that we could keep the heights exactly the same but get a different tiling by adding an extra row of red oriented rhombi above the top-left part, and an extra row of blue oriented rhombi above the top-right part. The point is that this would give us a bigger hexagon.

The first observation is that the dimensions of the plane partition correspond to two of the side lengths of the hexagon, indeed the bottom two sides. The third length of the hexagon corresponds to the maximum possible height (ie z component) of the region we are looking at. This is therefore an upper bound on the heights of the stacks.

So we can conclude our bijective argument. There is a bijection between rhombus tilings of the hexagon with side lengths X, Y, Z and plane partitions with dimension X x Y, (where entries are allowed to be zero) where the largest element (which is by definition also the top-left element, or top-right in our re-definition) is at most Z.

It seems there are plenty of interesting questions to be asked about both deterministic and random tilings and plane partitions, based on talks in Marseille. For now though, I feel ill-qualified even to read about such things, so will leave it at that for today.

Related articles

• Tilings and their duals (geometricolor.wordpress.com)
• irregular tilings and their duals (geometricolor.wordpress.com)
• Determinants and Dodgson’s condensation (icountslowly.wordpress.com)
• A Cuddly, Crocheted Klein Quartic Curve (blogs.scientificamerican.com)