Ribbon tile invariants
Author:
Igor Pak
Journal:
Trans. Amer. Math. Soc. 352 (2000), 55255561
MSC (2000):
Primary 05E10, 52C20; Secondary 05B45, 20C30
Published electronically:
August 8, 2000
MathSciNet review:
1781275
Fulltext 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 ConwayLagarias 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 (89c:05012), http://dx.doi.org/10.1090/S0002994719880946427X
 [BK]
A.
N. Kirillov and A.
D. Berenstein, Groups generated by involutions,
Gel′fandTsetlin 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
(96e:05178)
 [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
(97k:52026), http://dx.doi.org/10.1215/S0012709496085063
 [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
(91a:05030), http://dx.doi.org/10.1016/00973165(90)900574
 [EKLP]
Noam
Elkies, Greg
Kuperberg, Michael
Larsen, and James
Propp, Alternatingsign matrices and domino tilings. I, J.
Algebraic Combin. 1 (1992), no. 2, 111–132. MR 1226347
(94f:52035), http://dx.doi.org/10.1023/A:1022420103267
Noam
Elkies, Greg
Kuperberg, Michael
Larsen, and James
Propp, Alternatingsign matrices and domino tilings. II, J.
Algebraic Combin. 1 (1992), no. 3, 219–234. MR 1194076
(94f:52036), http://dx.doi.org/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 (99c:05202)
 [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 NPcompleteness;
A Series of Books in the Mathematical Sciences. MR 519066
(80g:68056)
 [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,
AddisonWesley Publishing Co., Reading, Mass., 1981. With a foreword by P.
M. Cohn; With an introduction by Gilbert de B. Robinson. MR 644144
(83k:20003)
 [Ka]
P. W. Kastelyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 12091225.
 [Ke]
Richard
Kenyon, A note on tiling with integersided rectangles, J.
Combin. Theory Ser. A 74 (1996), no. 2,
321–332. MR 1385374
(97c:52045), http://dx.doi.org/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
(84g:05003)
 [MP]
R. Muchnik, I. Pak, On tilings by ribbon tetrominoes, J. Combin. Theory, Ser. A 88 (1999), 199193. 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
(98m:52031), http://dx.doi.org/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 (23 #A3182)
 [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 (87c:05014), http://dx.doi.org/10.1016/00973165(85)900883
 [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 (24 #B2436)
 [T]
W. Thurston, Conway's tiling group, Amer. Math. Monthly 97 (1990), 757773. MR91k:52028
 [BW]
 A. Bjorner, M. Wachs, Generalized quotients in Coxeter groups., Trans. Amer Math. Soc. 308 (1988), 137. MR 89c:05012
 [BK]
 A. Berenstein, A. Kirillov, Groups generated by involutions, GelfandTsetlin patterns, and combinatorics of Young tableaux, St. Petersburg Math. J. 7 (1996), 77127. MR 96e:05178
 [CEP]
 H. Cohn, N. Elkies, J. Propp, Local statistics for random domino tilings of the Aztec diamond, Duke Math. J. 85 (1996), 117166. MR 97k:52026
 [CL]
 J. H. Conway, J. C. Lagarias, Tilings with polyominoes and combinatorial group theory, J. Comb. Theory, Ser. A 53 (1990), 183208. MR 91a:05030
 [EKLP]
 N. Elkies, G. Kuperberg, M. Larsen and J. Propp, Alternating sign matrices and domino tilings. I, II, J. Alg. Comb. 1 (1992), 111132, 219234. MR 94f:52035, MR 94f:52036
 [FS]
 S. Fomin, D. Stanton, Rim hook lattices, St. Petersburg Math. J. 9 (1998), 10071016. MR 99c:05202
 [GJ]
 M. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NPcompleteness, Freeman, San Francisco, CA, 1979. MR 80g:68056
 [G]
 S. Golomb, Polyominoes, Scribners, New York, 1965. MR 95k:00006 (later ed.)
 [JK]
 G. James, A. Kerber, The Representation Theory of the Symmetric Group, AddisonWesley, Reading, MA, 1981. MR 83k:20003
 [Ka]
 P. W. Kastelyn, The statistics of dimers on a lattice. I. The number of dimer arrangements on a quadratic lattice, Physica 27 (1961), 12091225.
 [Ke]
 R. Kenyon, A note on tiling with integersided rectangles, J. Combin. Theory, Ser. A 74 (1996), 321332. MR 97c:52045
 [M]
 I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, London, 1979.MR 84g:05003
 [MP]
 R. Muchnik, I. Pak, On tilings by ribbon tetrominoes, J. Combin. Theory, Ser. A 88 (1999), 199193. CMP 2000:01
 [Pa]
 I. Pak, A generalization of the rim hook bijection for skew shapes, preprint, 1997.
 [Pr]
 J. Propp, A pedestrian approach to a method of Conway, or, A tale of two cities, Math. Mag. 70 (1997), 327340. MR 98m:52031
 [R]
 G. de B. Robinson, Representation Theory of the Symmetric Group, Edinburgh University Press and Univ. of Toronto Press, 1961. MR 23:A3182
 [S]
 R. P. Stanley, Enumerative Combinatorics. Vol. 2, Cambridge Univ. Press, 1999. CMP 99:09
 [SW]
 D. Stanton, D. White, A Schensted algorithm for rim hook tableaux, J. Comb. Theory, Ser. A 40 (1985), 211247. MR 87c:05014
 [TF]
 H. N. V. Temperley, M. E. Fisher, Dimer problem in statistical mechanics  An exact result, Philos. Mag. 6 (1961), 10611063. MR 24:B2436
 [T]
 W. Thurston, Conway's tiling group, Amer. Math. Monthly 97 (1990), 757773. MR91k:52028
Similar Articles
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 065208283
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/S0002994700026660
PII:
S 00029947(00)026660
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
