Mathematics – Combinatorics
Scientific paper
2001-07-12
Mathematics
Combinatorics
25 pages, 7 figures. This version has been slightly revised (new references, a new illustration, and a few cosmetic changes).
Scientific paper
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.
No associations
LandOfFree
Ribbon Tilings and Multidimensional Height Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Ribbon Tilings and Multidimensional Height Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ribbon Tilings and Multidimensional Height Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-141334