Ribbon tilings and multidimensional height functions
Author:
Scott Sheffield
Journal:
Trans. Amer. Math. Soc. 354 (2002), 47894813
MSC (2000):
Primary 68R05, 06A07
Published electronically:
August 1, 2002
MathSciNet review:
1926837
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We fix and say a square in the twodimensional 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 onetoone correspondence with a set of height functions from the vertices of to satisfying certain difference restrictions. It is also in onetoone 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), 117166. 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, 297346. 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, 183208. 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, 617631. MR 85k:51030
 6.
S. Fomin and D. Stanton, Rim hook lattices, St. Petersburg Math. J. 9 (1998), 10071016. MR 99c:05202
 7.
W. Geller and J. Propp, The projective fundamental group of a shift, Ergodic Theory and Dynamic Systems 15 (1995), 10911118. MR 96m:54076
 8.
G. James and A. Kerber, The Representation Theory of the Symmetric Group, AddisonWesley, 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), 610619.
 10.
R. Kenyon, A note on tiling with integersided rectangles, J. Combin. Theory (Ser. A) 74 (1996), no. 2, 321332. MR 97c:52045
 11.
, Conformal invariance of domino tiling, Ann. Probab. 28 (2000), no. 2, 759795. 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), 150159.
 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, 188193. MR 2000g:05050
 15.
I. Pak, Ribbon tile invariants, Trans. Amer. Math. Soc. 352 (2000), no. 12, 55255561. 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), 327340. 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), 223252. 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), 14731525. 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 CunQuan Zhang, The connectivity of acyclic orientation graphs, Discrete Math. 184 (1998), no. 13, 281287. MR 98m:05117
 24.
Richard P. Stanley, Acyclic orientations of graphs., Discrete Math. 5 (1973), 171178. MR 47:6537
 25.
D. Stanton and D. White, A Schensted algorithm for rim hook tableaux., J. Combin. Theory, Ser. A 40 (1985), 211247. 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, 15981615. CMP 2000:13
 27.
W. P. Thurston, Conway's tiling groups, Amer. Math. Monthly, vol. 97 (1990), no. 8, 757773. MR 91k:52028
 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), 117166. 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, 297346. 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, 183208. 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, 617631. MR 85k:51030
 6.
 S. Fomin and D. Stanton, Rim hook lattices, St. Petersburg Math. J. 9 (1998), 10071016. MR 99c:05202
 7.
 W. Geller and J. Propp, The projective fundamental group of a shift, Ergodic Theory and Dynamic Systems 15 (1995), 10911118. MR 96m:54076
 8.
 G. James and A. Kerber, The Representation Theory of the Symmetric Group, AddisonWesley, 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), 610619.
 10.
 R. Kenyon, A note on tiling with integersided rectangles, J. Combin. Theory (Ser. A) 74 (1996), no. 2, 321332. MR 97c:52045
 11.
 , Conformal invariance of domino tiling, Ann. Probab. 28 (2000), no. 2, 759795. 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), 150159.
 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, 188193. MR 2000g:05050
 15.
 I. Pak, Ribbon tile invariants, Trans. Amer. Math. Soc. 352 (2000), no. 12, 55255561. 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), 327340. 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), 223252. 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), 14731525. 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 CunQuan Zhang, The connectivity of acyclic orientation graphs, Discrete Math. 184 (1998), no. 13, 281287. MR 98m:05117
 24.
 Richard P. Stanley, Acyclic orientations of graphs., Discrete Math. 5 (1973), 171178. MR 47:6537
 25.
 D. Stanton and D. White, A Schensted algorithm for rim hook tableaux., J. Combin. Theory, Ser. A 40 (1985), 211247. 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, 15981615. CMP 2000:13
 27.
 W. P. Thurston, Conway's tiling groups, Amer. Math. Monthly, vol. 97 (1990), no. 8, 757773. MR 91k:52028
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 980526399
Email:
scott@math.stanford.edu
DOI:
http://dx.doi.org/10.1090/S0002994702029811
PII:
S 00029947(02)029811
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
