Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Ribbon tilings and multidimensional height functions
HTML articles powered by AMS MathViewer

by Scott Sheffield PDF
Trans. Amer. Math. Soc. 354 (2002), 4789-4813 Request permission

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
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
  • Email: scott@math.stanford.edu
  • 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
  • © Copyright 2002 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 354 (2002), 4789-4813
  • MSC (2000): Primary 68R05, 06A07
  • DOI: https://doi.org/10.1090/S0002-9947-02-02981-1
  • MathSciNet review: 1926837