## 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

- Alexei Borodin,
*Longest increasing subsequences of random colored permutations*, Electron. J. Combin.**6**(1999), Research Paper 13, 12. MR**1667453** - Henry Cohn, Noam Elkies, and James Propp,
*Local statistics for random domino tilings of the Aztec diamond*, Duke Math. J.**85**(1996), no.ย 1, 117โ166. MR**1412441**, DOI 10.1215/S0012-7094-96-08506-3 - H. Cohn, R. Kenyon, and J. Propp,
*A variational principle for domino tilings*, J. Amer. Math. Soc.**14**(2001), no. 2, 297โ346. arXiv:math.CO/0008220 - J. H. Conway and J. C. Lagarias,
*Tiling with polyominoes and combinatorial group theory*, J. Combin. Theory Ser. A**53**(1990), no.ย 2, 183โ208. MR**1041445**, DOI 10.1016/0097-3165(90)90057-4 - Paul H. Edelman,
*A partial order on the regions of $\textbf {R}^{n}$ dissected by hyperplanes*, Trans. Amer. Math. Soc.**283**(1984), no.ย 2, 617โ631. MR**737888**, DOI 10.1090/S0002-9947-1984-0737888-6 - S. Fomin and D. Stanton,
*Rim hook lattices*, Algebra i Analiz**9**(1997), no.ย 5, 140โ150; English transl., St. Petersburg Math. J.**9**(1998), no.ย 5, 1007โ1016. MR**1604377** - William Geller and James Propp,
*The projective fundamental group of a $\mathbf Z^2$-shift*, Ergodic Theory Dynam. Systems**15**(1995), no.ย 6, 1091โ1118. MR**1366310**, DOI 10.1017/S0143385700009810 - Gordon James and Adalbert Kerber,
*The representation theory of the symmetric group*, Encyclopedia of Mathematics and its Applications, vol. 16, Addison-Wesley Publishing Co., Reading, Mass., 1981. With a foreword by P. M. Cohn; With an introduction by Gilbert de B. Robinson. MR**644144** - C. Kenyon and R. Kenyon,
*Tiling a polygon with rectangles*, Proc. 33rd Symposium on Foundations of Computer Science (1992), 610โ619. - Richard Kenyon,
*A note on tiling with integer-sided rectangles*, J. Combin. Theory Ser. A**74**(1996), no.ย 2, 321โ332. MR**1385374**, DOI 10.1006/jcta.1996.0053 - Richard Kenyon,
*Conformal invariance of domino tiling*, Ann. Probab.**28**(2000), no.ย 2, 759โ795. MR**1782431**, DOI 10.1214/aop/1019160260 - Michael Luby, Dana Randall, and Alistair Sinclair,
*Markov chain algorithms for planar lattice structures*, 36th Annual Symposium on Foundations of Computer Science (1995), 150โ159. - C. Moore and I. Pak,
*Ribbon tile invariants from signed area*, Preprint (2000). - Roman Muchnik and Igor Pak,
*On tilings by ribbon tetrominoes*, J. Combin. Theory Ser. A**88**(1999), no.ย 1, 188โ193. MR**1713456**, DOI 10.1006/jcta.1999.2980 - Igor Pak,
*Ribbon tile invariants*, Trans. Amer. Math. Soc.**352**(2000), no.ย 12, 5525โ5561. MR**1781275**, DOI 10.1090/S0002-9947-00-02666-0 - โ,
*Tile Invariants: New Horizons*, To appear in Theoretical Computer Science, special issue on tilings. - James Propp,
*A pedestrian approach to a method of Conway, or, A tale of two cities*, Math. Mag.**70**(1997), no.ย 5, 327โ340. MR**1488869**, DOI 10.2307/2691169 - James Gary Propp and David Bruce Wilson,
*Exact sampling with coupled Markov chains and applications to statistical mechanics*, Proceedings of the Seventh International Conference on Random Structures and Algorithms (Atlanta, GA, 1995), 1996, pp.ย 223โ252. MR**1611693**, DOI 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.3.CO;2-R - E. Remila,
*On the structure of some spaces of tilings*, Preprint (2000). - G. de B. Robinson,
*Representation theory of the symmetric group*, Mathematical Expositions, No. 12, University of Toronto Press, Toronto, 1961. MR**0125885** - Klaus Schmidt,
*Tilings, fundamental cocycles and fundamental groups of symbolic $\textbf {Z}^d$-actions*, Ergodic Theory Dynam. Systems**18**(1998), no.ย 6, 1473โ1525. MR**1658619**, DOI 10.1017/S0143385798118060 - Scott Sheffield,
*Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles*, Preprint (2000). arXiv:math.CO/0008231 - Carla D. Savage and Cun-Quan Zhang,
*The connectivity of acyclic orientation graphs*, Discrete Math.**184**(1998), no.ย 1-3, 281โ287. MR**1609342**, DOI 10.1016/S0012-365X(97)00201-X - Richard P. Stanley,
*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171โ178. MR**317988**, DOI 10.1016/0012-365X(73)90108-8 - Dennis W. Stanton and Dennis E. White,
*A Schensted algorithm for rim hook tableaux*, J. Combin. Theory Ser. A**40**(1985), no.ย 2, 211โ247. MR**814412**, DOI 10.1016/0097-3165(85)90088-3 - D. Randall and P. Tetali,
*Analyzing Glauber dynamics by comparison of Markov Chains*, Journal of Mathematical Physics**41**(2000), no. 3, 1598โ1615. - William P. Thurston,
*Conwayโs tiling groups*, Amer. Math. Monthly**97**(1990), no.ย 8, 757โ773. MR**1072815**, DOI 10.2307/2324578

## 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