Ribbon tilings and multidimensional height functions

Author:
Scott Sheffield

Journal:
Trans. Amer. Math. Soc. **354** (2002), 4789-4813

MSC (2000):
Primary 68R05, 06A07

Published electronically:
August 1, 2002

MathSciNet review:
1926837

Full-text PDF Free Access

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 increasing subsequences of random colored permutations*, Electron. J. Combin.**6**(1999), Research Paper 13, 12 pp. (electronic). MR**1667453****2.**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**, 10.1215/S0012-7094-96-08506-3**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**1041445**, 10.1016/0097-3165(90)90057-4**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**737888**, 10.1090/S0002-9947-1984-0737888-6**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****7.**William Geller and James Propp,*The projective fundamental group of a 𝐙²-shift*, Ergodic Theory Dynam. Systems**15**(1995), no. 6, 1091–1118. MR**1366310**, 10.1017/S0143385700009810**8.**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****9.**C. Kenyon and R. Kenyon,*Tiling a polygon with rectangles*, Proc. 33rd Symposium on Foundations of Computer Science (1992), 610-619.**10.**Richard Kenyon,*A note on tiling with integer-sided rectangles*, J. Combin. Theory Ser. A**74**(1996), no. 2, 321–332. MR**1385374**, 10.1006/jcta.1996.0053**11.**Richard Kenyon,*Conformal invariance of domino tiling*, Ann. Probab.**28**(2000), no. 2, 759–795. MR**1782431**, 10.1214/aop/1019160260**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.**Roman Muchnik and Igor Pak,*On tilings by ribbon tetrominoes*, J. Combin. Theory Ser. A**88**(1999), no. 1, 188–193. MR**1713456**, 10.1006/jcta.1999.2980**15.**Igor Pak,*Ribbon tile invariants*, Trans. Amer. Math. Soc.**352**(2000), no. 12, 5525–5561 (electronic). MR**1781275**, 10.1090/S0002-9947-00-02666-0**16.**-,*Tile Invariants: New Horizons*, To appear in Theoretical Computer Science, special issue on tilings.**17.**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**, 10.2307/2691169**18.**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**, 10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.3.CO;2-R**19.**E. Remila,*On the structure of some spaces of tilings*, Preprint (2000).**20.**G. de B. Robinson,*Representation theory of the symmetric group*, Mathematical Expositions, No. 12. University of Toronto Press, Toronto, 1961. MR**0125885****21.**Klaus Schmidt,*Tilings, fundamental cocycles and fundamental groups of symbolic 𝑍^{𝑑}-actions*, Ergodic Theory Dynam. Systems**18**(1998), no. 6, 1473–1525. MR**1658619**, 10.1017/S0143385798118060**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**1609342**, 10.1016/S0012-365X(97)00201-X**24.**Richard P. Stanley,*Acyclic orientations of graphs*, Discrete Math.**5**(1973), 171–178. MR**0317988****25.**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**, 10.1016/0097-3165(85)90088-3**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.**William P. Thurston,*Conway’s tiling groups*, Amer. Math. Monthly**97**(1990), no. 8, 757–773. MR**1072815**, 10.2307/2324578

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:
http://dx.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