| Ribbon tilings and multidimensional height function, preprint arXiv:math.CO/0107095 (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We fix n and say a square in the two-dimensional grid indexed by (x, y)hascolorc if x + y ≡ c (mod 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 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. 1. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||