Ribbon tile invariants

Author:
Igor Pak

Journal:
Trans. Amer. Math. Soc. **352** (2000), 5525-5561

MSC (2000):
Primary 05E10, 52C20; Secondary 05B45, 20C30

Published electronically:
August 8, 2000

MathSciNet review:
1781275

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let be a finite set of tiles, and a set of regions tileable by . We introduce a *tile counting group* as a group of all linear relations for the number of times each tile can occur in a tiling of a region . We compute the tile counting group for a large set of *ribbon tiles*, also known as rim hooks, in a context of representation theory of the symmetric group.

The tile counting group is presented by its set of generators, which consists of certain new *tile invariants*. In a special case these invariants generalize the Conway-Lagarias invariant for tromino tilings and a height invariant which is related to computation of characters of the symmetric group.

The heart of the proof is the known bijection between rim hook tableaux and certain standard skew Young tableaux. We also discuss signed tilings by the ribbon tiles and apply our results to the tileability problem.

**[BW]**Anders Björner and Michelle L. Wachs,*Generalized quotients in Coxeter groups*, Trans. Amer. Math. Soc.**308**(1988), no. 1, 1–37. MR**946427**, 10.1090/S0002-9947-1988-0946427-X**[BK]**A. N. Kirillov and A. D. Berenstein,*Groups generated by involutions, Gel′fand-Tsetlin patterns, and combinatorics of Young tableaux*, Algebra i Analiz**7**(1995), no. 1, 92–152; English transl., St. Petersburg Math. J.**7**(1996), no. 1, 77–127. MR**1334154****[CEP]**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**[CL]**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**[EKLP]**Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp,*Alternating-sign matrices and domino tilings. I*, J. Algebraic Combin.**1**(1992), no. 2, 111–132. MR**1226347**, 10.1023/A:1022420103267

Noam Elkies, Greg Kuperberg, Michael Larsen, and James Propp,*Alternating-sign matrices and domino tilings. II*, J. Algebraic Combin.**1**(1992), no. 3, 219–234. MR**1194076**, 10.1023/A:1022483817303**[FS]**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****[GJ]**Michael R. Garey and David S. Johnson,*Computers and intractability*, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. MR**519066****[G]**S. Golomb,*Polyominoes*, Scribners, New York, 1965. MR**95k:00006 (later ed.)****[JK]**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****[Ka]**P. W. Kastelyn,*The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice*, Physica**27**(1961), 1209-1225.**[Ke]**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**[M]**I. G. Macdonald,*Symmetric functions and Hall polynomials*, The Clarendon Press, Oxford University Press, New York, 1979. Oxford Mathematical Monographs. MR**553598****[MP]**R. Muchnik, I. Pak,*On tilings by ribbon tetrominoes*, J. Combin. Theory, Ser. A**88**(1999), 199-193. CMP**2000:01****[Pa]**I. Pak,*A generalization of the rim hook bijection for skew shapes*, preprint, 1997.**[Pr]**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**[R]**G. de B. Robinson,*Representation theory of the symmetric group*, Mathematical Expositions, No. 12. University of Toronto Press, Toronto, 1961. MR**0125885****[S]**R. P. Stanley,*Enumerative Combinatorics*. Vol. 2, Cambridge Univ. Press, 1999. CMP**99:09****[SW]**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**[TF]**H. N. V. Temperley and Michael E. Fisher,*Dimer problem in statistical mechanics—an exact result*, Philos. Mag. (8)**6**(1961), 1061–1063. MR**0136398****[T]**W. Thurston,*Conway's tiling group*, Amer. Math. Monthly**97**(1990), 757-773. MR91k:52028

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
05E10,
52C20,
05B45,
20C30

Retrieve articles in all journals with MSC (2000): 05E10, 52C20, 05B45, 20C30

Additional Information

**Igor Pak**

Affiliation:
Department of Mathematics, Yale University, New Haven, Connecticut 06520-8283

Address at time of publication:
Department of Mathematics, MIT, Cambridge, Massachusetts 02139

Email:
paki@math.yale.edu, paki@math.mit.edu

DOI:
http://dx.doi.org/10.1090/S0002-9947-00-02666-0

Keywords:
Polyomino tilings,
tile invariants,
Conway group,
rim (ribbon) hooks,
Young diagrams,
Young tableaux,
rim hook bijection,
symmetric group

Received by editor(s):
December 12, 1997

Published electronically:
August 8, 2000

Article copyright:
© Copyright 2000
American Mathematical Society