Ribbon Tilings and Multidimensional Height Functions
| dc.creator | Sheffield, Scott | |
| dc.date | 2001-07-12 | |
| dc.date | 2001-12-07 | |
| dc.date.accessioned | 2026-07-07T04:42:35Z | |
| dc.date.available | 2026-07-07T04:42:35Z | |
| dc.description | We fix $n$ and say a square in the two-dimensional grid indexed by $(x,y)$ has color $c$ if $x+y \equiv c \pmod{n}$. A {\it ribbon tile} of order $n$ is a connected polyomino containing exactly one square of each color. We show that the set of order-$n$ ribbon tilings of a simply connected region $R$ is in one-to-one correspondence with a set of {\it height functions} from the vertices of $R$ to $\mathbb Z^{n}$ satisfying certain difference restrictions. It is also in one-to-one correspondence with the set of acyclic orientations of a certain partially oriented graph. Using these facts, we describe a linear (in the area of $R$) algorithm for determining whether $R$ can be tiled with ribbon tiles of order $n$ and producing such a tiling when one exists. We also resolve a conjecture of Pak by showing that any pair of order-$n$ ribbon tilings of $R$ can be connected by a sequence of local replacement moves. Some of our results are generalizations of known results for order-2 ribbon tilings (a.k.a. domino tilings). We also discuss applications of multidimensional height functions to a broader class of polyomino tiling problems. | |
| dc.description | 25 pages, 7 figures. This version has been slightly revised (new references, a new illustration, and a few cosmetic changes). To appear in Transactions of the American Mathematical Society | |
| dc.identifier | https://arxiv.org/abs/math/0107095 | |
| dc.identifier | http://arxiv.org/abs/math/0107095 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/61843 | |
| dc.subject | Combinatorics | |
| dc.subject | Mathematical Physics | |
| dc.subject | 05-XX | |
| dc.title | Ribbon Tilings and Multidimensional Height Functions | |
| dc.type | text |