Ribbon tilings and multidimensional height functions

Author:
Scott Sheffield

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

Published electronically:
August 1, 2002

MathSciNet review:
1926837

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We fix and say a square in the two-dimensional grid indexed by has color if . A *ribbon tile* of order is a connected polyomino containing exactly one square of each color. We show that the set of order- ribbon tilings of a simply connected region is in one-to-one correspondence with a set of *height functions* from the vertices of to 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 ) algorithm for determining whether can be tiled with ribbon tiles of order and producing such a tiling when one exists. We also resolve a conjecture of Pak by showing that any pair of order- ribbon tilings of can be connected by a sequence of local replacement moves. Some of our results are generalizations of known results for order- ribbon tilings (a.k.a. domino tilings). We also discuss applications of multidimensional height functions to a broader class of polyomino tiling problems.

**1.**Alexei Borodin,*Longest Increases Subsequences of Random Colored Permutations*, Electronic Journal of Combinatorics**6(1)**(1999), Research Paper 13. MR**2000a:05014****2.**H. Cohn, N. Elkies, and J. Propp,*Local statistics for random domino tilings of the Aztec diamond*, Duke Math. J.**85**(1996), 117-166. arXiv:math.CO/0008243 MR**97k:52026****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 CMP**2001:08****4.**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**91a:05030****5.**Paul H. Edelman,*A partial order on the regions of dissected by hyperplanes*, Trans. Amer. Math. Soc.**283**(1984), no. 2, 617-631. MR**85k:51030****6.**S. Fomin and D. Stanton,*Rim hook lattices*, St. Petersburg Math. J.**9**(1998), 1007-1016. MR**99c:05202****7.**W. Geller and J. Propp,*The projective fundamental group of a -shift*, Ergodic Theory and Dynamic Systems**15**(1995), 1091-1118. MR**96m:54076****8.**G. James and A. Kerber,*The Representation Theory of the Symmetric Group*, Addison-Wesley, Reading, MA, 1981. MR**83k:20003****9.**C. Kenyon and R. Kenyon,*Tiling a polygon with rectangles*, Proc. 33rd Symposium on Foundations of Computer Science (1992), 610-619.**10.**R. Kenyon,*A note on tiling with integer-sided rectangles*, J. Combin. Theory (Ser. A)**74**(1996), no. 2, 321-332. MR**97c:52045****11.**-,*Conformal invariance of domino tiling*, Ann. Probab.**28**(2000), no. 2, 759-795. MR**2002e:52022****12.**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.**13.**C. Moore and I. Pak,*Ribbon tile invariants from signed area*, Preprint (2000).**14.**R. Muchnik and I. Pak,*On tilings by ribbon tetrominoes*, J. Combin. Theory (Ser. A)**88**(1999), no. 1, 188-193. MR**2000g:05050****15.**I. Pak,*Ribbon tile invariants*, Trans. Amer. Math. Soc.**352**(2000), no. 12, 5525-5561. MR**2001g:05039****16.**-,*Tile Invariants: New Horizons*, To appear in Theoretical Computer Science, special issue on tilings.**17.**J. Propp,*A pedestrian approach to a method of Conway, or, A tale of two cities*, Math Mag.**70**(1997), 327-340. MR**98m:52031****18.**J. Propp and D. B. Wilson,*Exact sampling with coupled Markov chains and applications to statistical mechanics*, Random Structures and Algorithms**9**(1996), 223-252. MR**99k:60176****19.**E. Remila,*On the structure of some spaces of tilings*, Preprint (2000).**20.**G. de B. Robinson,*Representation Theory of the Symmetric Group*, Edinburgh University Press, 1961. MR**23:A3182****21.**K. Schmidt,*Tilings, fundamental cocycles and fundamental groups of symbolic -actions*, Ergodic Theory and Dynamical Systems**18**(1998), 1473-1525. MR**99j:58068****22.**Scott Sheffield,*Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles*, Preprint (2000). arXiv:math.CO/0008231**23.**Carla D. Savage and Cun-Quan Zhang,*The connectivity of acyclic orientation graphs*, Discrete Math.**184**(1998), no. 1-3, 281-287. MR**98m:05117****24.**Richard P. Stanley,*Acyclic orientations of graphs.*, Discrete Math.**5**(1973), 171-178. MR**47:6537****25.**D. Stanton and D. White,*A Schensted algorithm for rim hook tableaux.*, J. Combin. Theory, Ser. A**40**(1985), 211-247. MR**87c:05014****26.**D. Randall and P. Tetali,*Analyzing Glauber dynamics by comparison of Markov Chains*, Journal of Mathematical Physics**41**(2000), no. 3, 1598-1615. CMP**2000:13****27.**W. P. Thurston,*Conway's tiling groups*, Amer. Math. Monthly, vol.**97**(1990), no. 8, 757-773. MR**91k:52028**

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

DOI:
https://doi.org/10.1090/S0002-9947-02-02981-1

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