Combinatorial Tiling Theory and Delaney-Dress Symbols

The study of tilings has a long history, but it was only in the 1980's that a finite symbol was found to uniquely encode both the topology and symmetry of an infinite periodic tiling. This result is due to Andreas Dress using earlier work of Matthew Delaney, so we refer to this description of a tiling as a Delaney-Dress symbol. Two students of Dress, Daniel Huson and Olaf Delgado-Friedrichs, have extended his mathematical formalism and developed efficient algorithms for enumerating tilings of the sphere, euclidean and hyperbolic planes, and 3D euclidean space. This body of work is usually referred to as Combintorial Tiling Theory.

This webpage provides an introduction to the aspects of tiling theory we have used to generate tilings of periodic minimal surfaces. See the the bibliography for links to further reading and the original papers.

Chamber Systems for 2D Tilings

We discuss and illustrate tilings of the hyperbolic plane here, but the concepts apply to the sphere and euclidean plane with almost no adjustment, and the underlying theory generalises to higher-dimensional spaces.

The following four conditions form the definition of a tiling.

We want to study tilings with edge skeletons that are connected networks, so the first condition we impose is that all tiles are closed topological disks (they have no holes).
Tiles can intersect only along their boundaries. The intersection of two tiles defines an edge, the intersection of three or more tiles defines a vertex.
The tiles are uniformly bounded in size.
The tiles cover the whole hyperbolic plane.

The trick to describing the way tiles fit together is to subdivide them into triangles, called flags or chambers , and then record the neighbour-relations of the different symmetry classes of these chambers.

The following pictures show a tiling of the hyperbolic plane by hexagons and squares. To generate a chamber system for this tiling, we make a barycentric subdivision by placing a 2-vertex in the center of each tile, a 1-vertex at the center of each edge, and a 0-vertex at each tiling vertex, then forming 0-1-2-triangles within each tile. The edges of the chambers are also labelled 0-, 1-, and 2-edges according to the type of vertex they face. Chambers for a part of the tiling are illustrated on the right.

As the colouring in the above picture indicates, there are only two different symmetry types of chamber, Red and Blue. Red neighbours itself across the 0- and 1-edges, while the 2-neighbour of Red is Blue; Blue is also its own 0- and 1-neighbour. These neighbour-relations are formally described by maps s0, s1, and s2 from the chamber system onto itself. For obvious geometric reasons, these maps are involutions (their own inverses).

The final step to encode the tiling is to describe what happens when you repeatedly apply pairs of the neighbour maps. There are three orbits to consider:

Applying (s0s1) or (s1s0) always walks around the chambers in a single tile.
(s1s2) walks around a vertex of the tiling.
(s0s2) walks around an edge of the tiling.

The topology of the tiling determines how many times you need to apply each pair to come back to the exact same chamber you started with (not a symmetry copy of it). So for our example, we find that

starting with the bright red chamber, we need to apply (s0s1) six times to walk around the hexagonal tile (represented by a 2-vertex), apply (s1s2) four times to walk around the 0-vertex, and apply (s0s2) twice to walk around the edge.
Since s2(Red) = Blue, the bright blue chamber has the same (s1s2) and (s0s2) orbits, but we need only apply (s0s1) four times to walk around the square face.
In any 2D tiling, (s0s2)^2 is the identity for all chambers, because this orbit represents a walk around an edge of the tiling, and there are always exactly four chambers around the 1-vertex at the center of an edge.

Duality

A geometric duality operation is defined by replacing every tile by a vertex, then joining these new vertices if the original tiles share an edge. This results in a new tiling with the same symmetry as the original, and topological properties dual to the original. The degree of each new vertex is the number of edges the original tile had, and the new tiles have as many sides as the corresponding original vertex degree. The dual of our example hyperbolic tiling by hexagons and squares is therefore a tiling by squares which have two distinct vertices, one of degree 6, and the other of degree 4.

This geometric operation has a simple interpretation in terms of Delaney-Dress symbols. The chambers remain the same, but the 0- and 2- vertices swap roles, as do the 0- and 2-edges, and therefore the s0 and s2 neighbour maps.

Representations of Delaney-Dress symbols

A full description of the Delaney-Dress symbol for a 2D tiling is given by listing the distinct symmetry-classes of chambers, their 0-, 1-, and 2- neighbours (i.e. the action of s0, s1, and s2 on each symmetry class) and their tile and vertex orbit numbers, m10 and m12.

There are a number of different ways to represent this information compactly. The most direct way is via a table. For our example and its dual we have

Chamber
Class

m01

m12

Chamber
Class

m01

m12

Red

Blue

Red

Blue

Red

Blue

Red

Blue

Red

Blue

This is slightly cumbersome and there are three alternative ways to represent the same information depending on context.

The Delaney-Dress graph

This method is often used by Huson and Delgado in their papers. The Delaney-Dress symbol is given by an edge- and node- labelled multi-graph. Each symmetry class of chamber is a node in the graph. Edges in the graph represent the neighbour relations s0, s1, s2. The tile and vertex orbit numbers, m01 and m12, are labels attached to each node. The graphs for our example and its dual are as follows.

Conway Crankshaft

A combination of the tabular and graph representations was developed by John Conway; we call it the “crankshaft notation”. This notation is more human-readable than the others. The chamber symmetry classes are listed down the page, and the two pairs of neighbour-maps, s0s1, and s1s2 are given a column. The chamber classes are joined according to the individual neighbour maps, s0, s1, s2. Connected components of the resulting graph are the distinct tile and vertex orbits, so the m01 and m12 numbers are written in only once for each type of orbit. To get the crankshaft symbol for the dual tiling, you just reflect it in a vertical line.

A numerical string

In their code and papers, Huson and Delgado-Friedrichs use a very compact encoding of the Delaney-Dress symbol. This numerical string is used to sort different possible relabellings of a given DD symbol, and the “smallest” is used as a canonical form for the tiling.

For the example hyperbolic tiling by hexagons and squares, the string is

< 2 : 1 2, 1 2, 2 : 4 6, 4 >
The first number is the number of distinct chambers, 2 in this example. Blue is labelled 1, and red is labelled 2. After the colon there are three sequences separated by commas - these define the s0, s1, and s2 neighbour maps. The first entry in each sequence is the image of chamber 1, so for this example s0(1) = 1. The next entry is the image of the next free chamber, which in this case is chamber 2, so s0(2) = 2. The definition of s1 and s2 proceed in the same way. The sequence for s2 begins with a ‘2’: this mean s2(1) = 2. By definition s2(2) = 1, so there is no need to specify the image of chamber 2 explicitly.

After the second colon there are two lists of numbers which give the m01 and m12 values for each distinct tile and vertex orbit. The tiling by squares and hexagons has two distinct tile orbits {Blue x 8} and {Red x 12} (m01= 4 and 6), and one vertex orbit {(Blue, Red, Red, Blue) x 2} (m12=4).

The symbol for the dual tiling is found by swapping the s0 and s2 maps, and the m01 and m12 values: <2:2,1 2,1 2:4,4 6>

Enumeration of Tilings

Delaney-Dress symbols are enumerated within a symmetry group, and with a defined level of complexity.

The level of complexity is quantified by the number of distinct symmetry classes of tiles, also called the number of transitivity classes. Thus, a tiling in which every tile is related by a symmetry of the entire tiling to every other tile is called tile-1-transitive . In our example above there are two types of tile, so it is tile-2-transitive.

The second distinction we make is between fundamental and non-fundamental tiles: a tile is fundamental if no symmetery of the entire tiling maps it onto itself. In the example above, both the hexagonal and square tiles are non-fundamental.

Following Huson, a systematic enumeration of DD symbols is made in the following order:

Start with the tile-1-transitive fundamental tilings with a given symmetry orbifold .
From these, determine all possible tile-1-transitive non-fundamental tilings by applying GLUE operations.
From the tile-1-transitive fundamental tilings, determine all tile-2-transitive fundamental tilings by applying a SPLIT operation.
From these, determine tile-2-transitive non-fundamental tilings by applying GLUE operations to each of the two tile-types separately, and then to both.
The SPLIT and GLUE operations are applied successively to enumerate tilings with more transitivity classes of tile.

A symmetry group is described by its orbifold , and the system of chambers for a Delaney-Dress symbol is really just a triangulation of this orbifold. For a kaleidoscopic orbifold, there is only one tile-1-transitive fundamental tiling, found by barycentric subdivision of the polygonal orbifold. For an orbifold with cone points or more complicated topology, there is usually more than one way to cut it open into a fundamental tile. A familiar euclidean example is that you can cut open the torus into a parallelogram or a hexagon.

Our example hyperbolic tiling has symmetry group *246. The orbifold is a triangle with angles π/2, π/4, and π/6. You can see that the bright red and blue chambers, joined together along their shared 2-edge, cover the orbifold.

The hexagon-square example tiling is found twice in the EPINET enumeration, because it is vertex-1-transitive and tile-2-transitive. Both paths begin with the tile-1-transitive fundamental *246 tiling. The first process then glues four fundamental tiles together around the π/2 vertex, to get our tiling by squares. As already explained above, the tiling by hexagons and squares is the dual of this tiling.

The second process avoids the duality operation, but involves a split and then two glues. The split operation adds a new edge from the π/2 vertex to a point on the opposite edge:

The next row of images shows the two different glue operations separately (left and center) followed by the double-glue (right). Notice that in making the double-glue, vertices of degree two are created and removed, so that the central 12-sided star becomes a hexagon.

Return to the EPINET mathematical background pages.