Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

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



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 $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 [Enhancements On Off] (What's this?)

  • 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 ${R}\sp{n}$ 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 $\mathbb Z^2$-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 $Z\sp d$-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

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

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

American Mathematical Society