Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 34 (1993), No. 1, 87-118.

Tile-Transitive Partial Tilings of the Plane

Daniel H. Huson

Fakultät für Mathematik, Universität Bielefeld, Universitätsstraße, W-4800 Bielefeld

Abstract. There are 3 different kinds of periodic tile-transitive partial tilings of the plane; those having none, one or an infinite number of unbounded components. In each case all possible equivariant types can be enumerated. These results are obtained by using a generalization of the method of Delaney-Dress symbols.

1. Introduction

It is well-known that there exist precisely 93 equivariant types of tile-transitive tilings of the euclidean plane. From [11] follows that the number of equivariant types of “(discrete) periodic closed disk patterns” is 52.

Both of these results are special cases of the problem of classifying all possible equivariant types of periodic tile-transitive partial tilings of the plane, i.e. of such tilings that do not necessarily completely cover the plane.

In [7] and [9] Andreas Dress introduces the theory of Delaney symbols (or -more appropriately- Delaney-Dress symbols), which proves to be quite a successful approach to classification problems concerning periodic tilings. For example, using algorithms described in [6] and [15], all tile-k-transitive tilings of the plane, the sphere or the hyperbolic plane can be systematically enumerated. In this paper we discuss how to adapt the theory of Delaney-Dress symbols to partial tilings of the plane.

In Section 2 we define periodic tile-transitive partial tilings and discuss some of their properties. In Section 3 we prove that there exist three different families of periodic tiletransitive partial tilings, which we call patchy, stripey and net-like.

We investigate the relationship between such tilings and Delaney-Dress symbols in Section 4. This is followed by a detailed inspection of the net-like, patchy, and finally, the stripey tile-transitive partial tilings, in Sections 5, 6 and 7, respectively.

The main result of this paper is that there exist three different families of periodic tile-transitive partial tilings; those having none, one or an infinite number of unbounded components. Furthermore, there exist precisely 152+52 types of such patchy, 248 types of stripey and 1028+93 types of net-like periodic tile-transitive partial tilings of the plane, respectively.

This paper is is based on my Ph. D. thesis [13]. I would like to thank my Ph. D. advisor, Andreas Dress.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1993 Heldermann Verlag, Berlin

2. Periodic Tile-Transitive Partial Tilings

A system T = {t_{1}, t_{2}, …} of subsets t_{i} ⊆ ^{2} of the euclidean plane, called tiles, is called a tiling (of the plane) if it satisfies:

(T1) Every tile is a topological disk.

(T2) The intersection of any two different tiles is either empty, a point or an arc. (T3) The tiles are uniformly bounded, i.e. there exist two positive numbers r, R such

that each tile contains a disk of radius r and is contained in a disk of radius R. (T4) The tiling covers the plane, i.e. ⋃_{t∈T} t = ^{2}.

By properties (T2) and (T3), all tilings considered in this paper are so-called normal tilings.

For a tiling T , the intersection of a finite number of distinct tiles is either empty, a point called a vertex or an arc called an edge. The boundary of any tile t ∈ T is divided into a number of parts (at least two) by vertices, each such arc being an edge of the tiling.

We called any system T = {t_{1}, t_{2}, …} of subsets of the plane satisfying conditions (T1)—(T3), but not necessarily (T4), a partial tiling. For any such partial tiling T let T denote the support of T , i.e. T := ⋃_{t∈T} t and let K denote the closure of the complement of T, i.e. K := \overline{^{2} \ T} = ⋃_{H∈K} H, where K := \{\overline{H} ⊂ ^{2} | H ∈ π_{0}( ^{2} \ K )\} is the set of all (closures of) connected components of the complement of T. Finally, let K_{∞} denote the set of all unbounded elements in K. See Figure 1.

Figure 1a: A net-like partial tiling

Figure 1b: A stripey partial tiling

Figure 1c: A patchy partial tiling

Let T be a partial tiling. If t ∈ T doesn’t intersect any other tile in T , then the boundary ∂t of t is said to contain neither vertices nor edges. Otherwise, call any point in ∂t that lies in the intersection of at least three tiles, or at least two tiles and K, a vertex. The edges (in ∂t) are defined as the closures of the connected components of the set that one obtains from ∂t by removing all the contained vertices. Following V. Klee, a vertex or an edge is called exposed if it lies in K and protected otherwise.

The degree of a vertex v is the number of edges incident to v (where “loops” are counted twice) and the degree of a tile t is the number of edges contained in the boundary of t. Note that an edge always lies in either exactly two tiles or exactly one tile and K. Furthermore, an exposed edge may be a loop, i.e. a simple closed curve that is incident to precisely one vertex.

Let T be a partial tiling and let Γ be a discrete group of isometries of the euclidean plane. If T is Γ -invariant, i.e. if T = γT := {γt | t ∈ T } for all γ ∈ Γ, then we call the system (T , Γ) an equivariant partial tiling. Such a system is called tile-transitive, if for any two tiles t, t′ ∈ T there exists a symmetry γ ∈ Γ such that γt = t′. If Γ is a crystallographic group, i.e. if Γ contains translations in two linearly independent directions, then (T , Γ) is called periodic.

Let (T , Γ) be a periodic equivariant partial tiling. We will make use of the following notation:

Γ̄ := {γ ∈ Γ | γ is a translation } ≤ Γ
Γ_{H} := {γ ∈ Γ | γH = H}
Γ̄_{H} := Γ̄ ∩ Γ_{H}

for any set H ∈ T ∪ K.

Two equivariant partial tilings (T , Γ) and (T′, Γ′) are called equivariantly equivalent, if there exists a homeomorphism ϕ : ^{2} → ^{2} with ϕT = T′ and Γ′ = ϕΓ ϕ^{−1}. We intend to enumerate all possible equivariant types of periodic tile-transitive partial tilings of the plane.

From now on we will refer to equivariant partial tilings simply as partial tilings. Remember, however, that an equivariant tiling is not plainly a family of tiles, but rather a system consisting of a set of tiles and a prescribed symmetry group.

3. Patchy, Stripey and Net-Like Tilings

In this Section we investigate the basic properties of a periodic tile-transitive partial tiling (T , Γ). Let us first look at the bounded elements of K.

Theorem 3.1 Let (T , Γ) be a periodic tile-transitive partial tiling. Every bounded set L ∈ K is a topological disk.

Proof. For a compact set X ⊆ ^{2} , let D(X) denote its diameter, i.e. the maximal distance between any two points in X. For a Jordan curve J, let int(J) denote its interior region.

Let L ∈ K \ K_{∞}. It suffices to show that for any point p ∈ ∂L, the set ∂L \ {p} is connected. Assume that ∂L \ {p} is disconnected for some p ∈ ∂L. Because L is bounded, there exists a Jordan curve J ⊆ ∂L with L ⊆ J ∪ int(J). Let J′ ⊆ ∂L be a Jordan curve with J ∩ J′ ⊆ {p} that has maximal diameter. Let t ∈ T , or t′ ∈ T , be a tile that intersects J, or J′, respectively, in at least two points. Note that t ≠ t′. For any Jordan curve C ⊆ ∂T that intersects t′ in at least two points we have

D(C) ≤ D(J′) < D(J)

because C, J′ ⊆ int(J) ∪ {p}. However, the existence of an isometry γ ∈ Γ with γt = t′ implies that there exists a Jordan curve γJ in ∂T of diameter D(γJ) = D(J) that intersects t′ in at least two points, a contradiction.

Let (T , Γ) be a periodic tile-transitive partial tiling. If H ⊆ T is a connected component of T , then we call (T_{H}, Γ_{H}) a component of (T , Γ), with T_{H} := {t ∈ T | t ∩ H ≠ ∅} = {t ∈ T | t ⊆ H}.

Theorem 3.2 Let (T , Γ) be a periodic tile-transitive partial tiling. Exactly one of the following cases holds (see Figure 1):

(1) The tiling is net-like: It possesses exactly one unbounded connected component. All components of the complement are (bounded) topological disks (“holes”).

(2) The tiling is stripey: It consists of an infinite number of unbounded components (“stripes”), all invariant under translations in exactly one same direction. The complement of the tiling possesses an infinite number of unbounded components, which are all invariant under precisely the same translations as the components of the tiling.

(3) The tiling is patchy: It consists of an infinite number of bounded components (“patches”), all surrounded by the same (and only) unbounded component of the complement.

To prove this result, let us first show two Lemmas on “crystal-structures”. A system (C, Γ) consisting of a connected set C ⊆ ^{2} and a group Γ of symmetries of C is called a connected (2-dimensional) crystal-structure if Γ is a discrete group of translations in two linearly independent directions, i.e. a crystallographical group of type p1. If Γ is a discrete group of translations in one direction, i.e. a frieze group of type p111, then (C, Γ) is called a connected rod-structure (compare [1]).

Lemma 3.3 Let (C, Γ) be a connected crystal-structure. Every connected component of 2 \ C is bounded.

Proof. Let γ ∈ Γ be a non-trivial translation and p_{0} ∈ C. Define p_{i} := γ^{i}p_{0} and α_{i} := γ^{i}α_{0}, where α_{0} ⊂ C denotes an arc joining p_{0} and p_{1}. Let D denote the maximal distance between two points in α_{0}. The curve α := ⋃_{i∈} α_{i} lies in an infinite strip of width D and partitions the plane into two unbounded regions. Let γ′ ∈ Γ be a translation not parallel to γ. The set A := ⋃_{j∈} (γ′)^{j}α partitions the plane into an infinite number of unbounded regions, each contained in an infinite strip of width d + D (where d is the distance between p_{0} and γ′p_{0}). Note that the strips are all parallel.

The same construction, but starting with γ′ and then applying γ, yields a second such set A′. It now follows from γ ∦ γ′ that the intersection of any two components of ^{2} \ A and ^{2} \ A′ is bounded, and hence, any component of ^{2} \ C ⊂ ( ^{2} \ A) ∩ ( ^{2} \ A′) is also bounded.

This result and similar arguments imply:

Lemma 3.4 The intersection of any two connected crystal-structures, or a connected crystal-structure and a connected rod-structure, is non-empty. The intersection of any two connected rod-structures is either non-empty, or the translational directions of the two are parallel.

Proof of Theorem 3.2. Let H be a connected component of T. Consider the (induced) stabilizer group Γ_{H}. There are precisely three possible cases:

(1) The group Γ_{H} contains translations in two linearly independent directions. In this case the system (H, Γ̄_{H}) is a connected crystal-structure. The Lemmas imply that all connected components of the complement of the tiling are (bounded) topological disks. Furthermore, tile-transitivity implies H = T.

(2) The group Γ_{H} contains translations in precisely one direction. Note that then all translations (in Γ) in that direction must lie in Γ_{H}. Let γ ∈ Γ̄ be a translation not contained in Γ_{H}, and therefore, not parallel to any translation in Γ_{H}.

Then, the system (γ^{i}H, γ^{i}Γ̄_{H}(γ^{i})^{−1}) is a rod-structure for every i ∈ and one has γ^{i}H ∩ γ^{j}H = ∅ whenever i ≠ j. If we now assume that γ was chosen as a (non-trivial) translation of minimal displacement, then any two sets γ^{i}H and γ^{i+1}H are separated by an unbounded connected set L ∈ K_{∞}.

We claim that (L, Γ̄_{L}) is a rod-structure. To see why this is true, let E_{L} denote the set of all edges of T that lie in ∂L. The tiling T is uniformly bounded, so #E_{L} = ∞. On the other hand, as the boundary of a tile contains only a finite number of edges and Γ operates transitively on T , it follows that the number of transitivity classes of edges is finite. The only elements of Γ that have infinite orbits are translations (and glide-reflections). So there must exist a non-trivial translation γ ∈ Γ̄ with γ(E_{L}) = E_{L}. But then γL = L and so Γ̄_{L} ≠ ∅.

(3) The group Γ_{H} does not contain translations. In this case every component of T must be bounded and the complement of T must contain at least one unbounded component L ∈ K_{∞}. Again, ∂L contains an infinite set of edges partitioned into a finite number of Γ -orbits. In this case Γ_{L} must contain translations in two linearly independent directions, and this implies K_{∞} = {L}.

4. Delaney-Dress Symbols of Partial Tilings

As we will see, the Delaney-Dress symbol of a periodic 2-dimensional tiling is a finite, edge-colored graph, together with two functions defined on the vertices of the graph, that encode the tiling up to equivariant equivalence. The relationship between such tilings and their symbols has been studied in great detail, see the References. In this Section we discuss how one can define the symbol of a periodic tile-transitive partial tiling. First we recall the definition of the Delaney-Dress symbol for a 2-dimensional tiling.

Let (T , Γ) be an equivariant tiling that covers the euclidean plane, the sphere or the hyperbolic plane. Let us assume that the tiling is tile-k-transitive, i.e. that the tiling possesses precisely k ∈ transitivity classes of tiles with respect to the symmetry group Γ. We define the chamber system C_{T} of T via formal barycentric subdivision in the usual way: For every vertex, edge and tile choose an interior point, called a 0-, 1- or 2-center, respectively. Then, for every tile A ∈ T , join its 2-center to each 0- and 1-center contained in the boundary of the tile, by pairwise non-intersecting edges. These “triangles” are called chambers and they make up the set C_{T}. Each chamber has exactly three vertices, namely a 0-, a 1- and a 2-center. The edge opposite the i-center of a chamber is called an i-edge.

Note that for every chamber C ∈ C_{T} and any i ∈ {0, 1, 2} there exists exactly one chamber C′ ∈ C_{T} (with C′ ≠ C) such that C and C′ have the same i-edge. We say that C and C′ are i-adjacent or i-neighbors and define a permutation σ_{i} : C_{T} → C_{T} that maps every C ∈ C_{T} onto its i-neighbor C′ =: Cσ_{i} (so C′ = Cσ_{i} implies C = C′σ_{i}).

Note that the chamber system C_{T} can always be constructed in a way compatible with the action of Γ on T . We call two chambers C, C′ ∈ C_{T} equivalent whenever there exists a symmetry γ ∈ Γ with γ · C = C′. The assumption that (T , Γ) is tile-k-transitive implies that the set of all equivalence classes (or Γ -orbits) in C_{T} is finite. This set is denoted by D := D_{(T ,Γ)} = Γ \ C_{T}.

Consider C := C_{T}. Any symmetry γ ∈ Γ necessarily maps i-neighbors onto ineighbors, hence the operation of σ_{i} commutes with Γ on C, for any i ∈ {0, 1, 2}. Thus we can introduce the concept of i-adjacency of Γ -orbits. The permutation σ_{i} : D → D maps every D ∈ D onto its i-neighbor D′ =: Dσ_{i}, with i ∈ {0, 1, 2}.

The set D and the maps σ_{0}, σ_{1}, σ_{2} define a finite, connected 3-colored graph with node set D and set of colored edges E := {({D, D′}, i) | D, D′ ∈ D and Dσ_{i} = D′}, where the component i ∈ {0, 1, 2} of an edge ({D, D′}, i) is called its color. (Note that D = Dσ_{i} is possible; the arising edge is a loop. Note also that D and D′ can be connected by more than one edge.) This Delaney-Dress graph (D, E) makes up the first part of the Delaney-Dress symbol corresponding to (T , Γ). To complete the definition, let us introduce functions m_{ij} : D → for 0 ≤ i < j ≤ 2 with

m_{ij}(D) := min{m ∈ | C(σ_{i}σ_{j})^{m} = C for any C ∈ D}.

It is well worth mentioning that these functions have the following geometric interpretations: The value m_{01}(D) equals the number of edges of any tile that contains a chamber C ∈ D ∈ D. Similarly, the value m_{12}(D) equals the number of edges incident to any vertex that is adjacent to a chamber C ∈ D ∈ D. Finally, m_{02}(D) = 2, because this value equals the number of faces incident to any edge adjacent to C ∈ D ∈ D.

We now come to the formal definition of the symbol of a periodic 2-dimensional tiling. A system (D; m) := ((D, E); m_{01}, m_{12}, m_{02}) consisting of a finite, connected Delaney-

Dress graph D := (D, E) and functions m_{01}, m_{12}, m_{02} : D → , is called a (2-dimensional) Delaney-Dress symbol if and only if for all D ∈ D and 0 ≤ i < j ≤ 2 the following hold:

(1) m_{ij}(D) = m_{ij}(Dσ_{i}) = m_{ij}(Dσ_{j}),

(2) D(σ_{i}σ_{j})^{m_{ij}(D)} = D(σ_{j}σ_{i})^{m_{ij}(D)} = D,

(3) m_{02}(D) = 2 and m_{12}(D) ≥ 3. Two Delaney-Dress symbols (D; m) and (D′; m′) are called isomorphic if and only if

there exists a bijection π : D → D′ with (πD)σ_{k} = π(Dσ_{k}) and m′_{ij}(πD) = m_{ij}(D) for all D ∈ D, 0 ≤ k ≤ 2 and 0 ≤ i < j ≤ 2. It is not too difficult to prove the following ([8]):

Lemma 4.1 Two tilings (T , Γ) and (T′, Γ′) are equivariantly equivalent if and only if the corresponding Delaney-Dress symbols (D; m) and (D′; m′) are isomorphic.

Proof. It is obvious that isomorphic symbols give rise to equivalent tilings. Now assume that (T , Γ) and (T′, Γ′) are two periodic tile-transitive partial tilings with Delaney-Dress symbols (D; m) and (D′; m′), equivariantly equivalent via an homeomorphism ϕ : T → T′. It follows that the corresponding chamber systems C and C′, being barycentric subdivisions, are topologically equivalent. Furthermore, ϕ induces a one-to-one correspondence between Γ -orbits in C and Γ′-orbits in C′, which commutes with σ_{i} (i ∈ {0, 1, 2}), because Γ′ = ϕΓ ϕ^{−1}. Hence both arising symbols are isomorphic.

Consider a Delaney-Dress graph (D, E). If we delete all edges of color k in the graph, then we obtain a two-colored graph D_{ij}, which we call the {i, j}-subgraph of D, with {i, j, k} = {0, 1, 2}. The connected components of D_{ij} are called the {i, j}-orbits of D. An {i, j}-orbit O is called a cycle, if Dσ_{i} ≠ D and Dσ_{j} ≠ D for all D ∈ O, and a chain, otherwise. Any {i, j}-orbit O with 0 ≤ i < j ≤ 2 is also called a 2-color-orbit. It is a nice fact that the different equivalence classes of vertices, edges and tiles of a periodic tiling correspond directly to the different {1, 2}-, {0, 2}- and {0, 1}-orbits of the associated Delaney-Dress symbol, respectively.

How does one adjust the above definition of a Delaney-Dress symbol to periodic tiletransitive partial tilings? As we have seen, periodicity and tile-transitivity imply that such a tiling is made up of (one or infinitely many) equivalent components. We intend to define the symbol for any such component. The important question is how to treat the components of the complement of such a periodic tile-transitive partial tiling?

Let (T , Γ) be a periodic tile-transitive partial tiling and let T_{H} ⊆ T be the set of all tiles that make up a given connected component H of T. Let K_{H} = {L ∈ K \ K_{∞} | L ∩ H ≠ ∅} be the set of all bounded connected components of the complement of T that are adjacent to tiles in T_{H}.

Note that if L ∈ K_{H}, then ∂L∩∂H ≠ ∅ and therefore ∂L ⊆ ∂H, since ∂L is connected. Hence, all elements of K_{H} can be considered as additional tiles, which we call holes. To define the chamber system C := C_{(T_{H},Γ_{H})} of the component (T_{H}, Γ_{H}) of a periodic tiletransitive partial tiling we begin as discussed above, by first subdividing all tiles and all holes. Let C_{tiles} and C_{holes} denote the sets of the two kind of chambers that arise. We can define the 0-, 1-, and 2-neighbor relationships for all chambers in C_{tiles} ∪ C_{holes} as above, expect for those chambers that are adjacent to some unbounded set L ∈ K_{∞}. The latter unprotected chambers all lie in C_{tiles} and for these we must now discuss how to define σ_{2}.

With each unprotected chamber C ∈ C_{tiles} associate a “formal” chamber C′ and set Cσ_{2} := C′. Let C_{∞} be the set of all such formal chambers. The chamber system of (T_{H}, Γ_{H}) is the set C = C_{tiles} ˙∪C_{holes} ˙∪C_{∞}. Now, for every formal chamber C′ ∈ C_{∞}, we set C′σ_{0} := C′σ_{2}σ_{0}σ_{2} ∈ C_{∞} and C′σ_{1} := Cσ_{2} ∈ C_{∞}, where C ∈ C_{tiles} is the first chamber that one encounters when going around a small circle around the 0-vertex of C′σ_{2} ∈ C_{tiles} in the orientation defined by leaving the chamber C′σ_{2} across its 2-edge.

Now that we have defined the chamber system C and the i-neighbor relationships we obtain a finite Delaney-Dress graph (D, E) by considering Γ_{H}-orbits on C. The partitioning of C carries over to D as follows:

D = D_{tiles} ˙∪D_{holes} ˙∪D_{∞}.

The functions m_{ij} are defined as above, except that there are two special cases: If the tiling is stripey, then every connected component of the boundary of any set L ∈ K_{∞} is unbounded. In this case one must set m_{01}(D) = ∞ for all D ∈ D_{∞}. If the tiling is patchy, then every connected component of the boundary of the one set L ∈ K_{∞} is bounded, and we must define m_{01}(D) = N for all D ∈ D_{∞}, where N denotes the number of edges of the tiling that lie in the considered component of the boundary of L.

We now state the formal definition of a “PTTP Delaney-Dress symbol”, where PTTP stands for “periodic tile-transitive partial”. A system (D; m) := ((D, E); m_{01}, m_{12}, m_{02}) consisting of a finite, connected Delaney-Dress graph D := (D, E), with a partitioning D = D_{tiles} ˙∪D_{holes} ˙∪D_{∞}, and functions m_{01}, m_{12}, m_{02} : D → ∪ {∞}, is called a PTTP Delaney-Dress symbol if for all D ∈ D and 0 ≤ i < j ≤ 2 the following hold:

(DS1) m_{ij}(D) = m_{ij}(Dσ_{i}) = m_{ij}(Dσ_{j}), (DS2) D(σ_{i}σ_{j})^{m_{ij}(D)} = D(σ_{j}σ_{i})^{m_{ij}(D)} = D if m_{ij}(D) < ∞, (DS3) m_{02}(D) = 2 and m_{12}(D) ≥ 3, (DS4) (D_{holes} ∪ D_{∞})σ_{2} ⊆ D_{tiles}, (DS5) D_{tiles}σ_{k} = D_{tiles}, D_{holes}σ_{k} = D_{holes} and D_{∞}σ_{k} = D_{∞} for k ∈ {0, 1}, (DS6) D_{tiles} consists of precisely one {0, 1}-orbit.

Note that m_{ij}(D) < ∞ if D ∉ D_{∞} or (i, j) ≠ (0, 1). For an example, see Figure 2.

Figure 2: The Delaney-Dress graph of a component of a partial tiling (T_{H},Γ_{H}). The component consists of three tiles, which are shaded grey. The stabilizer group Γ_{H} is a rotation group of type C3. The Delaney-Dress graph has 12 vertices, drawn here as circles labeled A,B,...,L. Note that D_{tiles}={A,...,H}, D_{holes}={I,J} and D_{∞}={K,L}. The edges of the graph are depicted as heavy lines, each labeled 0, 1, or 2, indicating the edge’s color. In this example we have m_{01}(D)=4 for all D∈D_{tiles} and m_{01}(D)=3 for all D∈D_{holes}∪D_{∞}. Furthermore, m_{12}(D)=3 for all D∈D.

Two PTTP Delaney-Dress symbols (D; m) and (D′; m′) are called isomorphic if and only if there exists a bijection π : D → D′ with

πD_{tiles} = D_{tiles}, πD_{holes} = D_{holes}, πD_{∞} = D_{∞},

(πD)σ_{k} = π(Dσ_{k}) and m′_{ij}(πD) = m_{ij}(D)

for all D ∈ D, 0 ≤ k ≤ 2 and 0 ≤ i < j ≤ 2.

Similar to Lemma 4.1, we have:

Lemma 4.2 Two components (T_{H}, Γ_{H}) and (T′_{H′}, Γ′_{H′}) of periodic tile-transitive regular tilings are equivariantly equivalent if and only if the two associated PTTP Delaney-Dress Symbols (D; m) and (D′; m′) are isomorphic.

Finally, we need to introduce a number of different basic concepts associated with Delaney-Dress symbols in general (not just PTTP symbols). Let (D; m) be a (PTTP or not) Delaney-Dress symbol. Define

r_{ij}(D) := min{n ∈ | D(σ_{i}σ_{j})^{n} = D}

for all D ∈ D and 0 ≤ i < 2 ≤ 2. Note that (DS2) implies r_{ij}(D) | m_{ij}(D) and it is also clear that r_{ij} is constant on \{i, j\}-orbits. We call the map v_{ij}(D) := \frac{m_{ij}(D)}{r_{ij}(D)} the branching number map. It turns out that the branching number v_{ij}(D ∈ O) of an {i, j}-orbit O equals the rotational order of the stabilizer group of the corresponding vertex, edge or tile of the associated tiling (depending on whether {i, j} = {1, 2}, {0, 2} or {0, 1}, respectively). An {i, j}-orbit O is said to have a trivial branching number, if v_{ij}(D ∈ O) = 1.

For any Delaney-Dress symbol (D; m) we call

K_{(D;m)} := ∑_{D∈D}(\frac{1}{m_{01}(D)} + \frac{1}{m_{12}(D)} + \frac{1}{m_{02}(D)} − 1)

the curvature of the symbol and

χ(D) := ∑_{D∈D}(\frac{1}{r_{01}(D)} + \frac{1}{r_{12}(D)} + \frac{1}{r_{02}(D)} − 1)

is called the Euler characteristic of the symbol. A rather long but straight forward calculation shows that this number indeed coincides with the usual Euler characteristic of the so-called topological realization of the given Delaney-Dress graph.

A Delaney-Dress symbol (D; m) is called orientable, if one can define a map ϕ : D → {−1, +1} such that ϕ(Dσ_{i}) = −ϕ(D) for all D ∈ D and i ∈ {0, 1, 2}. Now assume (D; m) encodes a tiling (T , Γ). It can be shown that (D; m) is orientable if and only if Γ consists of orientation-preserving symmetries only. If Γ contains orientation-reversing symmetries, then the following construction yields the Delaney-Dress symbol of the equivariant tiling (T , Γ′) that one obtains from (T , Γ) by removing the orientation reversing symmetries from Γ: Set D′ := D × {−1, +1} and define (D, ϵ)σ_{i} := (Dσ_{i}, −ϵ) for all D ∈ D, ϵ ∈ {−1, +1} and i ∈ {0, 1, 2}. Set m′_{ij}((D, ϵ)) := m_{ij}(D) for all D ∈ D, ϵ ∈ {−1, +1} and 0 ≤ i < j ≤ 2. We call (D′; m′) the oriented covering of (D; m).

A Delaney-Dress symbol is called fixed-point-free, if Dσ_{i} ≠ D for all D ∈ D and i ∈ {0, 1, 2}.

The following Lemma is easy, but tedious to prove:

Lemma 4.3 Let (D; m) be a non-orientable Delaney-Dress symbol and (D′; m′) its oriented covering. Then (D′; m′) fulfills conditions (DS1)–(DS5), but not necessarily (DS6). Furthermore,

K_{(D′;m′)} = 2K_{(D;m)} and χ(D′) = 2χ(D).

In the following we will not distinguish between Delaney-Dress symbols and PTTP Delaney-Dress symbols. This should not lead to confusion.

5. Net-Like Partial Tilings

Through out this Section we will assume that all consider partial tilings (T , Γ) are periodic tile-transitive partial tilings with K_{∞} = ∅. We will refer to them as net-like tilings.

First let us state an important result that holds for tile-k-transitive tilings that cover the plane. This theorem is due to A. Dress, see [7] and [8]. By our definition in Section 1, the tiles of a tiling are assumed to be topological disks. For the following result, however, we need to allow the sightly more general non-disk tiles which arise from disk-tiles when the boundary of a tile is permitted to self-intersect in vertices and edges, see [3]. For an algorithm that can decide whether a given Delaney-Dress symbol encodes non-disk tiles, see [15].

Theorem 5.1 A (2-dimensional) Delaney-Dress symbol (D; m) corresponds to a tiling of the euclidean plane if and only if K_{(D;m)} = 0. (The tiling possibly contains non-disk tiles.)

Proof. The original (unpublished) proof due to A. Dress involves considering 17 different cases, one for each possible type of crystallographic symmetry group. Recently it has become clear that the Theorem also follows from the fact that every 2-dimensional Delaney-Dress symbol (D; m) with curvature K_{(D;m)} is essentially a 2-dimensional orbifold with Euler characteristic K_{(D;m)}, as defined by W. Thurston. According to W. Thurston, every “good”, connected, closed 2-orbifold with Euler characteristic > 0, 0 or < 0, is spherical, Euclidean, or hyperbolic, respectively, see [16], pg. 91. There are exactly four families of 2-orbifolds that are not “good”, i.e. that are not globally the orbit space of some symmetry-group, see [16], pg. 88. These are precisely the cases characterized by the integerity condition mentioned in Section 6.

Let (T , Γ) be a net-like tiling. Theorem 3.1 states that every set L ∈ K is a topological disk. So (T ∪ K, Γ) is obviously a tile-k-transitive tiling that covers the plane, with k ∈ , having the following properties:

(1) The symmetry group Γ operates transitively on T .

(2) The symmetry group Γ partitions K into precisely k − 1 ≥ 0 different Γ -transitivity classes. We characterize the Delaney-Dress symbols associated with such tilings in the follow-

ing result, see [4].

Theorem 5.2 Let (D = D_{tiles}∪D_{holes}∪D_{∞}; m) be a Delaney-Dress symbol with D_{tiles} ≠ ∅. There exists a net-like tiling (T , Γ) that is associated with (D; m) if and only if the following conditions hold:

(N1) D_{∞} = ∅,

(N2) ∞ > m_{01}(D) ≥ 3 if D ∈ D_{tiles} and ∞ > m_{01}(D) ≥ 2 if D ∈ D_{holes}, (N3) K_{(D;m)} = 0.

Proof. Condition (N1) reflects K_{∞} = ∅. Conditions (N2) corresponds to the fact that tiles in T (or K) must contain at least two (or three, respectively) edges in their boundary. The condition (N3) ensures that the associated tiling can be realized in the euclidean plane.

The following result was established in [4]:

Lemma 5.3 There exist only a finite number of Delaney-Dress symbols (D = D_{tiles} ∪ D_{holes} ∪ D_{∞}; m) that satisfy conditions (N1)—(N3). For these we have #D ≤ 36.

This high bound for the maximal size of a Delaney-Dress symbol of a net-like tiling makes a brute-force approach to the classification of all possible symbols impracticable. Hence in this paper we discuss a more direct approach. The idea is to use geometric algorithms to “construct” rather than “find” all feasible symbols. See [15] for a very similar discussion.

Let (T , Γ) be a net-like partial tiling. If K = ∅, then T covers the plane and (T , Γ) belongs to one of the well-known 93 equivariant types of tile-transitive tilings of the plane. We call such net-like tilings simple. The Delaney-Dress symbols of all such tilings were classified in [10].

In the following we will show that all net-like tilings can be obtained from the 93 types of simple ones by systematic application of two geometric operations, called vertex truncation and edge-contraction. We will discuss the operations geometrically in terms of tilings and tiles. For a formulation of both operations in terms of Delaney-Dress symbols, see [14]. The latter discussion leads to algorithms that have been implemented on a computer and that have been used to obtain the complete classification of the net-like tilings.

Algorithm 5.4 (Vertex-Truncation) Let (T , Γ) be a net-like tiling and let v be a protected vertex of T , i.e. with v ∉ K. Let U ⊂ ^{}be a small neighborhood around v that intersects no other vertex and only such edges and tiles that are incident to v. The intersection with any of the latter is assumed to be connected. Furthermore, assume that γU = U or γU ∩ U = ∅ for every γ ∈ Γ. Then the system T′ := {t \ ⋃_{γ∈Γ} γU | t ∈ T } is a Γ -invariant net-like tiling with K′ = K ∪ {γU | γ ∈ Γ }. We say that (T′, Γ) can be derived from (T , Γ) by (equivariant) vertex-truncation. See Figure 3.

Algorithm 5.5 (Edge-Contraction) Let (T , Γ) be a net-like tiling and let e be a protected edge of T . Furthermore, assume that at least one of the two vertices incident to e is unprotected, with degree greater than 3. Call this vertex v and let w be the other vertex incident to e. Note that v ≠ w. Assume that the number of edges incident to v, say, that are equivalent to e, is one, then Γ_{v} ≤ Γ_{e}. If Γ_{e} ≤ Γ_{w}, then we can “move” v along e to w (bending other edges incident to v), thus contracting e to the point w. If Γ_{w} ≤ Γ_{e},

Figure 3: (Equivariant) vertex-truncation of the vertex v in the left-hand tiling yields the right-hand tiling

Γ_{w} ≠ Γ_{e}, then e has a unique Γ_{e}-fixed-point x, and we can move both v and w along e to x (again bending incident edges), thus contracting e to x. The conditions fulfilled by v insure that this can be done to every edge e′ ∈ Γ e. We thus obtain a new net-like partial tiling (T′, Γ) and say that it can be derived from (T , Γ) by (equivariant) edge-contraction. See Figure 4.

Figure 4: (Equivariant) edge-contraction of the edge e in the left-hand tiling yields the right-hand tiling

We can now state an important observation.

Theorem 5.6 If (T′, Γ) is a net-like tiling then there exists a finite sequence of net-like tilings

(T , Γ) = (T_{0}, Γ), (T_{1}, γ), …, (T_{p}, Γ), …, (T_{p+q}, Γ) = (T′, Γ)

with the properties (1) (T , Γ) is a simple net-like tiling,

(2) (T_{i+1}, Γ) can be derived from (T_{i}, Γ) by vertex-truncation (0 ≤ i < p),

(3) (T_{i+1}, Γ) can be derived from (T_{i}, Γ) by edge-contraction (0 ≤ i < q).

Proof. Given a net-like tiling (T′, Γ). Let v be a unprotected vertex with degree 3. Let k ∈ K′ be a hole incident to v. Let e and e′ be the two adjacent edges of k that meet at v. By definition of a hole, both edges lie between k and some tile. Hence, starting at v we can “zip-up” the edges e and e′ along a short distance and thus push v out of the boundary of k, creating a new vertex in the boundary of k, which has degree 3. This operation is precisely the reversion of edge-contraction. Applying it precisely q times, where q is the number of non-equivalent unprotected vertices of degree greater than 3, yields a net-like tiling for which every unprotected vertex has degree 3.

Now, given a net-like tiling (T′, Γ) with the property that every unprotected vertex has degree 3. We can obtain a simple net-like tiling (T , Γ) by “dividing” each hole k ∈ K′ among the tiles of T′ that share an edge with k, in a way compatible with the operation of Γ. One way to do this is to consider a Γ -invariant barycentric subdivision of T′. We “glue” each pair of chambers in k that are incident to an edge e of k to the tile that lies on the other side of e. The fact that all unprotected vertices have degree 3 implies that vertices of degree 2 cannot arise. This operation is precisely the reversion of vertextruncation. Applying it precisely p times, where p is the number of non-equivalent holes, yields a simple net-like tiling.

One can obtain a complete classification of all possible equivariant types of net-like tilings in the following three steps:

(1) Produce the complete list of 93 Delaney-Dress symbols that encode simple net-like tilings (or isohedral tilings that cover the plane), as in [10] or [15].

(2) For every symbol listed in (1), apply vertex-truncation in all possible ways. Discard isomorphic symbols.

(3) For every symbol produced in (2), apply edge-contraction in all possible ways. Discard isomorphic symbols. We have implemented this approach on a computer, see [14]. Using three programs

ISOHEDRAL, TRUNCATE-VERTEX and CONTRACT-EDGE we obtain the following result:

Lemma 5.7 There exist exactly 1028+93 Delaney-Dress symbols (D; m) satisfying (N1)— (N3), up to isomorphism. Exactly 237 of the 1028 non-simple symbols are derived from the simple symbols by equivariant vertex-truncation, whereas the other 791 are obtained by equivariant vertex-truncation, followed by equivariant edge-contraction.

By virtue of Lemma 4.2 and Theorem 5.2 there exists a one-to-one correspondence between the above mentioned 1028+93 isomorphism classes of Delaney-Dress symbols and the equivariant equivalence classes of net-like tilings. We have the following

Theorem 5.8 There exist exactly 1028+93 equivariant types of periodic tile-transitive partial tilings (T , Γ) that are net-like, i.e. for which K_{∞} = ∅ holds.

All enumerated net-like tilings are available on a disk encoded as Delaney-Dress symbols from the author, together with the computer program REPTILES, developed in cooperation with Olaf Delgado Friedrichs, which translates Delaney-Dress symbols into tilings and visualizes them, see [5].

6. Patchy Partial Tilings

A periodic tile-transitive partial tiling (T , Γ) is called a patchy tiling, if #K_{∞} = 1. A patchy tiling is discrete if no two of its tiles touch.

Comparing definitions shows that there exists a natural one-to-one correspondence between the equivariant types of discrete patchy tilings (T , Γ) and the 52 different “homeomeric types” PP1—PP47, PP48A, PP48B, PP49—PP51 of “(discrete periodic) closed disk patterns” enumerated by B. Grünbaum and G. C. Shephard in [12], Table 5.2.3, pg. 228pp and pg. 345. Their results can be stated as

Theorem 6.1 There are exactly 52 equivariant types of discrete patchy tilings (T , Γ).

Let us now focus our attention on the non-discrete patchy tilings. First we will discuss how to enumerate the possible components.

Lemma 6.2 Let (T_{H}, Γ_{H}) be a component of a patchy tiling (T , Γ). The degree of any tile t ∈ T_{H} cannot exceed 4.

Proof. Let p ∈ ^{}be a fix-point of Γ_{H}. Such a point always exists, because Γ_{H} is a finite group of isometries. Consider a tile t ∈ T_{H}. Let x_{min} ∈ t be a point of minimal distance d_{min} from p. Let x_{max} ∈ t be a point of maximal distance d_{max} from p. Tile-transitivity implies that all tiles in T_{H} lie between the two circles of radius d_{min} and d_{max} centered at p. Furthermore, each tile t contains a path α(t) which connects a point on the inner circle with a point on the outer circle. Clearly, in this situation a tile t can only have at most four edges: one adjacent to the hole that lies within the inner circle (if this circle has positive radius), one adjacent to the unbounded component of the complement that lies outside the outer circle, at most one adjacent to the tile which lies to the one side of the path in α(t) and at most one to the otherside of α(t).

Lemma 6.3 Let (T_{H}, Γ_{H}) be a component of a non-discrete patchy tiling (T , Γ), let (D = D_{tiles} ∪ D_{holes} ∪ D_{∞}; m) be the associated Delaney-Dress symbol. Then #D ≤ 12.

Proof. If t ∈ T_{H} has three or less edges, then #D_{tiles} ≤ 6 and by property (DS4), #D ≤ #D_{tiles} + #(D_{tiles}σ_{2} \ D_{tiles}) ≤ 6 + 6 = 12. If t ∈ T_{H} has four edges, then two are shared by other tiles, and again, #D ≤ #D_{tiles} + #(D_{tiles}σ_{2} \ D_{tiles}) ≤ 8 + (8 − 4) = 12.

Let (T_{H}, Γ_{H}) be a component of a patchy tiling (T , Γ). Let K_{H} denote the set of all bounded sets in K and let L := ^{}\ ⋃_{∈T_{}∪K_{}}be the complement of the tiles and holes of the patch. Let x ∈ ^{}be a point such that γp = p for all γ ∈ Γ_{H}. Now, let ˜·: ^{}→ ^{} be the stereographic projection of the plane onto the sphere, based at point p.

It is obvious that the image of (T_{H}, Γ_{H}) under this projection: (T̃ := T̃_{H} ∪ K̃_{H} ∪ L̃, Γ̃) can be considered as an equivariant tile-k-transitive tiling of the sphere with k > 1, having the following properties:

(1) Γ̃_{H} operates transitively on T̃,

(2) Γ̃_{H} operates (k − 2)-transitively on K̃_{H}, with k ≥ 2,

(3) Γ̃_{H} stabilizes L̃, i.e. γL̃ = L̃ for all γ ∈ Γ̃. (Note that L̃ is possibly a non-disk tile).

Hence, the problem of classifying all possible components of patchy partial tilings can be translated into the problem of classifying appropriate equivariant tilings of the sphere. Our next step is to characterize the Delaney-Dress symbols of these spherical tilings.

First let us state a result that holds for tile-k-transitive tilings that cover the sphere, which is closely related to Theorem 5.1. This result is due to A. Dress, see [7] and [8].

Theorem 6.4 A (2-dimensional) Delaney-Dress symbol (D; m) corresponds to a tiling of the sphere if and only if K_{(D;m)} > 0 and the so-called integerity condition

\frac{χ(D)}{v_{ij}(D)} ∈ \frac{K_{(D;m)}}{2}

holds for all D ∈ D. (The tiling possibly contains non-disk tiles.)

Proof. See proof of Theorem 5.1 For a discussion of the following Lemma, due to A. Dress, see [15].

Lemma 6.5 Let (D; m) be the Delaney-Dress symbol corresponding to a spherical tiling (T , Γ). Then #Γ = \frac{4}{K_{(D;m)}} .

Now we can completely characterize those Delaney-Dress symbols that encode a component of a non-discrete patchy tilings:

Theorem 6.6 Let (D = D_{tiles}∪D_{holes}∪D_{∞}; m) be a Delaney-Dress symbol with #D ≤ 12. There exists the component (T_{H}, Γ_{H}) of a non-discrete patchy tiling associated with (D; m) if and only if the following conditions hold:

(P1) D_{∞} ≠ ∅ consists of exactly one \{0, 1\}-orbit and K_{(D;m)} = 2\frac{#D_{∞}}{m_{01}(D)} for all D ∈ D_{∞}.

(P2)  ∞ > m_{01}(D) ≥ \{ \begin{matrix}1 & if D ∈ D_{tiles} \\ 2 & if D ∈ D_{∞} and m_{01}(D′) = 1 for D′ ∈ D_{tiles} \\ 3 & otherwise. \end{matrix}

(P3) K_{(D;m)} > 0 and the integerity condition holds.

Proof. Property (P1) ensures that the encoded component is a bounded patch and that Γ stabilizes the complement of the patch. The latter follows from \frac{2m_{01}(D)}{#D_{∞}} = \frac{#(Γ ·D_{∞})}{#D_{∞}} = #Γ = \frac{4}{K_{(D;m)}} for D ∈ D_{∞}, by Lemma 6.5. Property (P2): If T_{H} consists of exactly two tiles, then the intersection of K_{∞} and T contains exactly two edges and otherwise, it contains at least three. Finally, (P3) ensures that the encoded tiling can indeed be interpreted as a tiling of the sphere.

One can produce a complete classification of all possible equivariant types of components of patchy tilings by generating all possible Delaney-Dress symbols statisfying (P1)— (P3). Using a computer program PATCHES we obtain the following result:

Theorem 6.7 There exist exactly 54 equivariant equivalence classes of components (T_{H}, Γ_{H}) of non-discrete patchy tilings, see Figure 5 at the end of this paper.

Now that we have classified all possible components of patchy tilings, let us discuss how to classify the patchy tilings themselves.

Let (T_{H}, Γ_{H}) be the component of a non-discrete patchy tiling with Delaney-Dress symbol (D; m). The group Γ_{H} is a finite cyclic or dihedral group, which can can easily be determined from (D; m): If Γ_{H} is a cyclic group of type Cn with n ∈ {2, 3, 4, 6}, then D must be orientable with χ(D) = 2 and all 2-color-orbits have branching number 1, except exactly two, which have branching number n. If Γ_{H} is a dihedral group of type Dn with n ∈ {1, 2, 3, 4, 6}, then D must be non-orientable with χ(D) = 1 and all 2-color-orbits have branching number 1, unless n > 1, in which case exactly two chains have branching number n.

In [12], Grünbaum and Shephard classify all “(discrete periodic) closed disk patterns” into 52 different “homeomeric types” PP1—PP47, PP48A, PP48B, PP49—PP51. Comparing definitions makes it obvious how to associate to each non-discrete patchy tiling (T , Γ) a homeomeric type PP1—PP51, i.e. by “engulfing” each component of the tiling in an appropriate “(marked) disk”, in such a way that the following result holds.

Theorem 6.8 Let (T , Γ) and (T′, Γ′) be two non-discrete patchy tilings with components (T_{H}, Γ_{H}) and (T′_{H′}, Γ′_{H′}), respectively. Then (T , Γ) and (T′, Γ′) are equivariantly equivalent if and only if

(1) (T_{H}, Γ_{H}) and (T′_{H′}, Γ′_{H′}) are equivariantly equivalent,

(2) (T , Γ) and (T′, Γ′) give rise to the same “homeomeric type” PP1—PP51.

So now we can produce an enumeration of the non-discrete patchy tilings. Let (T_{H}, Γ_{H}) be a representative of one of the 54 classes of components of non-discrete patchy tilings. Consider Table 5.2.3 in [12]. If for the “homeomeric type” PPi (where i ∈ {1, …, 47, 48A, 48B, 49, …, 51}) the “induced tile group” in column (3) of the table and the group type of Γ_{H} coincide, then there exists a patchy tiling (T , Γ) with component (T_{H}, Γ_{H}) that is associated with the “homeomeric type” PPi. In this way, the Table 5.2.3 and the above statements lead to the main result of this section:

Theorem 6.9 There exist exactly 204 equivariant equivalence classes of patchy tilings, 52 of which are classes of discrete patchy tilings [see Table 1].

Table 1: For each of the possible stabilizer groups we list the number of types of discrete patchy components, the names and number of appropriate patterns types and the resulting number of discrete patchy tilings.

7. Stripey Partial Tilings

A periodic tile-transitive partial tiling (T , Γ) is called a stripey tiling, if #K_{∞} = ∞. We will first discuss how to enumerate all possible types of components of stripey tilings. Such a classification can be based on the following

Theorem 7.1 Let (D = D_{tiles}∪D_{holes}∪D_{∞}; m) be a Delaney-Dress symbol with D_{tiles} ≠ ∅. There exists a component (T_{H}, Γ_{H}) of a stripey tiling associated with (D; m) if and only if the following conditions hold:

(S1) D_{∞} ≠ ∅ and m_{01}(D) = ∞ for all D ∈ D_{∞}.

(S2) ∞ > m_{01}(D) ≥ 3 if D ∈ D_{tiles} and ∞ > m_{01}(D) ≥ 2 if D ∈ D_{holes}.
(S3) K_{(D;m)} = 0.

Proof. Condition (S1) reflects that K_{∞} ≠ ∅ and that the connected components of the boundary of any set L ∈ K_{∞} are unbounded. Condition (S2) has the same effect as (N2) above. The condition (S3), together with (S1), ensures that the associated component (T_{H}, Γ_{H}) can be realized in the Euclidean plane. The proof of this fact involves studying the orbifolds associated with each of the seven types of frieze groups. This we do in the next Lemma.

The proof of the following result is analog to the discussion in [10] and [4]. We show that any Delaney-Dress symbol satisfying (S1)—(S3) leads to one of the seven orbifolds (see [2]) associated with the seven frieze groups (see [12], pg. 39).

Lemma 7.2 Let (D = D_{tiles} ∪ D_{holes} ∪ D_{∞}; m) be a Delaney-Dress symbol with properties (S1)—(S2). Then (S3) holds if and only if one of the following conditions hold:

• D is orientable and χ(D) = 2. There exist precisely two 2-color-orbits with non-trivial branching numbers. These are the two {0, 1}-cycles that make up D_{∞}, and both have branching number ∞. This gives rise to the orbifold ∞∞. The frieze group is p111.

• D is orientable and χ(D) = 2. There exist precisely three 2-color-orbits with nontrivial branching numbers; the {0, 1}-cycle D_{∞} has branching number ∞, whereas two other 2-color-orbits have branching number 2. This gives rise to the orbifold 22∞. The frieze group is p112.

• D is non-orientable, but fixed-point-free, and χ(D) = 1. There exists only one 2-color-orbit with a non-trivial branching number, namely the {0, 1}-cycle D_{∞}, with branching number ∞. This gives rise to the orbifold ∞×. The frieze group is p1a1.

• D has fixed-points and χ(D) = 1. There exists only one 2-color-orbit with non-trivial branching number, namely the {0, 1}-cycle D_{∞}, with branching number ∞. This gives rise to the orbifold ∞∗. The frieze group is p1m1.

• D has fixed-points and χ(D) = 1. Furthermore, D_{∞} consists of precisely two {0, 1}- chains, and these are the only 2-color-orbits having non-trivial branching numbers, both ∞. This gives rise to the orbifold ∗∞∞. The frieze group is pm11.

• D has fixed-points and χ(D) = 1. Furthermore, D contains a {i, j}-cycle with branching number 2 and D_{∞} is a single {0, 1}-chain with branching number ∞. This gives rise to the orbifold 2∗∞. The frieze group is pma2.

• D has fixed-points and χ(D) = 1. There exist three 2-color-orbits with non-trivial branching numbers, ∞, 2, 2, and these are all chains. This gives rise to the orbifold ∗22∞. The frieze group is pmm2.

Proof. Let us first assume that D is orientable. In this case the topological realization of D is a compact orientable 2-manifold and thus, χ(D) ∈ {2, 0, −2, …}. We have

2χ(D) + #D = ∑_{0≤i<j≤2} ∑_{D∈D} \frac{1}{r_{ij}(D)}.

Thus, K_{(D;m)} = 0 if and only if

#D = ∑_{0≤i<j≤2} ∑_{D∈D} \frac{1}{m_{ij}(D)},

where \frac{1}{m_{ij}(D)} := 0 whenever m_{ij}(D) = ∞. So (S3) holds if and only if

2χ(D) + ∑_{D∈D} ∑_{0≤i<j≤2} \frac{1}{m_{ij}(D)} = ∑_{D∈D} ∑_{0≤i<j≤2} \frac{1}{r_{ij}(D)}

or

2χ(D) = ∑_{D∈D} ∑_{0≤i<j≤2}(\frac{1}{r_{ij}(D)} − \frac{1}{m_{ij}(D)})

= ∑_{0≤i<j≤2} ∑_{O\{i,j\}−orbit} ∑_{D∈O}(\frac{1}{r_{ij}(D)} − \frac{1}{v_{ij}(D)r_{ij}(D)})

= ∑_{0≤i<j≤2} ∑_{O\{i,j\}−orbit} #O(\frac{1}{r_{ij}(D ∈ O)} − \frac{1}{v_{ij}} (D ∈ O)r_{ij}(D ∈ O))

= ∑_{0≤i<j≤2} ∑_{O\{i,j\}−orbit} 2(1 − \frac{1}{v_{ij}(D ∈ O)})

(#O = 2r_{ij}(D ∈ O), because D is orientable)

holds. In particular, χ(D) > 0 in view of v_{01}(D) = ∞ for D ∈ D_{∞} ≠ ∅.

So property (S3) holds if and only if the n non-trival branching numbers v_{1}, …, v_{n} belonging to (D; m) satisfy

∑_{i=1}^{n}(1 − \frac{1}{v_{i}}) = 2

If we assume v_{1} = ∞, then ∑_{i=2}^{n}(1 − \frac{1}{v_{i}}) = 1.

From (1 − \frac{1}{v_{i}}) > \frac{1}{2} for v_{i} > 2 it follows that either v_{2} = ∞ and n = 2 or v_{2} = v_{3} = 2 and n = 3. If D is non-orientable, then by considering the oriented covering D′ we obtain the other cases.

Lemma 7.3 Let (D = D_{tiles} ∪ D_{holes} ∪ D_{∞}; m) be a Delaney-Dress symbol with properties (S1)—(S3). Then #D ≤ 24.

Proof. First assume #D_{∞} ≥ 2. Let

D_{3} := {D ∈ D | m_{12}(D) = 3} and D_{4} := {D ∈ D | m_{12}(D) ≥ 4}.

We have

\begin{aligned}0 = K_{(D,m)} & = ∑_{D∈D}(\frac{1}{m_{01}(D)} + \frac{1}{m_{12}(D)} + \frac{1}{m_{02}(D)} − 1) \\ & = ∑_{D∈D}(\frac{1}{m_{01}(D)} + \frac{1}{m_{12}(D)} − \frac{1}{2}) \end{aligned}

and therefore

∑_{D∈D}(\frac{1}{2} − \frac{1}{m_{12}(D)}) = ∑_{D∈D_{tiles}} \frac{1}{m_{01}(D)} + ∑_{D∈D_{holes}∪D_{∞}} \frac{1}{m_{01}(D)}

≤2 + \frac{1}{3}(#(D_{holes} ∪ D_{∞}) − 2)
=2 + \frac{1}{3}(#((D_{holes} ∪ D_{∞}) ∩ D_{3})
+ #((D_{holes} ∪ D_{∞}) ∩ D_{4}) − 2)
≤2 + \frac{1}{9}#D_{3} + \frac{1}{6}#D_{4} − \frac{2}{3}

because #((D_{holes} ∪ D_{∞}) ∩ D_{3}) ≤ \frac{1}{3}#D_{3} and #((D_{holes} ∪ D_{∞}) ∩ D_{4}) ≤ \frac{1}{2} in view of (D_{holes} ∪ D_{∞})σ_{2} ⊆ D_{tiles}. So it follows from

\begin{aligned}∑_{D∈D}(\frac{1}{2} − \frac{1}{m_{12}(D)}) & = \frac{1}{2}#D − ∑_{D∈D} \frac{1}{m_{12}(D)} \\ & ≥ \frac{1}{2}#D − \frac{1}{3}#D_{3} − \frac{1}{4}#D_{4} \end{aligned}

that

\begin{aligned}\frac{4}{3} & ≥ −\frac{1}{9}#D_{3} − \frac{1}{6}#D_{4} + \frac{1}{2}#D − \frac{1}{3}#D_{3} − \frac{1}{4}#D_{4} \\ & = \frac{1}{18}#D_{3} + \frac{1}{12}#D_{4} ≥ \frac{1}{18}#D \end{aligned}

and thus, 24 ≥ #D.

Now assume #D_{∞} = 1, then D is not orientable and the orientated covering (D′ = D′_{tiles}∪D′_{holes}∪D′_{∞}; m′) has properties (DS1)—(DS5) and also (S1)—(S3). If D′ ∈ D_{∞} then D′σ_{0} = D′σ_{1} = D′. So for D = D′σ_{2} ∈ D we have Dσ_{0} = D′σ_{2}σ_{0} = D′σ_{0}σ_{2} = D′σ_{2} = D. Thus D_{tiles} is a {0, 1}-chain and hence D′ = {(D, ϵ) | D ∈ D, ϵ ∈ {+1, −1}} is a single {0, 1}-orbit in D′, i.e. (D′; m′) also has property (DS6). Thus we can apply the first part of this proof to (D′; m′) and get 24 ≥ #D′ = 2#D.

Using a computer program STRIPES we have produced a representative for each isomorphism type of Delaney-Dress symbol (D; m) satisfying (S1)—(S3). Furthermore, for each such representative we have determined the frieze type of the stabilizer group Γ_{H} of an associated component (T_{H}, Γ_{H}). We thus obtain the following result

Theorem 7.4 There are exactly 93 different equivariant equivalence classes of components (T_{H}, Γ_{H}) of stripey tilings [see Figure 6 at the end of this paper].

In [12], Grünbaum and Shephard give a classification of the “periodic strip patterns” into 26 different “pattern types” SPS1—SPS26. Comparing definitions makes it obvious how to associate to each stripey tiling (T , Γ) a “pattern type” (i.e. by “engulfing” each component of the stripey tiling in an appropriate “marked strip tile”) in such a way that the following result holds Theorem 7.5 Let (T , Γ) and (T′, Γ′) be two stripey tilings with components (T_{H}, Γ_{H}) and (T′_{H′}, Γ′_{H′}). Then (T , Γ) and (T′, Γ′) are equivariantly equivalent if and only if

(1) (T_{H}, Γ_{H}) and (T′_{H′}, Γ′_{H′}) are equivariantly equivalent ,

(2) (T , Γ) and (T′, Γ′) give rise to the same “pattern type” SPSi (i ∈ {1, …, 26}).

We can now obtain an enumeration of the stripey tilings. Let (T_{H}, Γ_{H}) be a representative of one of the 93 classes of components of stripey tilings. Consider Table 6.5.1 in [12]. If for “pattern type” SPSi (i ∈ {1, …, 26}) it holds that the “induced tile group” in column (6) of the table and the frieze type of Γ_{H} coincide, then there exists a stripey tiling (T , Γ) with component (T_{H}, Γ_{H}) that is associated with the “pattern type” SPSi. In this way, Table 6.5.1 and the above statements lead to the main result of this Section

Theorem 7.6 There exist exactly 248 equivariant equivalence classes of stripey tilings [see Table 2].

Table 2: For each of the seven possible frieze groups we list the number of types of stripey components, the names and number of appropriate patterns types and the resulting number of stripey tilings.

Consider a strip in the euclidean plane bounded by two infinite parallel lines. In [17] it was shown that exactly 24 equivariant types of isohedral tilings of such a strip exist. These correspond to the following 24 types of stripey components depicted in Figure 6: SC 3, SC 5, SC 10, SC 11, SC 13, SC 15, SC 21, SC 23, SC 36, SC 37, SC 38, SC 39, SC 42, SC 50, SC 52, SC 53, SC 57, SC 62, SC 63, SC 65, SC 82, SC 85, SC 92 and SC 93.

References

[1] A. Brown, R. Bülow, J. Neubüser, J. Wondratschek, and H. Zassenhaus. Crystallographic groups for four-dimensional space. Wiley Mongraphs in Crystallography, New York, 1978.

[2] J.H. Conway. The orbifold notation for surface groups. In Groups, Combinatorics and Geometry, pages 438–447. Cambridge University Press, 1990. London Mathematical Society Lecture Note Series 165.

[3] A.W.M. Dress and D.H. Huson. On tilings of the plane. Geometriae Dedicata 24 (1987), 295–310.

[4] A.W.M. Dress and D.H. Huson. Heaven and hell tilings. Revue Topologie Structurale 17 (1991), 25–42.

[5] O. Delgado Friedrichs and D.H. Huson. REPTILES. University of Bielefeld, 1992. Shareware macintosh-program.

[6] O. Delgado Friedrichs, D.H. Huson, and E. Zamorzaeva. The classification of 2isohedral tilings of the plane. Geometriae Dedicata 42 (1992), 43–117.

[7] A.W.M. Dress. Regular polytopes and equivariant tessellations from a combinatorial point of view. In Algebraic Topology, pages 56–72. SLN 1172, Göttingen, 1984.

[8] A.W.M. Dress. The 37 combinatorial types of regular “heaven and hell” patterns in the euclidean plane. In H.S.M. Coxeter et al., editor, M.C. Escher: Art and Science, pages 35–43. Elsevier Science Publishers B.V., North-Holland, 1986.

[9] A.W.M. Dress. Presentations of discrete groups, acting on simply connected manifolds. Adv. in Math. 63 (1987), 196–212.

[10] A.W.M. Dress and R. Scharlau. Zur Klassifikation äquivarianter Pflasterungen. Mitteilungen aus dem Math. Seminar Giessen 164 (1984), 83–136.

[11] B. Grünbaum and G.C. Shephard. A hierarchy of classification methods for patterns. Zeitschrift f. Kristallographie 154 (1981), 163–187.

[12] B. Grünbaum and G.C. Shephard. Tilings and Patterns. W.H. Freeman and Company, New York, 1987.

[13] D.H. Huson. Patches, Stripes and Net-Like Tilings. PhD thesis, University of Bielefeld, 1989.

[14] D.H. Huson. A four-color theorem for periodic tilings. manuscript, 1993.

[15] D.H. Huson. The generation and classification of tile-k-transitive tilings of the euclidean plane, the sphere and the hyperbolic plane. to appear in: Geometriae Dedicata, 1993.

[16] J.M. Montesinos. Classical Tessellations and Three-Manifolds. Springer Verlag, New York Heidelberg Berlin, 1987.

[17] R.L. Roth. Isohedral tilings of a ribbon. Geometriae Dedicata 29 (1989), 186–191.

D.H. Huson: Tile-Transitive Partial Tilings of the Plane 109

Figure 5: The 54 types of components of non-discrete patchy partial tilings.

110 D.H. Huson: Tile-Transitive Partial Tilings of the Plane Figure 5 (continued)

D.H. Huson: Tile-Transitive Partial Tilings of the Plane 111

Figure 5 (continued)

Figure 5 (continued)

Figure 6: The 93 types of components of stripey patchy tilings.

D.H. Huson: Tile-Transitive Partial Tilings of the Plane 113

Figure 6 (continued)

114 D.H. Huson: Tile-Transitive Partial Tilings of the Plane Figure 6 (continued)

D.H. Huson: Tile-Transitive Partial Tilings of the Plane 115

Figure 6 (continued)

116 D.H. Huson: Tile-Transitive Partial Tilings of the Plane Figure 6 (continued)

D.H. Huson: Tile-Transitive Partial Tilings of the Plane 117

Figure 6 (continued)

118 D.H. Huson: Tile-Transitive Partial Tilings of the Plane Figure 6 (continued)