text:
# Ribbon tilings and multidimensional height functions

## 1. Introduction

### 1.1. Ribbon tilings

A square in the two-dimensional grid indexed by integers $`(x,y)`$ has color $`c`$ if $`x+yc(modn)`$. Two squares in the $`^2`$ lattice are adjacent if they share an edge. A ribbon tile of order $`n`$ is a connected set of squares containing exactly one square of each color. (See Figure 2.) A ribbon tile can also be defined as a connected sequence of $`n`$ squares, each of which comes directly above or to the right of its predecessor. A region $`R`$ is any connected, finite subset of the squares of $`^2`$. Two order-$`n`$ ribbon tilings of $`R`$ are connected by a local replacement move (or simply a local move) if one can be obtained from the other by removing a single pair of ribbon tiles and adding another pair in its place.

Labeled ribbon tilings of Young tableaux (also called rim hook tableaux) have connections with symmetric function theory, symmetric group representations, and monochromatic increasing subsequences in colored permutations. (See , , , , and .) Pak was the first to consider ribbon tilings of more general regions .

A ribbon tile of order $`n`$ has one of $`2^{n1}`$ possible shapes. (See Figure 1.) If $`ϵ`$ represents one of the $`2^{n1}`$ shapes of a ribbon tile of size $`n`$ and $`\alpha `$ is an order-$`n`$ ribbon tiling of a simply connected region, we denote by $`a_ϵ(\alpha )`$ the number of tiles in $`\alpha `$ of shape $`ϵ`$.

In , Pak coined the term tile invariant to describe linear combinations of the $`a_ϵ(\alpha )`$ whose values were the same for all tilings $`\alpha `$ of a region $`R`$. Pak showed that if it were proved that any two order-$`n`$ ribbon tilings of a region $`R`$ could be connected by a sequence of local replacement moves, then certain tile invariants of $`R`$ could be deduced as a trivial consequence . Pak used a version of the Schensted algorithm for rim hook tableaux—a correspondence between rim hook tableau and $`n`$-tuples of smaller tableaux (known by Nakayama and Robinson  , rediscovered by Stanton and White )—to prove that any two order-$`n`$ ribbon tilings of a Young diagram could be connected by a sequence of local moves, and that his tile invariants must therefore hold for Young-tableau-shaped regions. Pak used other techniques to extend the tile invariants to row-convex regions and conjectured that both local move connectedness and (consequently) the tile invariants could be extended to arbitrary simply connected regions.

Without proving local move connectedness, Muchnik and Pak  and Moore and Pak  extended Pak’s tile invariant results to (respectively) order-$`4`$ and order-$`n`$ ribbon tilings of general simply connected regions. Moore and Pak  reiterated Pak’s conjecture about local move connectedness for general simply connected regions and cited private communication from Thurston suggesting that the conjecture might be proved if one could find a correspondence between ribbon tilings and so-called height functions mapping the vertices of $`R`$ to $`^n`$. Using Thurston’s suggestion and a connection with acyclic orientations, we prove the conjecture.

###### Theorem 1.1.

Any two order-$`n`$ ribbon tilings of a simply connected region $`R`$ can be connected by a sequence of local replacement moves.

Here, we say $`R`$ is simply connected if $`sR`$ implies that there is no connected cycle of squares in $`R`$ that encircles $`s`$ with a non-zero winding number; unless otherwise specified, we will always assume $`R`$ is simply connected.

Our main ribbon tiling result relates the order-$`n`$ ribbon tilings of a given region $`R`$ to the acyclic orientations extending a certain partial orientation of a graph $`G_R`$. Pak’s original paper  on ribbon tilings used a related construction (based on earlier results in , , and ) to prove local replacement move connectedness for ribbon tilings of Young-tableaux. We will not use the results of these papers in our presentation.

Before we can state the main theorem, we need to define several terms. The first is a “left of” relation, denoted $``$, defined for both tiles and squares. In our pictures, we generally rotate the set of tiles forty-five degrees so that $`x+y`$ increases as we move upwards. (See Figure 2.) Let $`s_{x,y}`$ be the square at position $`(x,y)`$.

We say $`s_{x,y}`$ is directly left of $`s_{x^{},y^{}}`$ if $`x+y=x^{}+y^{}`$ and $`x<x^{}`$. We say $`s_{x,y}`$ is indirectly left of $`s_{x^{},y^{}}`$ if $`|(x+y)(x^{}+y^{})|=1`$ and $`xx^{}`$ and $`yy^{}`$. (Equivalently, $`s_{x,y}`$ is indirectly left of $`s_{x^{},y^{}}`$ if it is directly left of one of the four neighbors of $`s_{x^{},y^{}}`$.) If $`s_{x,y}`$ is directly or indirectly left of $`s_{x^{},y^{}}`$, we write $`s_{x,y}s_{x^{},y^{}}`$.

If $`t`$ is a tile and $`s`$ is a square, we write $`st`$ if $`ss^{}`$ for some $`s^{}t`$, and $`ts`$ if $`s^{}s`$ for some $`s^{}t`$. If $`t_1`$ and $`t_2`$ are two tiles in $`\alpha `$, we write $`t_1t_2`$ if there exist $`s_1t_1`$ and $`s_2t_2`$ with $`s_1s_2`$. It is easy to verify that if $`t_1`$ and $`t_2`$ are disjoint ribbon tiles, we cannot have both $`t_1t_2`$ and $`t_2t_1`$.

We will also say a square $`s_{x,y}`$ is higher (lower) than $`s_{x^{},y^{}}`$ if $`x+y>x^{}+y^{}`$ ($`x+y<x^{}+y^{}`$). We say $`x+y`$ is a square of level $`c`$ if $`x+y=c`$ and a tile $`t`$ has level $`c`$ if $`c`$ is the level of its lowest square. (A square’s color is equal to its level modulo $`n`$.) An edge has type $`(i,i+1)`$ if it separates squares of color $`i`$ and $`i+1`$, and a tile has type $`(i,i+1)`$ if its lowest and highest squares have color $`i+1`$ and $`i`$ respectively (when defining types, we always add modulo $`n`$). Also, $`a`$ and $`b`$ are comparable by $``$ if either $`ab`$ or $`ba`$.

Given a tiling $`\alpha `$, we define $`t_{c,i}(\alpha )`$ to be the $`i`$th tile in $`\alpha `$, from left to right, of level $`c`$ (when such a tile exists). Clearly $`t_{c,i}(\alpha )t_{c,i+1}(\alpha )`$ whenever these two tiles are defined.

Let $`B_R`$ be the boundary of $`R`$, that is, the set of squares that are not contained in $`R`$ but are adjacent to at least one square in $`R`$. We define the oriented graph $`G_R(\alpha )`$ to be the graph whose vertices are the tiles in $`\alpha `$ and the boundary squares of $`R`$. Two such vertices $`a`$ and $`b`$ are adjacent if they are comparable under $``$, and we say this edge is oriented from $`a`$ to $`b`$ if $`ab`$.

Some aspects of $`G_R(\alpha )`$ are independent of $`\alpha `$; using height functions, we will prove the following result:

###### Lemma 1.2.

Any two tilings $`\alpha `$ and $`\beta `$ of $`R`$ necessarily contain the same number of tiles of each level. Thus, $`t_{c,i}(\alpha )`$ is defined if and only if $`t_{c,i}(\beta )`$ is defined. Furthermore, if $`cd(modn)`$, then $`t_{c,i}(\alpha )t_{d,j}(\alpha )`$ if and only if $`t_{c,i}(\beta )t_{d,j}(\beta )`$. Also, if $`bB_R`$, then $`t_{c,i}(\alpha )b`$ if and only if $`t_{c,i}(\beta )b`$ . Similarly, $`bt_{c,i}(\alpha )`$ if and only if $`bt_{c,i}(\beta )`$.

In other words, the map sending $`t_{c,i}(\alpha )`$ into $`t_{c,i}(\beta )`$ is a canonical bijection between the tiles of $`\alpha `$ and those of $`\beta `$, and this bijection preserves the relation $``$ between tiles of the same type and between tiles and boundary squares.

We define a tiling-independent partially oriented graph $`G_R`$ as follows: all boundary squares in $`B_R`$ are vertices of $`G_R`$ and we include a vertex called $`t_{c,i}`$ in $`G_R`$ if the tile $`t_{c,i}(\alpha )`$ is defined for some tiling $`\alpha `$ (and hence all such tilings) of $`R`$. An edge is contained in $`G_R`$ if and only if the corresponding edge is included in $`G_R(\alpha )`$ for some tiling $`\alpha `$ (and hence all such tilings). (Thus, $`t_{c,i}`$ and $`t_{d,j}`$ are adjacent in $`G_R`$ if and only if $`|cd|n`$; $`t_{c,i}`$ and $`s_{x,y}`$ are adjacent in $`G_R`$ if and only if $`c1x+yc+n`$; and $`s_{x,y}`$ and $`s_{x^{},y^{}}`$ are adjacent in $`G_R`$ if and only $`|(x+y)(x^{}+y^{})|1`$.)

Given a tiling $`\alpha `$, we can now think of $`G_R(\alpha )`$ as an orientation on the graph $`G_R`$ (i.e., a way of assigning a direction to each edge of $`G_R`$) in the obvious way: that is, an edge $`(t_{c,i},t_{d,j})`$ is oriented from $`t_{c,i}`$ to $`t_{d,j}`$ in $`G_R(\alpha )`$ if and only if $`t_{c,i}(\alpha )t_{d,j}(\alpha )`$. We define the orientation similarly for edges involving two boundary squares or one tile and one boundary square.

An edge involving two tiles of different types (i.e., some $`t_{c,i}`$ and $`t_{d,j}`$ with $`cd(modn)`$) is called a free edge of $`G_R`$. All other edges are called forced edges of $`G_R`$. By Lemma 1.2, a forced edge $`(a,b)`$ will be oriented in the same direction as $`G_R(\alpha )`$ for every tiling $`\alpha `$. Thus, we can think of $`G_R`$ as being endowed with a partial orientation: its forced edges are all oriented. We say $`G_R(\alpha )`$ extends this partial orientation by assigning an orientation to each free edge of $`G_R`$.

Two orientations differ by an edge reversal if they agree on all but exactly one edge. The following is our main structure theorem about the set of order-$`n`$ ribbon tilings of $`R`$.

###### Theorem 1.3.

If $`R`$ admits at least one order-$`n`$ ribbon tiling, then there is a one-to-one correspondence between the order-$`n`$ ribbon tilings of $`R`$ and the acyclic orientations extending the partial orientation of $`G_R`$. Furthermore, local replacement moves in the space of tilings correspond to edge reversals in the space of orientations. To be precise, we make four assertions:

1. For every order-$`n`$ ribbon tiling $`\alpha `$ of $`R`$, $`G_R(\alpha )`$ is an acyclic orientation extending the partial orientation of $`G_R`$.
2. If $`\alpha `$ and $`\beta `$ are order-$`n`$ ribbon tilings then $`\alpha =\beta `$ if and only if $`G_R(\alpha )=G_R(\beta )`$.
3. Every acyclic orientation $`A`$ of $`G_R`$ that extends the partial orientation of $`G_R`$ is equal to $`G_R(\alpha )`$ for some tiling $`\alpha `$.
4. Two order-$`n`$ ribbon tilings $`\alpha `$ and $`\beta `$ differ by a local replacement move if and only if $`G_R(\alpha )`$ and $`G_R(\beta )`$ differ by an edge reversal.

Given Theorem 1.3, we will now deduce the connectedness of ribbon tilings under local replacement moves by citing a corresponding result about acyclic orientations.

Define the distance $`d(A,B)`$ between orientations $`A`$ and $`B`$ of a graph $`G`$ to be the number of edges on which they differ. Then it is well known that $`A`$ can be transformed into $`B`$ with $`d(A,B)`$ edge reversals in such a way that each intermediate step is also an acyclic orientation. (See  for a more general result.) Clearly, each intermediate step agrees with $`A`$ and $`B`$ on all edges on which $`A`$ and $`B`$ agree. It follows that if $`\alpha `$ and $`\beta `$ are tilings, then the intermediate steps of a length $`d(G_R(\alpha ),G_R(\beta ))`$ path of acyclic orientations connecting $`G_R(\alpha )`$ and $`G_R(\beta )`$ must all be extensions of the partial orientation of $`G_R`$. Thus, each of these corresponds to an order-$`n`$ ribbon tiling of $`R`$. Assuming Theorem 1.3, we have proved Theorem 1.1.

See , ,  and the references therein for more about the structure of the space of acyclic orientations. We will also derive, as another consequence of Theorem 1.3, an existence algorithm.

###### Theorem 1.4.

There is a linear-time (i.e., linear in the number of squares of $`R`$) algorithm for determining whether there exists an order-$`n`$ ribbon tiling of $`R`$ and producing such a tiling when one exists.

We begin in Section 2 by reviewing the height function theory of Conway-Lagarias and Thurston and showing that it leads naturally to a construction of abelian height functions for a variety of tiling problems. In Section 3, we apply this theory specifically to the ribbon tiling problem and prove our three main results: Lemma 1.2, Theorem 1.3, and Theorem 1.4. In Section 4 we discuss generalizations of our abelian height function constructions to tilings that do not appear to have the same acyclic orientation characterization that ribbon tilings have. Finally, in Section 5 we present a number of open problems in the theory of ribbon tilings and general abelian height functions.

## 2. Abelian Conway-Lagarias Thurston Height Functions

Our height function construction for ribbon tilings makes use of a general technique developed by Conway and Lagarias  and Thurston  for analyzing tiling problems. A polyomino is a finite, connected subset of the squares of $`^2`$ whose complement is also connected. For simplicity, we will review the theory only for polyomino tilings, although similar techniques apply if one replaces the squares of the grid with the faces of any planar graph (e.g., the hexagonal lattice). (More general expositions—which invoke the language of Cayley complex homology—can be found in , , and .)

A tile set $`T`$ is a (usually infinite) set of finite, simply-connected subsets of the squares of $`^2`$. Usually, we assume $`T`$ is translation invariant (i.e., $`tT`$ implies that $`\{s_{x,y}|s_{x+x_0,y+y_0}t\}T`$ for all $`x_0,y_0`$) but this need not be the case. The first step in the Conway-Lagarias construction is to choose a map $`\varphi `$ from the oriented edges of the plane into a group $`G`$ in such a way that $`\varphi (a)=\varphi (a^1)`$ for all oriented edges $`a`$; here $`a^1`$ is the same edge as $`a`$ with opposite orientation, and (since we will eventually restrict our attention to abelian groups) we write the group operation additively. We also require that the sum of $`\varphi (e)`$ over the clockwise-oriented edges $`e`$ on the boundary of any tile in $`T`$ (added in clockwise order) be equal to the identity in $`G`$. These requirements are called tile relations. Once the group is chosen, given any tiling $`\alpha `$, we can construct a height function $`h_\alpha `$ mapping at least some of the vertices of $`R`$ into $`G`$ as follows.

First, choose a reference vertex $`v_0`$ on the boundary of $`R`$ and require that $`h_\alpha (v_0)`$ be the identity. Then if $`v`$ is any other vertex of $`R`$ that is on the boundary of a tile, $`h_\alpha (v)`$ is the ordered product of the oriented edges along a path from $`v_0`$ to $`v`$ that does not cross any tiles. (If the tiles are simply connected, such a path will always exist.) Using the tile relations, it is not hard to prove that the value $`h_\alpha (v)`$ is independent of the path chosen.

We can also always assume that the group $`G`$ is generated by the values of $`\varphi (e)`$ where $`e`$ is an edge in the $`^2`$ lattice. (Otherwise, replace $`G`$ by the subgroup generated by these values.) One can obtain the largest possible group $`G`$ that is generated by $`\varphi (e)`$ as follows: Let $`G`$ be the group generated by the oriented edges of $`^2`$ modulo the relations $`e=0`$ for clockwise sums of clockwise-oriented boundary edges of a tile and $`e+e^1=0`$ for all $`e`$. Then let $`\varphi (e)`$ be the image of the edge $`e`$ in the group $`G`$.

The height function constructed in this way is in a sense “maximally informative” since any other height function is a quotient of this one. Unfortunately, this group is unwieldy in practice and can be difficult to analyze. On the other hand, if one merely seeks the maximally informative abelian group, the analysis becomes much simpler.

Suppose $`G`$ is an additive abelian group and $`\varphi `$ is a map from the oriented edges of $`^2`$ to $`G`$. If $`t`$ is any polyomino tile in $`^2`$, we denote by $`\varphi (t)`$ the sum of the clockwise-oriented edges of $`t`$. Observe that

$$\varphi (t)=\underset{st}{}\varphi (s),$$

where the sum is over squares $`s`$ that are contained in the tile $`t`$.

Now, suppose that $`p=(v_0,v_1,\mathrm{},v_k)`$ is a non-self-intersecting path of vertices in $`R`$ connecting the reference vertex $`v_0`$ to a vertex $`v_k`$ on the boundary of some tile in $`\alpha `$. We say that $`p`$ crosses a tile $`t`$ in $`\alpha `$ if for some $`0ik1`$, the edge $`(v_i,v_{i+1})`$ lies between two squares in $`t`$. If $`s`$ is a square in $`R`$ and $`0i<jk`$, we say $`p`$ passes $`s`$ on the left between vertices $`i`$ and $`j`$ if:

1. The vertices $`v_i`$ and $`v_j`$ are on the boundary of a tile $`t`$ and all edges between $`v_i`$ and $`v_j`$ on $`p`$ are interior edges of the tile $`t`$.
2. The square $`s`$ is contained in the polygon formed by the edges in $`p`$ between $`v_i`$ and $`v_j`$ together with the counter-clockwise half of the boundary of $`t`$ connecting $`v_i`$ to $`v_j`$.

Note that a long path could pass a square $`s`$ on the left several times if $`s`$ belongs to a tile that the path crosses several times.

We define $`\varphi (p)=_{i=0}^{k1}\varphi (v_i,v_{i+1})`$ and observe the following:

###### Proposition 2.1.

The height function value at $`v_k`$ can be written as

$$h_\alpha (v_k)=\varphi (p)+\varphi (s),$$

where the latter sum is over all squares (counted with multiplicity) that $`p`$ passes on the left.

To see this, let $`p^{}`$ be a path from $`v_0`$ to $`v_k`$ that is the same as $`p`$ except that each interval that crosses a tile $`t`$ is replaced by the path around the boundary of $`t`$ on the left side of $`p`$. The reader may easily check that $`\varphi (p^{})\varphi (p)`$ is equal to the sum of $`\varphi (s)`$ over all squares (counted with multiplicity) that $`p`$ passes on the left. By definition, $`h_\alpha (v_k)=\varphi (p^{})`$, so the proposition follows.

Since $`\varphi (p)`$ is independent of the particular tiling $`\alpha `$, we have a simple interpretation of the height function $`h_\alpha (v)`$: it tells us the sum of $`\varphi (s)`$ over the squares $`s`$ passed on the left by a path from $`v_0`$ to $`v`$. For our height function to be maximally informative, $`G`$ must be (or at least contain) the abelian group generated by $`\varphi (s)`$ subject to only the tiling relations. We refer to this group as the canonical abelian height space (also known as the color group) of a set of tiles $`T`$.

We say two squares $`s_1`$ and $`s_2`$ have the same color if it can be deduced from the tiling relations that $`\varphi (s_1)=\varphi (s_2)`$. (In other words, $`s_1s_2`$ is zero in the group generated by the squares of $`^2`$ modulo the relations $`_{st}s=0`$ for all $`tT`$.)

This notion is best illustrated using our primary example: ribbon tiling. Let $`s_{x,y}`$ denote the square at position $`(x,y)`$ in the lattice, and consider two overlapping horizontal ribbon tiles of length $`n`$, one of which has leftmost square $`s_{x,y}`$ and the other $`s_{x+1,y}`$. The corresponding tile relations tell us that $`_{i=0}^{n1}\varphi (s_{x+i,y})=0`$ and $`_{i=1}^n\varphi (s_{x+i,y})=0`$. And this implies that $`\varphi (s_{x,y})=\varphi (s_{x+n,y})`$. Thus, $`s_{x,y}`$ and $`s_{x+n,y}`$ have the same color.

Repeating similar arguments with other pairs of ribbon tiles that overlap on all but one square, one can deduce that squares at $`(x_1,y_1)`$ and $`(x_2,y_2)`$ necessarily have the same color whenever $`x_1+y_1`$ and $`x_2+y_2`$ are equivalent modulo $`n`$. Denote by $`e_i`$ the value of $`\varphi (s_{x,y})`$ when $`x+yi(modn)`$. Then the relation $`_{i=0}^{n1}e_i=0`$ is enough to guarantee that $`\varphi (t)=0`$ for any ribbon tile $`t`$ of length $`n`$. Thus, if $`G`$ is the abelian group generated by $`e_0,\mathrm{},e_{n1}`$ subject to this one relation, $`G`$ is maximally informative.

At this point, we know the value of $`\varphi (s)G`$ for every square $`s`$. However, we still have to choose a function $`\varphi `$ on the edges of the $`^2`$ lattice in such a way that $`\varphi (s)`$ has the desired values. This is essentially a linear algebra problem, and it is not hard to see that it always has at least one solution. (We return to this issue in the next section.)

This “maximally informative” abelian height function construction is unique up to two obvious transformations. First, change of basis: one can replace $`G`$ with any group $`G^{}`$ and the $`e_i`$ with any elements of $`G^{}`$ satisfying the necessary relations. Second, translation by a tiling-independent function: one can add to $`\varphi (e)`$ any function $`\varphi ^{}`$ satisfying $`\varphi ^{}(s)=0`$ for all $`s`$. This amounts to adding a function (independently of $`\alpha `$) to each height function $`h_\alpha `$.

In particular applications, we try to choose the basis for $`G`$ and the values of $`\varphi `$ on the edges in $`^2`$ in a way that makes the tiling space easy to understand. In particular, if $`T`$ is translation invariant, it is usually convenient for $`\varphi `$ to have some translational symmetries as well.

## 3. Ribbon Tilings

### 3.1. Height Functions for Ribbon Tilings

Although we determined in the last section that $`\varphi (s)=e_i`$ when $`s`$ is a square of color $`i`$, we have considerable freedom in choosing the values of $`\varphi `$ on the edges in $`^2`$. We will use this freedom to force $`\varphi `$ to have certain symmetries.

First, we would like $`\varphi `$ to be invariant under color-preserving translations of $`^2`$; this amounts to the requirement that $`\varphi (e)`$ be the same whenever $`e`$ is a vertical (or similarly, horizontal) edge of type $`(i,i+1)`$ oriented with color $`i+1`$ on the left. We would also like $`\varphi `$ at such an edge to have the same value—call it $`e_{i,i+1}`$—independently of whether the edge is horizontal or vertical.

Let $`e_{0,1},e_{1,2},\mathrm{},e_{n1,0}`$ be basis elements of a height space $`G=^n`$. Summing around a square of color $`i`$ tells us that $`e_i`$ must be equal to $`2e_{i,i+1}2e_{i1,i}`$. Since this clearly implies $`_{i=0}^ne_i=0`$, we need not add any additional relations to $`G`$. (Although the canonical abelian height function space is the subgroup of $`G`$ generated by the values $`e_i=2e_{i,i+1}2e_{i1,1}`$, it will be notationally convenient to define $`\varphi `$ and our height functions in this larger group.) We can now describe our height function $`h_\alpha `$ for a tiling $`\alpha `$ with the following rules:

1. Let $`h_\alpha (v_0)=0`$ for all tilings $`\alpha `$ of $`R`$, where $`v_0`$ is a reference vertex on the boundary of $`R`$.
2. When moving from one vertex to a neighbor along an edge separating $`i`$ and $`i+1`$ color squares with color $`i+1`$ on the left, the height changes by $`e_{i,i+1}`$ if no tile of $`\alpha `$ is crossed.
3. When moving from one vertex to a neighbor along an edge separating $`i`$ and $`i+1`$ color squares with color $`i+1`$ on the left, the height changes by $`2e_{j,j+1}e_{i,i+1}`$ if the edge crosses a tile in $`\alpha `$ of type $`(j,j+1)`$.

We write $`h_\alpha ^{i,i+1}`$ to mean the $`e_{i,i+1}`$ component of the height function $`h_\alpha `$. Of course, there is some redundancy in using an $`n`$ dimensional height space instead of the canonical $`n1`$ dimensional height space; as currently defined, $`_{i=0}^{n1}h_\alpha ^{i,i+1}`$ is a function that does not depend on the tiling $`\alpha `$. In particular, if $`n=2`$, the projection sending $`ae_{0,1}+be_{1,0}`$ to the integer $`ab`$ transforms our two-dimensional $`h_\alpha `$ into the standard one-dimensional domino-tiling height function without any loss of information.

### 3.2. Interpretations of Ribbon Tiling Height Functions

We can understand what the height function means by looking at its behavior along diagonals. We say $`p`$ is an $`(i,i+1)`$ diagonal if:

1. The path $`p=v_0,\mathrm{},v_k`$ is a connected left-to-right path made solely of edges of type $`(i,i+1)`$ that are incident to squares in $`R`$.
2. Both $`v_0`$ and $`v_k`$ are on the boundary of $`R`$ and the extending edges $`(v_1,v_0)`$ and $`(v_k,v_{k+1})`$ of type $`(i,i+1)`$ are not incident to squares in $`R`$.

Note that as one moves from left to right along an $`(i,i+1)`$ diagonal, $`h_\alpha ^{j,j+1}`$ increases by two if we cross a a tile of type $`(j,j+1)`$ and zero otherwise. Thus, in the diagonal described above, $`h_\alpha ^{j,j+1}(v_i)`$ is equal to $`h_\alpha ^{j,j+1}(v_0)`$ plus twice the total number of times the path $`v_0,\mathrm{},v_i`$ crosses a tile of type $`(j,j+1)`$. In particular, since the value of $`h_\alpha `$ on the boundary of $`R`$ is independent of $`\alpha `$, we have the following.

###### Lemma 3.1.

If $`ji`$, then the total number of tiles of type $`(j,j+1)`$ crossed by the portion of an $`(i,i+1)`$ diagonal between two consecutive boundary vertices $`v_1`$ and $`v_2`$ is equal to $`\frac{1}{2}(h_\alpha ^{j,j+1}(v_2)h_\alpha ^{j,j+1}(v_1))`$. In particular, since $`v_1`$ and $`v_2`$ are boundary vertices, this number is independent of $`\alpha `$.

How does $`h_\alpha ^{i,i+1}`$ change along an $`(i,i+1)`$ diagonal? We know that moving from left to right along the diagonal, it decreases by one when we cross a tile, increases by one otherwise. Also, inspection shows that there can never be tiles crossing both of two adjacent edges on a diagonal. Thus, as one moves along the diagonal from left to right, the value of $`h_\alpha ^{i,i+1}`$ alternates between sequences of decreasing steps (of length at most one) and sequences of increasing steps (of length one or more). We say $`v_a`$ is a record vertex if $`a1`$, and $`h_\alpha ^{i,i+1}(v_b)<h_\alpha ^{i,i+1}(v_a)`$ whenever $`0b<a`$. For notational convenience, we will also consider $`v_{k+1}`$ (the vertex just right of the vertex $`v_k`$ along an edge of type $`(i,i+1)`$) to be a record vertex. (See Figure 4.)

Since each decreasing sequence in $`h_\alpha ^{i,i+1}`$ along $`p`$ has length at most one, it is not hard to check that if $`2ak`$, then $`v_a`$ is a record vertex if and only if $`h_\alpha ^{i,i+1}(v_a)>h_\alpha ^{i,i+1}(v_{a1})>h_\alpha ^{i,i+1}(v_{a2})`$. Note that the first edge $`(v_0,v_1)`$ and last edge $`(v_{k1},v_k)`$ of a diagonal are always boundary edges of $`R`$, and hence represent increasing steps. In particular, $`v_1`$ is always a record vertex.

What does it mean for $`v_a`$ to be a record vertex? First of all, it means that the two adjacent edges $`(v_{a2},v_{a1})`$ and $`(v_{a1},v_a)`$ are both not crossed by tiles; this in turn implies that the square $`s`$ incident to both of them (which we will call a record square) is either a square outside of $`R`$ or a square in $`R`$ belonging to a tile of type $`(i,i+1)`$. Since each of the integers $`h_\alpha ^{i,i+1}(v_0)+1,h_\alpha ^{i,i+1}(v_0)+2,\mathrm{},h_\alpha ^{i,i+1}(v_k)`$ must occur as a record value exactly once, the number of record vertices on the diagonal (not counting $`v_{k+1}`$) is equal to $`h_\alpha ^{i,i+1}(v_k)h_\alpha ^{i,i+1}(v_0)`$, and is hence independent of $`\alpha `$.

Now, if $`s`$ is a record square outside of $`R`$ and $`v_a`$ is the corresponding record vertex, the two diagonal edges preceding $`v_a`$ must both be boundary edges of $`R`$ (unless one is an edge outside of $`R`$); hence, $`s`$ will be a record square for every tiling of $`R`$. If $`ak+1`$, then the value $`h_\alpha (v_a)`$ is also independent of the tiling. Whenever $`s`$ is a record square outside of $`R`$, the corresponding record vertex is called a boundary record vertex; in particular, $`v_1`$ and $`v_{k+1}`$ are boundary record vertices.

Between any two consecutive boundary record vertices $`v_a`$ and $`v_b`$, there are exactly $`h_\alpha ^{i,i+1}(v_b)h_\alpha ^{i,i+1}(v_a)1`$ record vertices whose record squares are squares of tiles of type $`(i,i+1)`$. Whether the tile lies above or below the diagonal clearly depends on the parity of $`a`$; since $`h^{i,i+1}`$ alternates parity along the diagonal, this in turn depends on the parity of the $`h_\alpha ^{i,i+1}`$ at the record vertex $`v_a`$. We call $`v`$ a lower record vertex if the corresponding record square lies below the diagonal and an upper record vertex if it lies above the diagonal. Since for each $`\alpha `$, the record values $`h_\alpha ^{i,i+1}(v_0)+1,h_\alpha ^{i,i+1}(v_0)+2,\mathrm{},h_\alpha ^{i,i+1}(v_k)`$ must be attained in the same order, we have the following lemma:

###### Lemma 3.2.

Suppose $`q`$ is the portion of a diagonal $`p`$ of type $`(i,i+1)`$ between two consecutive boundary record vertices $`v_a`$ and $`v_b`$. Then the number tiles of type $`(i,i+1)`$ with squares adjacent to $`q`$ that lie above or below the diagonal is equal to $`h_\alpha ^{i,i+1}(v_b)h_\alpha ^{i,i+1}(v_a)1`$. In particular, this value is the same for every tiling of $`R`$. Furthermore, the order in which the entire diagonal $`p`$ encounters boundary record vertices, lower record vertices, and upper record vertices is also the same for every tiling of $`R`$ and can be determined from the value of the height function on the boundary vertices in $`p`$.

Denote by $`S_\alpha (p)`$ the set of squares adjacent to $`p`$ that are either members of tiles of type $`(i,i+1)`$ or squares in $`B_R`$. (See Figure 4.) Note that if $`s_1`$ and $`s_2`$ are two record squares then $`s_1s_2`$ if and only if the record vertex for $`s_1`$ occurs before that of $`s_2`$ in the diagonal. Thus, we can restate the previous lemma:

###### Lemma 3.3.

Given any two tilings $`\alpha `$ and $`\alpha ^{}`$, $`S_\alpha (p)`$ and $`S_\alpha ^{}(p)`$ contain the same number of boundary squares, squares of color $`i`$ in type $`(i,i+1)`$ tiles, and squares of color $`i+1`$ in type $`(i,i+1)`$ tiles. The relation $``$ induces a total ordering on the squares in $`S_\alpha (p)`$ as well as those in $`S_\alpha ^{}(p)`$; if the $`m`$th square in the ordering of $`S_\alpha (p)`$ is a boundary square (or a square of color $`i`$ in a type $`(i,i+1)`$ tile, or a square of color $`i+1`$ in a type $`(i,i+1)`$ tile), the same is true of $`S_\alpha ^{}(p)`$.

Now we are ready to prove Lemma 1.2, which we restate here for convenience.

###### Lemma 3.4.

Any two tilings $`\alpha `$ and $`\beta `$ of $`R`$ necessarily contain the same number of tiles of each level. Thus, $`t_{c,i}(\alpha )`$ is defined if and only if $`t_{c,i}(\beta )`$ is defined. Furthermore, if $`cd(modn)`$, then $`t_{c,i}(\alpha )t_{d,j}(\alpha )`$ if and only if $`t_{c,i}(\beta )t_{d,j}(\beta )`$. Also, if $`bB_R`$, then $`t_{c,i}(\alpha )b`$ if and only if $`t_{c,i}(\beta )b`$ . Similarly, $`bt_{c,i}(\alpha )`$ if and only if $`bt_{c,i}(\beta )`$.

###### Proof.

Let $`t_{c,1}(\alpha )t_{c,2}(\alpha )\mathrm{}t_{c,k}(\alpha )`$ be the tiles of type $`(i,i+1)`$ in $`\alpha `$ whose lowest squares lie just above a given diagonal $`p`$. It is obvious from the definition of $`t_{c,i}(\alpha )`$ that the ordering of these tiles with respect to each other is independent of $`\alpha `$. Similarly, let $`t_{cn,1}(\alpha )t_{cn,2}(\alpha )\mathrm{}t_{cn,m}(\alpha )`$ be the tiles of type $`(i,i+1)`$ that lie just below the diagonal $`p`$.

Now, let $`a_1a_2\mathrm{}a_r`$ be the totally ordered set of all the boundary squares and all of the $`k+m`$ tiles that are incident to $`p`$. Since we know that the ordering restricted to the set of tiles of form $`t_{c,i}(\alpha )`$ (or the set of tiles of form $`t_{cn,i}(\alpha )`$, or the set of boundary squares) is independent of $`\alpha `$, it follows from Lemma 3.3 that the total ordering $`a_1a_2\mathrm{}a_r`$ is independent of $`\alpha `$.

Since any two tiles of the same type or any tile and any square that are comparable by $``$ must be incident to some common diagonal $`p`$, Lemma 3.3 covers all possible cases in which the $``$ relation occurs between tiles of the same type or between tiles and boundary squares. ∎

The reader may recall from the introduction that we used this lemma used to define the partially oriented graph $`G_R`$ and to justify our interpretation of $`G_R\alpha `$ as an extension of the partial orientation of $`G_R`$. This will be the topic of the next section.

### 3.3. The Acyclic Orientation Correspondence

The purpose of this section is to prove Theorem 1.3; we will state and prove each of its four parts as a separate lemma.

###### Lemma 3.5.

For every order-$`n`$ ribbon tiling $`\alpha `$ of $`R`$, $`G_R(\alpha )`$ is an acyclic orientation extending the partial orientation of $`G_R`$.

###### Proof.

We must show that, given a tiling $`\alpha `$, there exists no sequence

$$a_0a_1a_2\mathrm{}a_ka_0,$$

where each $`a_i`$ is either a tile or a square in $`B_R`$.

Since there can clearly be no cycle containing one or two elements, we may assume $`k2`$. Now, suppose a diagonal incident to both $`a_0`$ and $`a_k`$ is also incident to some $`a_i`$ with $`0<i<k`$. If $`a_ka_i`$, then $`a_ia_{i+1}\mathrm{}a_ka_i`$ is a shorter cycle. If $`a_ia_k`$, then $`a_ia_0`$ (by transitivity, since $`a_i`$, $`a_k`$, and $`a_0`$ are on the same diagonal and hence totally ordered), and $`a_0a_1\mathrm{}a_ia_0`$ is a shorter cycle.

Thus, if $`a_0a_1a_2\mathrm{}a_ka_0`$ is a cycle of minimal length in $`G_R(\alpha )`$, then any infinite diagonal that is incident to both $`a_0`$ and $`a_k`$ can be incident to no other tile or square. Denote by $`p_z`$ the infinite diagonal between square levels $`z`$ and $`z+1`$ and let $`z^{}`$ and $`z^{\prime \prime }`$ be the lowest and highest values of $`z`$ for which $`p_z`$ is incident to both $`a_0`$ and $`a_k`$. All tiles and squares other than $`a_0`$ and $`a_k`$ must lie entirely below $`p_z^{}`$ or entirely above $`p_{z^{\prime \prime }}`$. Since no tile or square below $`p_z^{}`$ can be comparable with any tile or square above $`p_{z^{\prime \prime }}`$, the sequence $`a_1a_2\mathrm{}a_{k1}`$ must lie entirely above $`p_{z^{\prime \prime }}`$ or entirely below $`p_z^{}`$. Suppose without loss of generality that the former is the case and that the lowest square in $`a_0`$ is at least as low as the lowest square in $`a_k`$. Then none of the elements $`a_i`$ below $`p_z^{}`$ is comparable with $`a_k`$, and this is a contradiction. ∎

###### Lemma 3.6.

If $`\alpha `$ and $`\beta `$ are order-$`n`$ ribbon tilings then $`\alpha =\beta `$ if and only if $`G_R(\alpha )=G_R(\beta )`$.

###### Proof.

Obviously, the first statement implies the second. Now, suppose $`G_R(\alpha )=G_R(\beta )`$. Since these orientations are acyclic, there must exist at least one leftmost tile, i.e., there exists a $`t_{c,i}`$ for which there exists no $`t_{d,j}`$ with $`t_{d,j}(\alpha )t_{c,i}(\alpha )`$ or $`t_{d,j}(\beta )t_{c,i}(\beta )`$. It follows that $`t_{c,i}(\alpha )`$ and $`t_{c,i}(\beta )`$ must each contain the leftmost squares in $`R`$ in the rows of level $`c,c+1,\mathrm{},c+n1`$; thus, their positions are determined and they are equal. Similarly, we can now choose a $`t_{d,j}`$ that is leftmost among the remaining set of tiles, and its position is also completely determined. Repeating this argument, we conclude that $`t_{c,i}(\alpha )=t_{c,i}(\beta )`$ for all $`c`$ and $`i`$ for which these values are defined. ∎

###### Lemma 3.7.

Every acyclic orientation $`A`$ of $`G_R`$ that extends the partial orientation of $`G_R`$ can be written as $`G_R(\alpha )`$ for some tiling $`\alpha `$.

In the introduction, we defined $`G_R`$ by assuming that $`R`$ admitted at least one tiling $`\alpha `$ and restricting the orientation on $`G_R(\alpha )`$ to the forced edges. However, in our later existence proofs, it will be necessary to have a definition of $`G_R`$ and a version of Lemma 3.7 that do not invoke a priori knowledge of the existence of $`\alpha `$. To do this, we will need some definitions.

We say a tile vertex $`t_{c,i}`$ crosses level $`d`$ if $`cdc+n1`$. (Note that if $`\alpha `$ is a tiling, then $`t_{c,i}`$ crosses level $`d`$ if and only if $`t_{c,i}(\alpha )`$ contains a square of level $`d`$.) We define a partially oriented graph $`G`$ to be a ribbon tile graph consistent with $`R`$ if the following hold:

1. The vertices of $`G`$ come from the set of tile vertices $`t_{c,i}`$ (with $`c,i`$ and $`i>0`$) and square vertices $`s_{x,y}`$ (with $`x,y`$).
2. Two tile vertices $`t_{c,i}`$ and $`t_{d,j}`$ are adjacent if and only if $`|cd|n`$. A tile $`t_{c,i}`$ and square $`s_{x,y}`$ are adjacent if and only if $`c1x+yc+n`$. Two squares $`s_{x,y}`$ and $`s_{x^{},y^{}}`$ are adjacent if and only if $`|(x+y)(x^{}+y^{})|1`$.
3. The graph $`G`$ is endowed with an orientation on its forced edges (i.e. all edges involving a square or involving two tile vertices $`t_{c,i}`$ and $`t_{d,j}`$ with $`cd(modn)`$). No other edges of $`G`$ are oriented.
4. If $`s_1`$ and $`s_2`$ are square vertices, then the edge $`(s_1,s_2)`$ is oriented toward $`s_2`$ if and only if $`s_1s_2`$. Also, whenever $`i>0`$ and $`t_{c,i+1}`$ is a tile vertex, $`t_{c,i}`$ is also a tile vertex. An edge of the form $`(t_{c,i},t_{c,j})`$ is oriented toward $`t_{c,j}`$ whenever $`i<j`$.
5. The set of square vertices of $`G`$ is precisely the set of boundary squares of $`R`$.
6. The total number of tiles crossing a given level $`c`$ is precisely the number of squares in $`R`$ of level $`c`$.
7. For every integer $`c`$ and every pair of boundary squares $`b_1`$ and $`b_2`$ of levels $`c1`$, $`c`$, or $`c+1`$ satisfying $`b_1b_2`$, the number of tile vertices $`t_{d,j}`$ in $`G_R`$ that cross level $`c`$ and satisfy $`b_1t_{d,j}b_2`$ is precisely the number of squares $`s`$ in $`R`$ of level $`c`$ satisfying $`b_1sb_2`$.

Only the last three conditions depend on $`R`$; we will refer to these as the consistency conditions. Although it involves overloading the symbol $``$, we will write $`ab`$ whenever the edge $`(a,b)`$ is a forced edge of $`G`$ oriented toward $`b`$. If $`A`$ is an orientation extending the partial orientation on the forced edges of $`G`$, we write $`a_Ab`$ if the edge $`(a,b)`$ in $`G`$ is oriented from $`a`$ to $`b`$ in $`A`$.

Note that up to this point, we have defined $``$ only on actual tiles, not on the tile vertices $`t_{c,i}`$, which are abstract place holders for tiles. However, our expanded use of $``$ is consistent in the following sense: if $`G_R(\alpha )`$ is the ribbon tiling graph of a tiling $`\alpha `$ and the edge $`(t_{c,i},t_{d,j})`$ is forced, then $`t_{c,i}(\alpha )t_{d,j}(\beta )`$ if and only if $`t_{c,i}t_{d,j}`$ in $`G_R`$. Similarly, if $`A=G_R(\alpha )`$ and the edge is $`(t_{c,i},t_{d,j})`$ is not necessarily forced, then $`t_{c,i}(\alpha )t_{d,j}(\alpha )`$ if and only if $`t_{c,i}_At_{d,j}`$. Similar results apply to edges involving squares.

If $`R`$ admits a tiling $`\alpha `$ then the graph $`G_R`$ as defined in the introduction clearly satisfies the above list of requirements and is consistent with $`R`$. (In fact, $`G_R`$ is the only ribbon tile graph consistent with $`R`$ in this case.) Thus, the following is a slightly more general version of Lemma 3.7:

###### Lemma 3.8.

Suppose $`G_R`$ is any ribbon tile graph that is consistent with $`R`$. Then every acyclic orientation $`A`$ of $`G_R`$ that extends the partial orientation on the forced edges of $`G_R`$ is equal to $`G_R(\alpha )`$ for some tiling $`\alpha `$. (In particular, if $`R`$ does not admit an order-$`n`$ ribbon tiling, then no such $`G_R`$ and $`A`$ exist.)

###### Proof.

Suppose $`t=t_{c,1}`$ is a leftmost tile vertex in $`G_R`$. As in the previous proof, we will choose the leftmost squares of each of the levels $`c,c+1,\mathrm{},c+n1`$ and declare them to be our first tile $`t_{c,1}(\alpha )`$. That there exists at least one square in $`R`$ on each of these levels follows from the consistency conditions of $`G_R`$. However, we must verify that this set of squares is actually a ribbon tile. Since it contains one square on each of levels $`c,c+1,\mathrm{},c+n1`$, it is sufficient to show that it is connected.

Suppose otherwise; then we can assume without loss of generality that there exists some $`i`$ such that the leftmost square $`s_i`$ in the row of level $`c+i`$ is left of the square $`s_{i+1}`$ in the row of level $`c+i+1`$ but that these two squares are not adjacent. Now, let $`s_r`$ ($`s_l`$) be the square of level $`c+i+1`$ that is right of (left of) and adjacent to $`s_i`$. Both $`s_r`$ and $`s_l`$ must be squares in $`B_R`$, since they are adjacent to $`s_i`$ and they are left of $`s_{i+1}`$, the leftmost square of their level in $`R`$.

Now, by the consistency conditions, there is exactly one tile $`t^{}`$ containing a square on level $`c+i`$ such that $`s_lt^{}s_r`$; every other tile with a square on level $`c+i`$ must be right of $`s_r`$. If $`tt^{}`$, then $`t^{}s_rtt^{}`$, violating acyclicity. Hence $`t=t^{}`$. However, since $`s_r`$ is left of every square of level $`c+i+1`$, one may deduce from the consistency conditions that every tile vertex $`t`$ of $`G_R`$ that crosses level $`c+i+1`$ must satisfy $`s_rt`$. Thus $`ts_rt`$, a contradiction, and it follows that the squares chosen do in fact form a tile.

Now we form a new region $`R^{}`$ by removing the squares in this tile from $`R`$. We form a new graph $`G_R^{}`$ by removing $`t_{c,1}`$ from the vertex set of $`G_R`$—along with all boundary squares of $`R`$ that are not boundary squares of $`R^{}`$—and adding all the boundary squares of $`R^{}`$ that were not boundary squares of $`R`$. (These are necessarily members of our removed tile.) We define the edges of $`G_R^{}`$ and their orientations in a new orientation $`A^{}`$ in the most natural possible way. Two vertices of $`G_R^{}`$ are adjacent whenever the corresponding edges in $`G_R`$ were adjacent, and $`A^{}`$ is the orientation induced by $`A`$ on such edges. Furthermore, if $`s`$ is one of the new boundary squares and is in a row $`c`$, we declare it to be adjacent in $`G_R^{}`$ to every tile $`t`$ that crosses rows $`c1`$, $`c`$, or $`c+1`$ (with $`st`$) and every boundary square $`s_0`$ of those levels (with $`ss_0`$ if and only if $`s`$ is directly or indirectly left of $`s_0`$ and $`s_0s`$ when the opposite is true). Finally, if $`t_{c,j}`$ was a vertex of $`G_R`$ with $`j>1`$, we relabel it $`t_{c,j1}`$ in $`G_R^{}`$.

It follows easily from the definition that the $`G_R^{}`$ thus defined—together with the partial orientation on forced edges induced by $`A^{}`$—is a ribbon tile graph consistent with $`R^{}`$. If we can further prove that $`A^{}`$ is necessarily acyclic, then Lemma 3.8 will follow by induction.

Suppose $`A^{}`$ has a cycle; then this cycle must include a square $`s`$ of $`B_R^{}`$ that was a member of the tile $`t`$—otherwise the cycle would also be a cycle in $`A`$. Also, although the cycle may contain multiple squares from the removed tile, it must contain at least one element that is not a square of $`t`$, since the squares do not themselves contain any cycles. Suppose the cycle contains a sequence $`s_1\mathrm{}s_k`$ of former squares of $`t`$ but that the elements $`a`$ immediately preceding this sequence and $`b`$ immediately following it are not squares of $`t`$. Then we must have had $`atb`$ in $`A`$, and $`A`$ too must have had a cycle. ∎

###### Lemma 3.9.

Two order-$`n`$ ribbon tilings $`\alpha `$ and $`\beta `$ differ by a local replacement move if and only if $`G_R(\alpha )`$ and $`G_R(\beta )`$ differ by an edge reversal.

###### Proof.

First of all, we can determine whether a local replacement move involving tiles $`t_{c,i}(\alpha )`$ and $`t_{d,j}(\alpha )`$ can occur by applying the theory we have already developed to $`R^{}`$, the region tiled by just these two tiles. Now, if $`R^{}`$ admits two distinct tilings, then $`G_R^{}`$ must admit two distinct orientations that extend the orientation on the forced edges. In particular, $`G_R^{}`$ must contain at least one free edge, and that can only be the edge $`(t_{c,i},t_{d,j})`$. For this edge to be free, we must have $`0<|cd|<n`$.

Without loss of generality, suppose $`c<d`$. Notice that if $`dec+n1`$, then $`R^{}`$ contains two squares of level $`e`$. Inspection shows that if tile $`t_{c,i}(\alpha )`$ contains the leftmost square of one of these same-level pairs, it must contain the leftmost square of every such pair. (See Figure 5.) Moreover, if a tile contains one square on a row higher than $`c+n1`$ (lower than $`d`$), it must contain every square with this property. Thus, a local replacement move must consist of swapping the squares in each same-level pair. Such a swap produces a new pair of ribbon tiles if and only if the single square on row $`d1`$ (resp., $`c+n`$) is adjacent to both of the squares in row $`d`$ (resp., $`c+n1`$). Inspection shows that whenever there is no square $`s`$ with either $`t_{c,i}(\alpha )st_{d,j}(\alpha )`$ or $`t_{d,j}(\alpha )st_{c,i}(\alpha )`$, then a local move can in fact occur.

Now, if $`\beta `$ is the tiling obtained by applying such a move to $`\alpha `$, and $`t_{c,i}(\alpha )t_{d,j}(\alpha )`$ then inspection shows that we must have $`t_{d,j}(\beta )t_{c,i}(\beta )`$; it is also easy check that if $`a`$ is any tile or square outside of $`R^{}`$, then $`at_{c,i}(\alpha )`$ if and only if $`at_{c,i}(\beta )`$. Similarly, $`t_{c,i}(\alpha )a`$ if and only if $`t_{c,i}(\beta )a`$. It follows that if $`\alpha `$ and $`\beta `$ differ by a local replacement move, $`G_R(\alpha )`$ and $`G_R(\beta )`$ do in fact differ by the reversal of exactly one edge: the edge $`(t_{c,i},t_{d,j})`$.

For the converse, note that if the orientation of an edge $`(t_{c,i},t_{d,j})`$ of the orientation $`G_R(\alpha )`$ can be reversed without creating a cycle, we know there must be no vertex $`a`$ of $`G_R(\alpha )`$ with either $`t_{c,i}(\alpha )at_{d,j}(\alpha )`$ or $`t_{d,j}(\alpha )at_{c,i}(\alpha )`$; we have already shown that this is a sufficient condition for there to exist a local move involving the tiles $`t_{c,i}(\alpha )`$ and $`t_{d,j}(\alpha )`$, and so $`G_R(\beta )`$ must be the orientation obtained by reversing the edge. ∎

### 3.4. The Existence Algorithm

The main result of this section will be a linear-time algorithm for determining whether a simply connected region $`R`$ has an order-$`n`$ ribbon tiling and constructing such a tiling when one exists. To determine existence, we will make use of the well-known fact (which we later prove) that there exists an acyclic orientation $`A`$ of a graph $`G`$ that extends a given partial orientation of $`G`$ if and only if the partial orientation is itself acyclic. This implies the following corollary of Lemma 3.8:

###### Corollary 3.10.

Given $`R`$, there exists an acyclic partially oriented ribbon tiling graph $`G_R`$ that is consistent with $`R`$ if and only if $`R`$ admits an order-$`n`$ ribbon tiling.

Using this fact, we divide our algorithm into three steps.

1. We either produce an acyclic ribbon tile graph $`G_R`$ that is consistent with $`R`$ or prove that no such graph exists (and hence $`R`$ admits no order-$`n`$ ribbon tiling).
2. If we succeed in producing $`G_R`$ in the previous step, we describe a total ordering on the vertices of $`G_R`$ that induces the partial orientation of $`G_R`$ on the forced edges of $`G_R`$.
3. Given this totally ordering on the vertices of $`G_R`$, we describe a tiling of $`R`$.

Now, we know that if there is an acyclic ribbon tile graph $`G_R`$ that is consistent with $`R`$, we can use it to generate $`G_R(\alpha )`$ using the construction of Lemma 3.8, and the partial orientation on $`G_R`$ will thus be the restriction of $`G_R(\alpha )`$ to the forced edges in $`G_R`$. Thus, in the construction that follows, we can make use of lemmas proved earlier in the paper under the assumption that $`R`$ had a tiling. If $`R`$ does have a tiling, our assumption will have been correct. If $`R`$ does not have a tiling, these assumptions will lead to contradictions, and these will enable us to conclude that no tiling exists.

Now we begin to construct $`G_R`$. Let $`S(c)`$ be the number of squares of level $`c`$ and let $`T(c)`$ be the number of tiles whose lowest square is $`c`$. Clearly $`T(c)=S(c)_{i=1}^{n1}T(ci)`$, and is thus easily computed for each $`c`$ in linear time. (If it is not the case that $`T(c)0`$ whenever $`S(c)0`$ and $`T(c)=0`$ whenever $`S(c)=0`$, we can conclude that no tiling exists.) For each $`c`$ for which $`T(c)0`$, we include $`t_{c,i}`$ for $`1iT(c)`$ as tile vertices of $`G_R`$. We also include all the boundary squares of $`R`$ as square vertices of $`G_R`$. This $`G_R`$ has an edge whenever the corresponding tiles/squares are on levels that would make them comparable by $``$, and we require that $`t_{c,i}t_{c,i+1}`$ whenever both of these vertices are in $`G_R`$.

We would now like to determine an orientation on the forced edges of $`G_R`$ that will make $`G_R`$ a consistent ribbon tiling graph. We will not store in memory all of the edges of $`G_R`$ (as the number of such edges could be quadratic in the size of $`R`$); instead, we will observe that the partial orientation on $`G_R`$ induces a total ordering $`a_0a_1\mathrm{}a_k`$ on the set of squares and tiles of a given type that are all incident to a common diagonal. Since every forced edge can be derived from such an ordering on some diagonal, it will thus be sufficient for us to store in memory the actual orderings corresponding to each such type/diagonal pair, and this requires only a linear amount of memory.

Given an infinite diagonal $`p`$ between square rows of levels $`c1`$ and $`c`$ and some $`j\{1,2,\mathrm{},n1\}`$, let $`𝒮_{j,p}`$ be the set of tiles in $`G_R`$ of the form $`t_{cj,i}`$ together with squares in $`G_R`$ on levels $`c1`$ and $`c`$. Since the elements in $`S_{j,p}`$ share a common diagonal and all tiles in this set are of the same type, each pair of elements in $`S_{j,p}`$ is connected by a forced edge and hence $`G_R`$ induces a total ordering on this set. Now, we can compute the height function $`h`$ on the boundary of $`R`$, and using $`h`$, we can deduce this ordering explicitly from Lemma 3.1 as follows. Let $`k=cj1(modn)`$. Given consecutive boundary vertices $`v_1`$ and $`v_2`$ along the diagonal, we know that the number of tiles of the form $`t_{cj,i}`$ (and hence of type $`(k,k+1)`$) that cross $`p`$ between consecutive boundary vertices $`v_1`$ and $`v_2`$ must be $`\frac{1}{2}(h^{k,k+1}(v_2)h^{k,k+1}(v_1))`$. Clearly, if $`b_1`$ is a square incident to the diagonal $`p`$ immediately before $`v_1`$ and $`b_2`$ is a square incident to $`p`$ immediately after $`v_2`$, the number of tiles $`t`$ of the form $`t_{cj,i}`$ satisfying $`b_1tb_2`$ must be exactly $`\frac{1}{2}(h^{k,k+1}(v_2)h^{k,k+1}(v_1))`$. Thus, we can compute the number of tiles of $`S_{j,p}`$ in between each pair of boundary squares, and this completely determines the ordering.

Similarly, given an infinite diagonal $`p`$ between square rows $`c1`$ and $`c`$, let $`𝒮_{p,0}`$ be the set of tiles in $`G_R`$ of the form $`t_{c,i}`$ or $`t_{cn,i}`$ together with the squares in $`G_R`$ on levels $`c1`$ and $`c`$. Each pair of elements in $`𝒮_{p,0}`$ is connected by a forced edge, and thus the partial orientation on $`G_R`$ must induce a total ordering on this set. By Lemma 3.2 and Lemma 3.3, we can deduce this total ordering from the value of the height function on the boundary vertices of $`R`$ in $`p`$.

Since every forced edge involves two elements along the same diagonal, we can compute the orientation of each forced edge by repeating this process for each diagonal. Now we check that if $`G_R`$ is acyclic, it is necessarily a consistent ribbon tiling graph. It is enough to check the consistency conditions. By construction, $`G_R`$ contains all boundary squares, and by the definition of $`T(c)`$, the total number of tiles crossing each level $`c`$ is the number of squares in $`R`$ of level $`c`$. For the final consistency condition, suppose $`c`$ is given and $`b_1`$ and $`b_2`$ are boundary squares of types $`c1`$, $`c`$, or $`c+1`$ with $`b_1b_2`$.

Then let $`p_1`$ be the diagonal above the row of squares of level $`c`$ and let $`p_2`$ the diagonal below these squares. One easily checks that both $`p_1`$ and $`p_2`$ contain edges in each of $`b_1`$ and $`b_2`$. It suffices to check the condition under the assumption that there exists no boundary square $`b_3`$ incident to $`p`$ with $`b_1b_3b_2`$, since otherwise we can check the condition separately for the pair $`(b_1,b_3)`$ and the pair $`(b_3,b_2)`$. Say a vertex has level $`c`$ if it is a corner of squares of type $`c1`$, $`c`$, and $`c+1`$, and let $`q`$ be the portion of the diagonal connecting the last level $`c`$ vertex of $`b_1`$ to the first level $`c`$ vertex of $`b_2`$.

Then it follows by applying Lemma 3.1 to the diagonal $`p_1`$ (or to $`p_2`$ if $`p_1`$ has type $`(j,j+1)`$) that the number of tile vertices $`t`$ of type $`(j,j+1)`$ crossing $`c`$ and satisfying $`b_1tb_2`$ must be equal to $`\frac{1}{2}(h^{j,j+1}(v_2)h^{j,j+1}(v_1))`$. Write $`\overline{h}=_{j=0}^{n1}h^{j,j+1}`$, and note that the total number of such tile vertices must then be $`\frac{1}{2}(\overline{h}(v_2)\overline{h}(v_1))`$. However, this function is tiling-independent and in fact always increases by one as we move between squares of color $`j`$ and $`j+1`$ with $`j+1`$ on the left. It follows that if the vertices of the grid are labeled with coordinates $`(u,v)`$, then $`\overline{h}(u,v)`$ will be equal to $`uv`$ plus a constant. In particular, this implies that $`\frac{1}{2}(\overline{h}(v_2)\overline{h}(v_1))`$ is equal to the number of squares on level $`c`$ directly between vertices $`v_1`$ and $`v_2`$, and this is easily seen to be the number of level $`c`$ squares $`s`$ in $`R`$ satisfying $`b_1sb_2`$.

The only remaining step is to determine whether our partial orientation of $`G_R`$ is indeed acyclic. There are many of ways to do this in time linear in the number of edges of $`G_R`$. We say a forced edge $`(a,b)`$ of $`G_R`$ is essential if $`ab`$ and there exist no forced edges $`(a,c)`$ and $`(c,b)`$ with $`ac`$ and $`cb`$—one easily checks that the number of essential forced edges of $`G_R`$ is linear in the size of $`R`$ and that any acyclic orientation of $`G_R`$ that extends the partial orientation on the essential forced edges must extend the partial orientation on all forced edges. (See Figure 6.) The following algorithm for determining acyclicity (know as the topological sort) is well-known, and we will apply it to the graph formed by the vertices of $`G_R`$ and the essential forced edges of $`G_R`$.

Choose a starting vertex $`a_0`$ from the set of vertices of $`G_R`$ and attempt to construct an increasing path $`a_0a_1a_2\mathrm{}`$ until we either reach a point we have already visited (and we declare that there exists a cycle) or we reach a vertex $`a_k`$ that is not left of any of its neighbors. Clearly, $`a_k`$ cannot be part of a cycle, so we remove it and begin searching again with $`a_{k1}`$ (if $`k=0`$, we choose a new $`a_0`$ arbitrarily from among the remaining vertices of $`V`$). We continue this process until we have removed all the vertices of $`V`$ or we have found a cycle.

In the former case, if we list the elements of $`V`$ in the order in which they were removed from $`V`$, we have some ordering $`a_0,a_1,a_2,\mathrm{},a_k`$ in which $`i<j`$ implies $`a_ia_j`$ (since $`a_i`$ could otherwise not have been removed before $`a_j`$). Thus, we can define an acyclic orientation $`A`$ on $`G_R`$ by simply saying that whenever $`(a_i,a_j)`$ is an edge in $`G_R`$, $`a_j_Aa_i`$. Let $`\alpha `$ be the tiling for which $`G_R(\alpha )=A`$. Then if $`t_{c,i}`$ is the last tile that occurs in our ordering, we know that $`t_{c,i}(\alpha )`$ contains the leftmost squares of rows $`c,c+1,\mathrm{},c+n1`$. We know that the next to last tile $`t_{d,j}(\alpha )`$ contains the leftmost remaining squares of rows $`d,d+1,\mathrm{},d+n1`$, and so forth. Thus, given our ordering, it is easy to explicitly determine all the tiles of $`\alpha `$ in linear time. Note also that this algorithm yields an explicit proof of the fact (mentioned earlier) that every acyclic partial ordering of a graph has an acyclic extension.

## 4. General Tilings And Abelian Height-Functions

### 4.1. Examples

The constructions in this paper allow us in principle to work out the maximally informative abelian height function for any polyomino tiling problem. The following facts, for example, are simple to verify:

1. Given any coloring of the squares of $`R`$, a generalized ribbon tiling is a tiling in which each tile contains exactly one square of each color. Suppose, for example, we color the square at position $`(x,y)`$ one of $`mn`$ colors according to the values of $`x(modm)`$ and $`y(modn)`$. In this case, the canonical abelian height space is $`^{mn1}`$. (When $`m=n=2`$, this is the square/skew-tetromino tiling problem mentioned in .)
2. Let $`T`$ be the set of all polyominos with two black and two white squares in the usual chess board coloring. (These are squares, skew-tetrominos, and length-four vertical and horizontal bars.) The canonical abelian height function space is $`\times /2`$.
3. If $`T`$ contains all trominos, then the canonical abelian height space is trivial.
4. Let $`T`$ be the set of all rectangular $`m\times 1`$ tiles and $`1\times n`$ tiles. Then the canonical abelian height space is $`^{(m1)(n1)}`$. (This problem was studied in , where connectedness under local moves was proved using a non-abelian height function.)
5. If $`T`$ contains only horizontal dominos, then the canonical abelian height space is infinite dimensional.

### 4.2. Defining height functions at all vertices

In general, the height function $`h_\alpha `$ is only defined at the vertices of $`R`$ that are on the boundary of tiles of $`\alpha `$. One (admittedly awkward) way around this is to replace each tile with a spanning tree of the squares in that tile, and consider an edge in $`t`$ to be on the boundary if the squares it divides are not adjacent as members of the tree. (See Figure 7.) That is, if $`v_1`$ and $`v_2`$ are adjacent vertices in $`R`$, we say $`h_\alpha (v_2)h_\alpha (v_1)`$ is equal to $`\varphi (v_1,v_2)`$ when the squares incident to $`(v_1,v_2)`$ are either contained in different tiles or are contained in the same tile $`t`$ but are not adjacent as members of the spanning tree of $`t`$; this is enough to determine the value of $`h_\alpha `$ at every vertex $`v`$ in $`R`$—and this is now true even if we allow $`T`$ to contain non-simply-connected tiles.

Of course, the height values now depend on the particular choice of spanning tree for each tile; one might even consider each way of choosing a spanning tree of a tile $`t`$ to be a different tile in its own right. In this perspective, $`T`$ becomes a set of tile–spanning-tree pairs. Changing the spanning tree corresponding to a given tile is a sort of local replacement move.

### 4.3. Can distinct tilings have the same height function?

We saw in the examples that the abelian height function space for tromino-tilings is trivial; in this case, of course, all tilings of $`R`$ by trominos have the same (trivial) height function mapping all vertices to zero.

We will now describe a condition on tile sets $`T`$ that will ensure that two distinct tilings do not have the same height function. Given a map $`\varphi `$ from the squares of $`R`$ to the abelian height group $`G`$, we say a tile $`t`$ is admissible by $`\varphi `$ if $`\varphi (t)=0`$. We say $`t`$ is irreducible with respect to $`\varphi `$ if there is no way to partition $`t`$ into two or more smaller polyominos each of which is admissible. A tile set $`T`$ is irreducible if each tile is irreducible with respect to the map $`\varphi `$ from the squares of $`R`$ to the canonical abelian height space determined by those tiles. Note that these definitions depend only on the (canonically determined) values of $`\varphi `$ on squares $`s`$; they do not depend on any arbitrary choices we made when choosing the value of $`\varphi `$ on individual edges.

Now, consider two tilings $`\alpha `$ and $`\beta `$ of $`R`$ with the same height function $`h`$. We claim that each connected component $`u`$ of the intersection of any tile in $`\alpha `$ with a tile in $`\beta `$ satisfies $`\varphi (u)=0`$. To see this, let $`v_0,v_1,\mathrm{},v_k=v_0`$ be the vertices of a cycle surrounding $`u`$. Since each edge in this cycle is a boundary edge of either $`\alpha `$ or $`\beta `$, it follows that

$$\varphi (u)=\underset{su}{}\varphi (s)=\underset{i=1}{\overset{k}{}}\varphi (v_i,v_{i1})=\underset{i=1}{\overset{k}{}}h(v_i)h(v_{i1})=0,$$

where the second sum is over clockwise edges on the boundary of $`u`$. Unless $`u`$ is a tile in both $`\beta `$ and $`\alpha `$, it must be contained in a larger tile $`t`$ in one of the two tilings, say $`\beta `$. All the connected components of intersections of $`t`$ with tiles of $`\alpha `$ are admissible, and it follows that $`t`$ is reducible with respect to $`\varphi `$. We can now deduce the following:

###### Proposition 4.1.

If $`T`$ is irreducible, then no two tilings of $`R`$ by tiles in $`T`$ have the same height function.

This does not mean that height functions for reducible tile sets cannot provide useful information, but if a tile set is reducible, there may be aspects of the tiling that are not captured by the height function. A good example is the tile set $`T`$ containing all domino tiles and all skew tetromino tiles. The abelian height function for tilings by these tiles is simply the usual domino-tiling height function, where a skew tetromino is treated as a pair of dominos.

### 4.4. Which functions are height functions of a tiling?

Assume our height functions are defined at every vertex. Then for each oriented edge $`e=(v_1,v_2)`$ we define $`\mathrm{\Delta }_e`$ to be the set of all differences $`h_\alpha (v_2)h_\alpha (v_1)`$ that can possibly arise for a tiling $`\alpha `$ of any region $`R`$. Recall that:

$$h_\alpha (v_2)h_\alpha (v_1)=\varphi (v_1,v_2)+\varphi (s),$$

where the latter sum ranges over all squares passed on the left by the edge $`(v_1,v_2)`$. Thus the set $`\mathrm{\Delta }_e`$ is equal to $`\varphi (v_1,v_2)+L_e`$ where $`L_e`$ is the set containing $`0`$ and all possible square sums $`\varphi (s)`$ over sets of squares that can occur in the left side of a tile divided by $`e`$. Clearly, $`\mathrm{\Delta }_e=\mathrm{\Delta }_{e^1}`$.

We say a function $`h`$ from the vertices of $`R`$ to $`G`$ has proper differences with respect to the tile set if

1. $`h(v_2)h(v_1)=\varphi (v_1,v_2)`$ whenever $`(v_1,v_2)`$ is a boundary edge of $`R`$.
2. $`h(v_2)h(v_1)\mathrm{\Delta }_{(v_1,v_2)}`$ whenever $`(v_1,v_2)`$ is an interior edge of $`R`$.
3. $`h(v_0)=0`$ for some reference vertex $`v_0`$ on the boundary of $`R`$.

We say a tile set $`T`$ is complete if it is irreducible and for every simply connected region $`R`$, every function on $`R`$ with proper differences is the height function of a tiling of $`R`$ by tiles in $`T`$. For this definition, $`\varphi `$ is assumed to be the usual map from edges into a group $`G`$ containing the canonical abelian height space as a subgroup. Like the definition of irreducibility of $`T`$, this definition is independent of any arbitrary choices we made in choosing $`\varphi `$. To see this, note that if we add to $`\varphi `$ a function $`\varphi ^{}(e)`$ on the edges of $`^2`$ such that $`\varphi ^{}(s)=0`$ for any square, this simply amounts to adding a tiling-independent function to each $`h_\alpha `$ and adjusting the $`\mathrm{\Delta }_e`$ values accordingly. When a tile set is complete, there is a precise one-to-one correspondence between tilings of $`R`$ by that tile set and height functions on the vertices of $`R`$ with proper differences.

The fact that dominos are a complete set of tiles has been very important to the study of domino tilings; it is often easier to work with the space of height functions satisfying difference restrictions than to work directly with domino tilings. Completeness of domino tilings implies that existence algorithms and random sampling algorithms for domino tilings can all be derived from corresponding algorithms for spaces of height functions with proper differences.

### 4.5. Generalized Ribbon Tiling Completeness

We show here that any set of generalized ribbon tilings is complete. Given a coloring of the squares of $`^2`$ with $`n`$ colors, recall that a generalized ribbon tile set $`T`$ consists of all polyominos (together with corresponding spanning trees) that contain exactly one square of each color.

Let $`G`$ be the canonical abelian height space for the generalized ribbon tile set $`T`$. Although we do not in general know the structure of $`G`$, we can determine the structure of $`H`$, the quotient of $`G`$ with the relations $`\varphi (s_1)\varphi (s_2)=0`$ whenever $`s_1`$ and $`s_2`$ have the same color. Let $`\psi `$ be the composition of $`\varphi `$ with the quotient map sending $`G`$ to $`H`$ and observe that the value of $`\psi (s)`$ depends only on the color of $`s`$ (the same is not necessarily true of $`\varphi (s)`$). Let $`e_i`$ be the value of $`\psi (s)`$ when $`s`$ has color $`i`$.

Now $`H`$ is precisely the group generated by the $`e_i`$ subject to the one relation $`_{i=0}^{n1}e_i=0`$. (Because this relation is enough to force $`\psi (t)`$ to be zero for each $`tT`$, no additional relations are required.) It is easy to see that these tiles are irreducible: no nonempty proper subset of the $`e_i`$ sums to zero in $`H`$, so each sum of $`\varphi (s)`$ over a nonempty proper subset of the squares of a tile has nonzero image in $`H`$ and is hence a nonzero element of $`G`$.

Now, to show that $`T`$ is complete, we must show that every $`h`$ mapping the vertices of $`R`$ to $`G`$ with proper differences is the height function of a tiling $`\alpha `$. Suppose $`h`$ has proper differences. Given an edge $`e=(v_1,v_2)`$ in $`R`$, we define $`b(e)=h(v_2)h(v_1)\varphi (e)`$. By the definition of proper differences, $`b(e)`$ is the sum of $`\varphi (s)`$ over some set $`S(e)`$ of squares $`s`$—and there exists at least one tile $`tT`$ such that $`e`$ crosses $`t`$ and passes those squares on the left. In particular, this implies that $`S(e)`$ contains at most one square of each color and cannot contain a square of every color. Put differently, the set $`C(e)`$ of colors that occur in squares of $`S(e)`$ is a proper subset of $`\{1,2,\mathrm{},n\}`$, and the image $`\overline{b}(e)`$ of $`b(e)`$ in $`H`$ is simply $`_{jC(e)}e_j`$. We say $`e`$ has color $`j`$ on its left if $`jC(e)`$. Note that if $`e`$ has a square of color $`j`$ immediately to its right and $`h`$ has proper differences, then $`C(e)`$ can never contain $`j`$.

Now we will construct the tiling $`\alpha `$ for which $`h`$ is the height function. Let $`a_1`$, $`a_2`$, $`a_3`$, and $`a_4`$ be the clockwise oriented edges of a square $`s`$ with color $`i`$. If $`h`$ is a function with proper differences and $`v_0,v_1,v_2,v_3,v_4=v_0`$ are a path of vertices surrounding $`s`$ clockwise, we have:

$$0=\underset{k=1}{\overset{4}{}}h(v_k)h(v_{k1})=\underset{k=1}{\overset{4}{}}\varphi (a_k)+b(a_k)=\varphi (s)+\underset{k=1}{\overset{4}{}}b(a_k)$$

Taking the image of the latter sum in $`H`$ gives

$$0=e_i+\overline{b}(a_k)=e_i+\underset{k=1}{\overset{4}{}}\underset{jC(a_k)}{}e_j$$

Since none of the $`C(a_k)`$ can contain $`i`$; it is easy to see that the only way $`\overline{b}(a_k)`$ can be $`e_i`$ in $`H`$ is if the sum includes exactly one term of type $`e_j`$ for each $`ji`$. Thus, for $`1k4`$, the $`C(a_k)`$ are disjoint, and their union contains all colors except $`i`$.

Now, we say $`s_1`$ and $`s_2`$ are tile adjacent if they are adjacent and the edge $`e`$ between them has a nonempty $`S(e)`$. We define our tiles to be the connected components of the tile-adjacency relation. If we can show that every tile contains exactly one square of each color, we will have proved the completeness of $`T`$.

Suppose $`s_0`$ has color $`i`$, and choose some $`ji`$. We aim to show that $`s_0`$ is in the same tile as a square of color $`j`$. Observe that at least one edge of the four clockwise edges of $`S`$ has color $`j`$ on its left. Let $`s_1`$ be the square adjacent to $`s_0`$ that is incident to the edge $`e`$ for which this is the case. Clearly, $`s_1`$ does not have color $`i`$. If it has color $`j`$, we are done. Otherwise, suppose $`a_1`$, $`a_2`$, and $`a_3`$ are the three other clockwise oriented edges of $`s_1`$. We know that the union of the $`C(a_i)`$ and $`C(e^1)`$ contains all colors except the color of $`s_1`$. Since $`C(e^1)C(e)=\{1,2,\mathrm{},n\}`$, it follows that each of the $`C(a_i)`$ is a proper subset of $`C(e)`$ and that one of them contains $`j`$. Now, we let $`s_2`$ be the square adjacent to $`s_1`$ and incident to the edge for which this is the case and repeat this process. Since the proper subsets cannot decrease in size indefinitely, we must eventually reach a square of color $`j`$. A similar argument shows that such a path starting at $`s_0`$ never reaches another square of color $`i`$. It follows that each tile contains exactly one square of each color and that the adjacency relation describes a spanning tree of that tile.

Using similar arguments, one can show that the tile set containing all $`1\times k`$ and $`m\times 1`$ rectangles is complete.

### 4.6. Completion of a Tile Set

A good example of a tile set that is irreducible but not complete is, when $`n3`$, the set of ribbon tiles of order $`n`$ with all but one of the possible ribbon tile shapes.

When is it possible to add tiles to an incomplete tile set $`T`$ to make it complete? First, it is clear that we will have to add as a tile every finite region $`R`$ on which there exists a height function $`h`$ with proper differences such that the set $`S`$ of edges $`(v_1,v_2)`$ in $`R`$ for which $`h(v_2)h(v_2)=\varphi (v_1,v_2)`$ does not divide the squares of $`R`$ into more than one component. (There may be an infinite number of such regions, and they may be arbitrarily large.) Note that since all of these new tiles are already admissible by $`\varphi `$, adding these tiles will not change the canonical abelian height space, and we can use the same $`\varphi `$ to define height functions for the new tiling.

If each of these new tiles is irreducible, the result is a complete set of tiles, called the completion of $`T`$.

### 4.7. Non-Existence Proofs for Complete Tile Sets

Conway-Lagarias  and Thurston  observed that a simple necessary condition for the existence of a tiling on $`R`$ is that the height function be well-defined on the boundary of $`R`$. That is, the group-wise sum of $`\varphi (e)`$ around the all the edges $`e`$ of $`R`$ must be the identity.

It is not difficult to describe much stronger necessary conditions. If a tile set $`T`$ is complete and $`R`$ is a simply-connected region, then (assuming the previous condition is satisfied) the question of whether $`R`$ can be tiled by $`T`$ reduces to the question of whether there is a height function on the vertices of $`R`$ with proper differences. Even if $`T`$ is not complete, the existence such a function is a necessary condition for the existence of a tiling of $`R`$. Thus, the following interpolation problem is of interest:

Given a simply connected region $`R`$, a function $`h`$ defined on all boundary vertices of $`R`$, and a set $`\mathrm{\Delta }_e`$ for each oriented edge (with $`\mathrm{\Delta }_e=\mathrm{\Delta }_{e^1}`$ for all $`e`$), is it possible to interpolate $`h`$ to all vertices of $`R`$ in such a way that $`h(v_2)h(v_1)\mathrm{\Delta }_{(v_1,v_2)}`$ whenever $`(v_1,v_2)`$ is an edge in $`R`$?

When the height function space is a rank $`n`$ free-abelian group, this is a special case of integer programming, which is in general NP-complete. But suppose we embed the height space in $`^n`$ and let $`\overline{\mathrm{\Delta }_e}`$ be the convex hull of the set of points in $`\mathrm{\Delta }_e`$. Then a relaxed version of the problem asks for an interpolation of $`h`$ to the interior squares of $`R`$ where $`h`$ is allowed to assume any values in $`^n`$ and the differences are merely required to lie in $`\overline{\mathrm{\Delta }_e}`$. Since each $`\overline{\mathrm{\Delta }_e}`$ is a convex polyhedron, this is now a linear programming problem that can be solved in polynomial time. If we prove that there is no solution to the relaxed interpolation problem, we know $`R`$ cannot be tiled by $`T`$.

### 4.8. Note on Multiply Connected $`R`$

Suppose that $`R`$ is simply connected except for $`k`$ “islands,” labeled $`I_1,\mathrm{}I_k`$; we assume that the boundary edge/vertex sets of the boundary of each $`I_k`$ and the outer boundary of $`R`$ are disjoint, but that each $`I_i`$ is connected.

The problem with defining height functions on $`R`$ is that as we traverse the boundary of a given $`I_k`$ clockwise and come back to the same place, the height function changes by $`\varphi (I_i)`$; thus, if $`\varphi (I_i)0`$, then the height function $`h_\alpha `$ is not well-defined as a single-valued function. There are two ways around this problem. One is simply to accept that $`h_\alpha `$ is a multiple-valued function; only the differential $`h_\alpha (v_1,v_2)=h_\alpha (v_2)h_\alpha (v_1)`$, is well defined, and this can be integrated to produce a single-valued $`h_\alpha `$ on the vertices of any simply connected subset of $`R`$—but not all of $`R`$.

Second, we could choose some replacement $`\varphi ^{}`$ for $`\varphi `$ satisfying:

1. $`\varphi ^{}(I_i)=0`$ for each island $`I_i`$.
2. $`\varphi ^{}(s)=\varphi (s)`$ for each $`s`$ in $`R`$.

It is not hard to see that such a $`\varphi ^{}`$ always exists. If we define $`h_\alpha `$ using $`\varphi ^{}`$ instead of $`\varphi `$, then it is everywhere defined. We require $`h_\alpha (v_0)=0`$ for some outer boundary vertex $`v_0`$, and we also choose one vertex $`v_i`$ on each island $`i`$. Clearly, the value of $`h_\alpha `$ on all boundary vertices is determined by its value on the $`v_i`$.

In the special case of ribbon tilings, we define a simple local replacement move on $`R`$ to be a move that involves removing two tiles $`t_1`$ and $`t_2`$ that together comprise a simply connected two-tile region $`R^{}`$ and replacing them with another pair of tiles. When $`R`$ is simply connected, no tiling of $`R`$ ever contains a pair $`t_1`$ and $`t_2`$ of tiles whose union is connected but not simply connected—otherwise, there would be a hole between them that could not be filled by order-$`n`$ ribbon tiles. Thus, when $`R`$ is simply connected, every possible local replacement move is simple. It is not hard to show in general that two order-$`n`$ ribbon tilings $`\alpha `$ and $`\beta `$ on $`R`$ can be connected by a sequence of simple local replacement moves if and only if $`h_\alpha (v_i)=h_\beta (v_i)`$ for each $`i`$. The reader may also check that when $`n<4`$, every local replacement move is simple.

## 5. Open Problems

The domino tiling problem is perhaps the most well understood of all tiling problems. Height functions and local replacement moves have played a fundamental role in the proofs of many domino tiling theorems, including the following.

1. Proofs of local-move connectedness.
2. Algorithms for computation of minimal-length local move sequences connecting two tilings.
3. Linear algorithms for determining when a region $`R`$ has a tiling.
4. Mixing time bounds on random processes based on local moves. ,
5. Perfect sampling algorithms based on “coupling from the past.”
6. Asymptotic entropy computations for random tilings and descriptions of finite and asymptotic Gibbs measures. ,
7. Law of large numbers and large deviations principles for asymptotic height function shapes of random tilings.
8. Conformal invariance of certain tiling properties in the asymptotic scaling limit.

These results and references are ridiculously far from exhaustive; there have been numerous papers relating to each of the above topics and many others. We include the references not to assign credit, necessarily, but to provide pointers to papers with more complete bibliographies. Because ribbon tilings are in many ways the simplest polyomino tilings that generalize domino tilings, the following question is very natural:

###### Question 5.1.

Which of the above results can be generalized to ribbon tilings?

An additional task is to generalize to other tiling spaces with abelian height functions.

###### Question 5.2.

Can connectedness under local replacement moves be generalized to the other tiling problems in this paper? In particular, is there a local move result for every complete, translation-invariant tile set?

Finally, the author hopes this paper will be a step towards a more thorough understanding of at least the abelian case of the Conway-Lagarias height function theory. The following is a more theoretical question:

###### Question 5.3.

Is there a simple classification of the complete, translation invariant tile sets with finitely many tile shapes? Given such a tile set $`T`$, is there always a polynomial algorithm for determining whether a simply connected region can be tiled by $`T`$?

## 6. Acknowledgements

Many thanks to Henry Cohn for bringing the problem to my attention, for numerous helpful conversations, and for reviewing early drafts of the paper. Thanks also to László Lovász for helpful conversations and to Igor Pak for suggesting additional references.


format: text

text:
# Production of 𝜔 mesons in proton-proton collisions

## Abstract

The cross section for the production of $`\omega `$ mesons in proton-proton collisions has been measured in a previously unexplored region of incident energies. Cross sections of $`\sigma `$ = (7.5 $`\pm `$ 1.9) $`\mu `$b and $`\sigma `$ = (30.8 $`\pm `$ 3.4) $`\mu `$b (with 20% systematic uncertainties) were extracted at $`ϵ`$ = 92 MeV and 173 MeV excess energy above the $`\omega `$ threshold, respectively. The angular distribution of the $`\omega `$ at $`ϵ`$ = 173 MeV is strongly anisotropic, demonstrating the importance of partial waves beyond pure s-wave production at this energy.

thanks: This work was sponsored in part by the BMBF and the Forschungszentrum Jülich.

The COSY-TOF collaboration

, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

The production of mesons in nucleon-nucleon reactions is currently being investigated both experimentally and theoretically because of its implications for the understanding of the nuclear force. In the early nineties, the comparison of theoretical predictions to newly emerging experimental results on near-threshold meson production, in particular on pp$`\pi `$0  and, to a lesser extent, also other channels, revealed the rather poor understanding of the reaction mechanism of inelastic collisions between nucleons. Since then, a wealth of data has been accumulated for a number of mesons in the pseudoscalar sector, e. g. $`\pi `$, $`\eta `$, $`\eta `$’, and K. Recently, investigations in the vector meson sector ($`\rho `$, $`\omega `$, $`\varphi `$) have come into focus. The exchange of these mesons dominates the nucleon-nucleon interaction at short distances.
The comparison of production cross sections of $`\omega `$ to that of $`\varphi `$ mesons may shed light on a possible contribution of strange quark-antiquark pairs in the nucleon. While the $`\varphi `$ contains almost only $`s\overline{s}`$, the $`\omega `$ wave function is practically decoupled from the strange sector, consisting of $`u\overline{u}`$$``$$`d\overline{d}`$ only. The $`\varphi `$ production should therefore be strongly suppressed, as predicted by the OZI rule . A small contribution of 4$``$10-3 is expected because the mixing angle, $`\mathrm{\Theta }`$V $``$ 39 , deviates by 3.7 from that of a perfectly decoupled system in SU(3), $`\mathrm{\Theta }`$V = 35.3.
Recently, the DISTO collaboration found that the $`\varphi `$/$`\omega `$ production exceeds the OZI prediction by about one order of magnitude . Their published data, however, were measured at one beam momentum setting of Pc = 3.67 GeV. Thus, the available kinetic energy in the overall CoM system (often referred to as excess energy, $`ϵ`$) is $`ϵ`$ = 85 MeV above the $`\varphi `$ threshold but 320 MeV for the much lighter pp$`\omega `$ system. The extrapolation down to 85 MeV which covers more than one order of magnitude in cross section is far from straightforward. It is guided only by reference data measured below $`ϵ`$ = 30 MeV . Measurements of $`\omega `$ production between $`ϵ`$ = 30 MeV and 300 MeV are crucial for a more detailed investigation of the excitation function and, thus, OZI violation in pp collisions.
While the $`\varphi `$ angular distribution measured by the DISTO collaboration  is isotropic and therefore compatible with mere s-wave production, the $`\omega `$ distribution shows strong contributions from higher partial waves. If these persist at lower energies, as is the case in one of the possible scenarios in a recent theoretical calculation of Nakayama and coworkers , a quantitative comparison of $`\varphi `$ and $`\omega `$ production may not be possible without a more detailed understanding of the underlying (and perhaps different) reaction mechanisms. Hence, experiments should aim at exclusive differential observables at lower excess energies.
In a first attempt to contribute to the issue of $`\omega `$ production in proton-proton collisions, data from an experiment at the Time-of-Flight spectrometer TOF located at an external beam line of the COoler SYnchrotron COSY at the Forschungszentrum Jülich were analyzed for a signal from $`\omega `$ production. The experimental setup was described in detail elsewhere . The proton beam extracted from the synchrotron impinges on a thin liquid hydrogen target . In the present case, beam momenta of Pc = 2.95 GeV and 3.2 GeV are used. The reaction products leaving the target into the forward hemisphere generate, in a thin scintillator, a start signal for the successive time-of-flight measurement, then penetrate a silicon detector and two scintillating-fiber hodoscopes which permit an accurate track reconstruction needed for the detection of sequential hyperon decay . After flight paths of more than 3 m in vacuum the particles are detected in a scintillator assembly with high angular coverage and good spatial and time resolution which consists of a barrel section  and a forward structure closing the cylindrical detector at small angles . The detector covers polar angles from about 1 up to 70.
The velocity vectors of charged particles thus measured were used in the analysis presented here. Events with four hits were selected for further inspection. A geometrical separation was applied in order to enrich events of the type pp$`\pi `$+$`\pi `$-, where the pions may originate from the decay of an intermediate resonance, e.g. $`\eta `$$``$$`\pi `$+$`\pi `$-$`\pi `$0 (BR 23%), $`\rho `$0$``$$`\pi `$+$`\pi `$- (BR 100%) or $`\omega `$$``$$`\pi `$+$`\pi `$-$`\pi `$0 (BR 89%), requiring two tracks with angles $`\theta `$ $``$ 25 (assumed to be protons) and two more hits at larger angles (corresponding to the charged pions). This particle assignment is justified by kinematics which confines protons from pp$`\omega `$ reactions to the forward cone, while the much lighter pions can reach larger angles. The proton identification was further improved by a condition on velocities which rejects particles with velocities in excess of that of the beam. The proton four-momenta were used to calculate the missing mass of a hypothetical third particle, X. If X was a $`\rho `$0, which exclusively decays into two charged pions, both pion directions can be combined to give the four-momentum of X. This also holds in case of non-resonant two-pion production where the four-momentum of X reconstructed from the missing-mass analysis of ppX and that calculated with the X$``$$`\pi \pi `$ hypothesis are required to agree within the detector resolution. In case of $`\omega `$ decay into three pions, a $`\pi `$0 will be missing so that the detected pion pair will in most cases not be consistent with a two-body decay of X. This is demonstrated in figure 1, where spectra of the angle of acoplanarity between the pion directions with respect to the decaying meson are shown for the data (large frame) and for simulated $`\rho `$0$``$$`\pi `$+$`\pi `$-, $`\eta `$$``$$`\pi `$+$`\pi `$-$`\pi `$0 and $`\omega `$$``$$`\pi `$+$`\pi `$-$`\pi `$0 events. The acoplanarity was defined as the deviation of the angle between the momenta of the pions taken in the rest frame of the decaying meson from 180 (i.e. back-to-back emission). The CoM momenta of the pions were calculated assuming a two-body decay of the primary meson X, as is the case for the $`\rho `$. In cases where this assumption holds, the deviation from a 180 opening angle remains small and peaks at 0. The data clearly show a large two-pion production branch, which is rejected in the subsequent analysis as indicated by the dashed vertical line. Only events with acoplanarities larger than 25 were associated with three-body decays, $`\pi `$+$`\pi `$-Y. This criterion rejects more than 90% of the two-body events while reducing the amount of $`\omega `$ events by only 30%. Hence, it permits a clean identification of the $`\omega `$ production above a non-resonant background, mostly with multiplicities nπ $``$ 3 as shown in the missing mass plot of figure 2. The apparent width of the resonance is dominated by the detector resolution of $`\sigma `$ $``$ 30 MeV at this energy. The $`\eta `$-meson also decays into three pions with 23% probability. The cross section for $`\eta `$-production at these energies is about five times larger than that for $`\omega `$ production. Therefore, an appreciable amount of events in the figure may be due to $`\eta `$ production. Because of the much lower mass of the $`\eta `$ and the correspondingly higher available energy, the angular restrictions on the proton directions and velocities reduce the acceptance for $`\eta `$ events to 1.9% compared with 6.4% for the $`\omega `$ and less than 0.5% for the $`\rho `$ contribution to the spectrum in figure 2. Since the available energy is large, the protons which are detected in case of $`\eta `$ production will have large velocities. Therefore, the missing mass resolution for $`\eta `$ mesons is much worse than for the heavier and kinematically constrained $`\omega `$, so that an $`\eta `$ signal is not observed in figure 2. The emission direction of X was restricted to forward emission, $`\theta `$$`{}_{}{}^{}{}_{X}{}^{}`$ $``$ 90. This event pattern is also favored by the detector acceptance. It yields protons sufficiently low in energy to allow calculation of the missing mass with the quoted precision, while the backward emission of X boosts the protons to higher velocities so that the missing-mass resolution degrades with increasing angle of X. The experimental mass spectrum (data points with statistical errors) exhibits a peak at the $`\omega `$ mass which is well reproduced in shape and position by the detector Monte Carlo (hatched peak for the $`\omega `$) when added to a parametrized background, as shown by the shaded spectrum. The small remaining shift in position is due to calibration uncertainties in the time-of-flight determination. The missing mass peak of figure 2 can be integrated to yield the total number of $`\omega `$ mesons produced. Different background shapes were applied in fits to the distribution. They produce cross sections for the $`\omega `$ which are consistent to within $`\pm `$10%. The background used in producing figure 2 is taken to be a third order polynomial which has been fitted to the distribution above and below the peak in the indicated region. While, in principle, a background estimation using simulations which incorporate non-resonant as well as resonant multi-pion production appears desirable, the lack of differential cross section data prevents doing so.
The normalisation of the data requires a luminosity calibration which is easily accomplished in our experiment due to the simultaneous measurement of elastically scattered protons over a wide angular range. These data can then be compared to the results of other experiments which measured the elastic scattering to a high level of precision (see e.g. ) and/or phase shift analyses . The overall normalisation uncertainty from this procedure is estimated to be about 5%. After correction for the acceptance of the setup using Monte Carlo simulations, total cross sections can be deduced. They are shown in figure 3 together with results from the literature  and theoretical calculations . The acceptance calculations include detector resolution as well as all the conditions applied to the data. The overall acceptance for $`\omega `$ events at 173 MeV is 6.4% with only a small modulation with angle (7.1% at 92 MeV). A systematical uncertainty which is larger than the statistical errors comes about when an angular distribution of the $`\omega `$ mesons is taken into account in the acceptance calculations. To this end, the isotropic three-body phase space was modified in an iterative procedure to fit the observed anisotropy (cf. figure 4) at 173 MeV. This changes the deduced cross section by almost 20%. Since the current analysis does not permit the extraction of angular distributions at the lower energy, anisotropies cannot be excluded in this case. It is however reasonable to assume that these will not exceed those determined at twice the excess energy, so that the same anisotropy was used for both energies to estimate the resulting change in cross section. This prescription yields a decrease in cross section by 13% (about half of the statistical error) at the lower energy and an increase by 19% at the higher energy (almost twice the statistical error). This is caused by the different ranges of momenta accessible to the $`\omega `$ and protons at the two energies. In particular, the kinematic focussing of the pions from $`\omega `$ decay is very different in both cases. This changes the acceptance of the detector differently at the two energies. The displayed cross sections are $`\sigma `$ = (7.5 $`\pm `$ 1.9) $`\mu `$b at $`ϵ`$ = 92 MeV and $`\sigma `$ = (30.8 $`\pm `$ 3.4) $`\mu `$b at 173 MeV, respectively, where in the latter the angular distribution of the ejectiles was taken into account in the acceptance correction. The corrections to the data due to background subtraction, acceptance calculations employing various conditions such as, e.g., using phase space distributions for the $`\omega `$ decay pattern instead of the vector meson decay, do not alter the deduced cross sections by more than 20% as was also obtained from the anisotropy considerations. Thus, we conclude that the absolute numbers for the total cross sections given here are subject to systematic uncertainties not larger than 20% which are included in the error bars of figure 3.
Neither of the theoretical excitation functions based on parametrizations of one-pion exchange model calculations (dotted  and dash-dotted  lines in figure 3) is able to describe the measured data at low energy. The parametrization given by Sibirtsev  comes closer to the data than the one by Cassing  but fails below 90 MeV where final state interactions may start to contribute.
There is a general agreement among various theorists  that $`\omega `$ and $`\varphi `$ production, when viewed in a meson exchange picture, can be ascribed to two dominant contributions which are called ”nucleonic” when the meson is emitted by one of the nucleons (NN$`\upsilon `$ vertex, $`\upsilon `$ denotes either vector meson, $`\varphi `$ or $`\omega `$) in contrast to the ”mesonic” current where the emitted vector meson originates from the exchanged meson, e.g. from a $`\rho `$$`\pi `$$`\upsilon `$ vertex. The solid and dashed lines in figure 3 show two calculations by Nakayama et al.  within such a model. Different sets of parameters for both the nucleonic and mesonic currents were used. The parameters for $`\varphi `$ and $`\omega `$, in particular the coupling constants, were related by SU(3) considerations. The form factor for the mesonic current was fixed to the $`\varphi `$ angular distribution at 85 MeV which is flat to within the - rather large - experimental errors . The vector coupling constants for the $`\rho `$$`\pi `$$`\upsilon `$ vertices were taken from $`\varphi \rho \pi `$ and $`\omega \gamma \pi `$ decay, respectively, while the tensor-to-vector ratio was varied within reasonable limits, $`\kappa `$υ = $`\pm `$0.5. Left with the cutoff parameter for the nuclear contribution’s form factor, the total pp$`\omega `$ cross sections  were fitted. Finally, the NN$`\varphi `$ coupling constant was adjusted to fit the nuclear contribution to the $`\varphi `$ angular distribution. While both calculations fail to reproduce our data, the solution with negative tensor coupling, $`\kappa `$υ = -0.5 (solid line), gives a better agreement in overall shape. It uses a rather small cutoff parameter, $`\mathrm{\Lambda }`$N = 1170 MeV, and results in a coupling constant of gNNϕ = -0.45. Because of the decreasing nuclear contribution with decreasing $`\mathrm{\Lambda }`$N and the destructive interference of vector and tensor currents, this solution results in an angular distribution which is completely dominated by the mesonic current. Hence, a flat distribution is expected, as is indeed observed in the case of $`\varphi `$ production. However, the anisotropic pp$`\omega `$ angular distribution for an excess energy of 173 MeV which is shown in figure 4 suggests that this parameter set cannot describe the $`\omega `$ production. The figure does not include the most backward-emitted mesons because of the forementioned bias toward low-momentum protons needed in the analysis. Since the entrance channel is symmetric the distribution has to be symmetric about $`\mathrm{cos}\theta `$$`{}_{}{}^{}{}_{\omega }{}^{}`$ = 0 as indicated by the two data points below $`\mathrm{cos}\theta `$$`{}_{}{}^{}{}_{\omega }{}^{}`$ = 0. The angular distribution of protons was indeed found to be symmetric. The acceptance corrections used to determine the differential cross sections were deduced separately for each interval in $`\mathrm{cos}\theta `$$`{}_{}{}^{}{}_{\omega }{}^{}`$. A decrease in acceptance from 12% to 7% is observed when going from $`\mathrm{cos}\theta `$$`{}_{}{}^{}{}_{\omega }{}^{}`$ = 0 to $`\mathrm{cos}\theta `$$`{}_{}{}^{}{}_{\omega }{}^{}`$ = 1, while the $`\omega `$ yield increases by a factor of two over the same range. Hence, the observed anisotropy is somewhat amplified by the acceptance correction, however the effect is already contained in the uncorrected data. The strong anisotropy which was also observed in  for 320 MeV excess energy suggests that higher partial waves may be present even at lower energy where, according to , this may be viewed as direct proof of the dominance of nucleonic currents. A fit with the lowest two even Legendre polynomials yields coefficients of a2/a0 = 2.5($`\pm `$0.3) / 2.6($`\pm `$0.1) compared to 3.1($`\pm `$0.2) / 4.0($`\pm `$0.1) at 320 MeV  where, in addition, a P4 contribution was needed which is not required here.
Using our $`\omega `$ cross section value at 92 MeV together with the $`\varphi `$ cross section  at 85 MeV yields a production ratio $`\sigma `$ϕ/$`\sigma `$ω of about (3 $`\pm `$ 1)%. This is, although smaller than the DISTO estimate without the current cross section, about a factor of 7 larger than the OZI prediction. The uncertainty is dominated by the experimental error on the $`\varphi `$ cross section. The current result also exceeds the prediction of about 1% for the ratio at this energy in  for small NN$`\varphi `$ coupling. More detailed studies are however needed before final conclusions will emerge.
With envisaged improvements in experimental techniques, especially in accepted luminosity, also $`\varphi `$ production may come into reach at COSY. Further experimental investigations will then help to shed light on the question of the strange content of the nucleon adressed in vector meson production.

The authors would like to express their gratitude to the COSY staff for the operation of the accelerator during the experiment. Fruitful discussions with C. Hanhart, K. Nakayama and J. Ritman are gratefully acknowledged.