Main Results

1. The Undecidability Theorem. There is no algorithm for deciding whether or not an arbitrary body or set of bodies admits a tiling of S [Ber66].
2. The Extension Theorem (for ${\mathbb{E}}^n$
   ). Let A be any finite set of bodies, each homeomorphic to a closed n-ball. If A tiles regions that contain arbitrarily large n-balls, then A admits a tiling of ${\mathbb{E}}^n$
   . (These regions need not be nested, nor need any of the tilings of the regions be extendable!) The proof for n = 2 in [GS87] extends to Eⁿ with minor changes.
3. The Normality Lemma (for ${\mathbb{E}}^n$
   ). In a normal tiling, the ratio of the number of tiles that meet the boundary of a spherical patch to the number of tiles in the patch tends to zero as the radius of the patch tends to infinity. In fact, a stronger statement can be made: For s ∊ S let t(r, s) be the number of tiles in the spherical patch P(r, s). Then, in a normal tiling, for every x > 0,
   $$\underset{r\to \infty }{\lim }\frac{t\left(r+x,s\right)-t\left(r,s\right)}{t\left(r,s\right)}=0.$$

   
   The proof for n = 2 in [GS87] extends to ${\mathbb{E}}^n$
   with minor changes.
4. Euler’s Theorem for tilings of ${\mathbb{E}}^2$
   . Let $\mathcal{T}$
   be a normal tiling of ${\mathbb{E}}^2$
   , and let t(r, s), e(r, s), and v(r, s) be the numbers of tiles, edges, and vertices, respectively, in the circular patch P(r, s). Then if one of the limits $e\left(\mathcal{T}\right)={\lim }_{r\to \infty }e\left(r,s\right)/t\left(r,s\right)\text{ or }\upsilon \left(\mathcal{T}\right)={\lim }_{r\to \infty }\upsilon \left(r,s\right)/t\left(r,s\right)$
   exists, so does the other, and $\upsilon \left(\mathcal{T}\right)-e\left(\mathcal{T}\right)+1=0$
   . Like Euler’s Theorem for Planar Maps, on which the proof of this theorem is based, this result can be extended in various ways [GS87].
5. Voronoi Dual. Every Voronoi tiling has a Delaunay dual and conversely (see Figure 3.1.2) [Vor09].

Main Results

1. The Local Theorem. Let $\mathcal{T}$
   be a monohedral tiling of S, and for $P\in \mathcal{T}$
   , let S_i (P) be the subgroup of the symmetry group of P that leaves invariant Cⁱ (P), the i th corona of P. $\mathcal{T}$
   is isohedral if and only if there exists an integer k > 0 for which the following two conditions hold: (a) for all $P\in \mathcal{T}$
   , S _k−1(P) = S_k (P) and (b) For every pair of tiles P, P′ in $\mathcal{T}$
   , there exists an isometry γ such that γ(P) = P′ and γ(C^k (P)) = C^k (P′). In particular, if P is asymmetric, then $\mathcal{T}$
   is isohedral if and only if condition (b) holds for k = 1 [DS98].
2. A convex polytope is a parallelotope if and only if it is centrosymmetric, its faces are centrosymmetric, and its belts have lengths four or six. First proved by Venkov, this theorem was rediscovered independently by McMullen [Ven54, McM80].
3. The number |F| of faces of a convex parallelotope in ${\mathbb{E}}^n$
   satisfies Minkowski’s inequality, 2n ≤ |F| ≤ 2(2 ⁿ − 1). Both upper and lower bounds are realized in every dimension [Min97].
4. The number of faces of an n-dimensional stereohedron in ${\mathbb{E}}^n$
   is bounded. In fact, if a is the number of translation classes of the stereohedron in an isohedral tiling, then the number of faces is at most the Delaunay bound 2 ⁿ (1+a) − 2 [Del61].
5. Using a classification system that takes into account the symmetry groups of the tilings and their tiles, the combinatorial structure of the tiling, and the ways in which the tiles are related to adjacent tiles, Grünbaum and Shephard proved that there are 81 classes of isohedral tilings of ${\mathbb{E}}^2$
   , 93 classes if the tiles are marked (that is, they have decorative markings to express symmetry in addition to the tile shape) [GS77]. There is an infinite number of classes of isohedral tilings of ${\mathbb{E}}^n$
   , n > 2.
6. Anisohedral tiles exist in ${\mathbb{E}}^n$
   for every n ≥ 2 [GS80]. (The first example, given for n = 3 by Reinhardt [Rei28], was the solution to part of Hilbert’s 18th problem.) H. Heesch gave the first example for n = 2 [Hee35] and R. Kershner the first convex examples [Ker68].
7. Every n-parallelotope admits a lattice tiling. However, for n ≥ 3, there are nonconvex tiles that tile by translation but do not admit lattice tilings [SS94].
8. A lattice tiling of ${\mathbb{E}}^n$
   by unit cubes must have a pair of cubes sharing a whole face [Min07, Haj42]. However, a famous conjecture of Keller, which stated that for every n, any tiling of ${\mathbb{E}}^n$
   by congruent cubesmust contain at least one pair of cubes sharing a whole face, is false: for n ≥ 10, there are translation tilings by unit cubes in which no two cubes share a whole face [LS92].
9. Every linear expansive map that transforms the lattice ${\mathbb{Z}}^n$
   of integer vectors into itself defines a family of k-rep tiles; these tiles, which usually have fractal boundaries, admit lattice tilings [Ban91].

Open Problems

1. Which convex n-polytopes in ${\mathbb{E}}^n$
   are prototiles for monohedral tilings of ${\mathbb{E}}^n$
   ? This is unsolved for all n ≥ 2 (see [GS87] for the case n = 2; the list of convex pentagons that tile has not been proved complete). For higher dimensions, little is known; it is not even known which tetrahedra tile ${\mathbb{E}}^3$
   [GS80, Sen81].
2. Heesch’s Problem. Is there an integer k_n , depending only on the dimension n of the space S, such that if a body A can be completely surrounded k_n times by tiles congruent to A, then A is a prototile for a monohedral tiling of S? (A is completely surrounded once if A, together with congruent copies that have nonempty intersection with A, tile a patch containing A in its interior.) When $S={\mathbb{E}}^2$
   , k ₂ > 5. The body shown in Figure 3.2.5 can be completely surrounded three times but not four; William Rex Marshall and, independently, Casey Mann, found 4-corona tiles, and Mann 5-corona tiles [Man01]. This problem is unsolved for all n.
3. Keller’s conjecture is true for n ≤ 6 and false for n ≥ 10 (see Result 8 above). The cases n = 7, 8, and 9 are still open.
4. Do r-morphic tiles exist for every positive integer r? Fontaine and Martin have shown the answer is yes in ${\mathbb{E}}^2$
   for r ≤ 10 [FM84].
5. Find a good upper bound for the number of faces of an n-dimensional stereohedron. Delaunay’s bound, stated above, is evidently much too high; for example, it gives 390 as the bound in ${\mathbb{E}}^3$
   , while the maximal known number of faces of a three-dimensional stereohedron (found by P. Engel [Eng81]) is 38.
6. For monohedral (face-to-face) tilings by convex polytopes there is an integer k_n , depending only on the dimension n of S, that is an upper bound for the constant k in the Local Theorem [DS98]. Find the value of this k_n . For the Euclidean plane ${\mathbb{E}}^2$
   it is known that k ₂ = 1 (convexity of the tiles is not necessary) [SD98], but for the hyperbolic plane, k ₂ ≥ 2 [Mak92]. For ${\mathbb{E}}^3$
   , it is known that 2 ≤ k ₃ ≤ 5.

Classification of Periodic Tilings

The mathematical study of tilings (like most mathematical investigations) has been accompanied by the development and use of a variety of notations for classification of different “types” of tilings and tiles. Far from being merely names by which to distinguish types, these notations tell us the investigators’ point of view and the questions they ask. Notation may tell us the global symmetries of the tiling, or how each tile is surrounded, or the topology of its orbifold. Notation makes possible the computer implementation of investigations of combinatorial questions about tilings.

Periodic tilings are classified by symmetry groups and, sometimes, by their skeletons (of vertices, edges, …, (n−1)-faces). The groups are known as crystallographic groups; up to isomorphism, there are 17 in ${\mathbb{E}}^2$

and 219 in ${\mathbb{E}}^3$ . For ${\mathbb{E}}^2$ and ${\mathbb{E}}^3$ , the most common notation for the groups has been that of the International Union of Crystallography (IUCr) [Hah83]. This is cross-referenced to earlier notations in [Sch78]. Recently developed notations include Delaney-Dress symbols [Dre87] and orbifold notation for n = 2 [Con92, CH02] and for n = 3 [CDHT01].

Glossary

International symbol (for periodic tilings of ${\mathbb{E}}^{2}and{\mathbb{E}}^3$ )

:Encodes lattice type and particular symmetries of the tiling. In Figure 3.3.1, the lattice unit diagram at the right encodes the symmetries of the tiling and the IUCr symbol p31m indicates that the highest-order rotation symmetry in the tiling is 3-fold, that there is no mirror normal to the edge of the lattice unit, and that there is a mirror at 60° to the edge of the lattice unit. These symbols are augmented to denote symmetry groups of perfectly 2-colored tilings.

Delaney-Dress symbol (for tilings of Euclidean, hyperbolic, or spherical space of any dimension)

:Associates an edge-colored and vertex-labeled graph derived from a chamber system (a formal barycentric subdivision) of the tiling. In Figure 3.3.2, the nodes of the graph represent distinct triangles A, B, C, D in the chamber system, and colored edges (dashed, thick, or thin) indicate their adjacency relations. Numbers on the nodes of the graph show the degree of the tile that contains that triangle and the degree of the vertex of the tiling that is also a vertex of that triangle.

Orbifold notation (for symmetry groups of tilings of 2-dimensional surfaces of constant curvature)

:Encodes properties of the orbifold induced by the symmetry group of a periodic tiling of the Euclidean plane or hyperbolic plane, or a finite tiling of the surface of a sphere; introduced by Conway. In Figure 3.3.1, the first 3 in the orbifold symbol 3*3 for the symmetry group of the tiling indicates there is a 3-fold rotation center (gyration point) that becomes a cone point in the orbifold, while *3 indicates that the boundary of the orbifold is a mirror with a corner where three mirrors intersect.

See Table 3.3.1 for the IUCr and orbifold notations for ${\mathbb{E}}^2$

.

Isohedral tilings of ${\mathbb{E}}^2$

fall into 11 combinatorial classes, typified by the Laves nets (Figure 3.3.3). The Laves net for the tiling in Figure 3.3.1 is [3.6.3.6]; this gives the vertex degree sequence for each tile. In an isohedral tiling, every tile is surrounded in the same way. Grünbaum and Shephard provide an incidence symbol for each isohedral type by labeling and orienting the edges of each tile [GS79]. Figure 3.3.4 gives the incidence symbol for the tiling in Figure 3.3.1. The tile symbol a ⁺ a ⁻ b ⁺ b ⁻ records the cycle of edges of a tile and their orientations with respect to the (arrowed) first edge (+ indicates the same, − indicates opposite orientation). The adjacency symbol b ⁻ a ⁻ records for each different letter edge of a single tile, beginning with the first, the edge it abuts in the adjacent tile and their relative orientations (now − indicates same, + opposite). These symbols can be augmented to adjacency symbols to denote k-color symmetry groups. Earlier, Heesch devised signatures for the 28 types of tiles that could be fundamental domains of isohedral tilings without reflection symmetry [HK63]; this signature system was extended in [BW94].

Main Results

1. If a finite prototile set of polygons admits an edge-to-edge tiling of the plane that has translational symmetry, then the prototile set also admits a periodic tiling [GS87].
2. The number of symmetry groups of periodic tilings in ${\mathbb{E}}^n$
   is finite (this is a famous theorem of Bieberbach [Bie10] that partially solved Hilbert’s 18th problem: see also Chapter 62); the number of symmetry groups of corresponding tilings in hyperbolic n-space, for n = 2 and n = 3, is infinite.
3. Every k-isohedral tiling of the Euclidean plane, hyperbolic plane, or sphere can be obtained from a (k−1)-isohedral tiling by a process of splitting (splitting an asymmetric prototile) and gluing (amalgamating two or more equivalent asymmetric tiles adjacent in the tiling into one new tile) [Hus93]; there are 1270 classes of normal 2-isohedral tilings and 48,231 classes of normal 3-isohedral tilings of ${\mathbb{E}}^2$
   .
4. Classifying isogonal tilings in a manner analogous to isohedral ones, Grünbaum and Shephard have shown [GS78a] that there are 91 classes of normal isogonal tilings of ${\mathbb{E}}^2$
   (93 classes if the tiles are marked). Similarly [GS78b], there are 26 classes of normal tilings of ${\mathbb{E}}^2$
   for which the symmetry group acts transitively on the edges (30 if the tiles are marked); these tilings are called isotoxal . See also [GS87].
5. There are 88 combinatorial classes of periodic tilings of ${\mathbb{E}}^3$
   for which the symmetry group acts transitively on the faces of the tiling [DHM93].
6. For every k, the number of k-uniform tilings of ${\mathbb{E}}^2$
   is finite. There are 11 uniform tilings of ${\mathbb{E}}^2$
   (also called Archimedean , or semiregular ), of which 3 are regular. The Laves nets in Figure 3.3.3 are duals of these 11 uniform tilings [GS87, Sections 2.1, 2.2]. There are 28 uniform tilings of ${\mathbb{E}}^3$
   [Grü94] and 20 2-uniform tilings of ${\mathbb{E}}^2$
   [Krö69]; see also [GS87, Section 2.2]. In the hyperbolic plane, uniform tilings with vertex valence 3 and 4 have been classified [GS79].
7. In any equitransitive tiling of ${\mathbb{E}}^2$
   by convex polygons, the maximum number of edges of any tile is 66 [DGS87].
8. There are finitely many regular tilings of ${\mathbb{E}}^n$
   (three for n = 2, one for n = 3, three for n = 4, and one for each n > 4) [Cox63]. There are infinitely many normal regular tilings of the hyperbolic plane, four of hyperbolic 3-space, five of hyperbolic 4-space, and none of hyperbolic n-space if n > 4 [Sch83, Cox54].
9. If two orbifold symbols for a tiling of the Euclidean or hyperbolic plane look exactly the same except for the numerical values of their digits, which may differ by a permutation of the natural numbers (such as *632 and *532), then the number of k-isohedral tilings for each of these orbifold types is the same [BH96].
10. There is a one-to-one correspondence between perfect k-colorings of a free tiling and the subgroups of index k of its symmetry group. See [Sen79].

Open Problems

1. Does every convex pentagon that tiles ${\mathbb{E}}^2$
   admit a k-isohedral tiling for some k ≥ 1, and if so, is there an upper bound on k? (All pentagons known to tile the plane admit k-isohedral tilings, with k ≤ 3.)
2. Classify uniform tilings of the hyperbolic plane for the cases of vertex valences greater than 4.
3. Enumerate the uniform tilings of ${\mathbb{E}}^n$
   for n > 3. (Some uniform tilings for ${\mathbb{E}}^n$
   , n > 3, are discussed in [Joh04].)
4. Delaney-Dress symbols and orbifold notations have made progress possible on the classification of k-isohedral tilings in all three 2-dimensional spaces of constant curvature; extend this work to higher-dimensional spaces.

Main Results

1. Self-similar and projected tilings are repetitive (see [Sen95]).
2. Uniquely hierarchical tilings are nonperiodic (the proof given in [GS87] for n = 2 extends immediately to all n). Conversely, nonperiodic self-similar tilings have the unique composition property [Sol98].
3. For each complex Perron number λ there is a self-similar tiling with expansion λ [Ken95].
4. “Irrational” projected tilings are nonperiodic (see Chapter 62).
5. The prototile sets of certain irrational projected tilings can be equipped with matching rules so that all tilings admitted by the prototile set belong to a single local isomorphism class (see Chapter 62).
6. Mutual local derivability is an equivalence relation on the set of all tilings. The existence or nonexistence of hierarchical structure and matching rules is a class property [KSB93].
7. Certain convex biprisms admit only nonperiodic monohedral tilings of ${\mathbb{E}}^3$
   if no mirror-image copies of the tiles are allowed [Sch88]; see Figure 3.4.3. These tiles can be altered to produce nonconvex aperiodic prototiles for ${\mathbb{E}}^3$
   [Dan95].
8. The prototile set of every uniquely hierarchical tiling can be equipped with matching rules that force the hierarchical structure [Goo98].

Open Problems

Does there exist a prototile in ${\mathbb{E}}^2$

that is aperiodic? Does there exist a convex prototile for ${\mathbb{E}}^3$ that is aperiodic without restriction?

Surveys

The following surveys are useful, in addition to the references below.

• [GS87]: The definitive, comprehensive treatise on tilings of ${\mathbb{E}}^2$
  , state of the art as of the mid-1980s. All subsequent work (in any dimension) has taken this as its starting point for terminology, notation, and basic results. The Main Results of our Section 3.1 can be found here.
• [Joh04]: A comprehensive and detailed account of uniform polytopes and honeycombs in Euclidean and non-Euclidean spaces of n dimensions.
• [Moo97]: The proceedings of the NATO Advanced Study Institute on the Mathematics of Aperiodic Order, held in Waterloo, Canada in August 1995.
• [Sch93]: A contemporary survey of tiling theory, especially useful for its accounts of monotypic and other kinds of tilings more general than those discussed in this chapter.
• [Sch02]: A recent brief survey of tiling.
• [Sen95]: Chapters 5 – 8 form an introduction to the emerging theory of aperiodic tilings.
• [SS94]: This book is especially useful for its account of tilings in ${\mathbb{E}}^n$
  by clusters of cubes.

Related Chapters

• Chapter 15: Polyominoes
• Chapter 23: Voronoi diagrams and Delaunay triangulations
• Chapter 62: Crystals and quasicrystals