Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Ribbon tilings and multidimensional height functions

Author: Scott Sheffield
Journal: Trans. Amer. Math. Soc. 354 (2002), 4789-4813
MSC (2000): Primary 68R05, 06A07
Published electronically: August 1, 2002
MathSciNet review: 1926837
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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 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 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.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 68R05, 06A07

Retrieve articles in all journals with MSC (2000): 68R05, 06A07

Additional Information

Scott Sheffield
Affiliation: Department of Mathematics, Stanford University, Building 380 MC 2125, Stanford, California 94305
Address at time of publication: Microsoft Research, One Microsoft Way, Redmond, Washington 98052-6399

Received by editor(s): August 10, 2001
Published electronically: August 1, 2002
Additional Notes: This research was supported by a summer internship at Microsoft Research
Article copyright: © Copyright 2002 American Mathematical Society