Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
|
   
Available in electronic format
Available in print format 		Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)

     

Ribbon tile invariants

Author(s): Igor Pak
Journal: Trans. Amer. Math. Soc. 352 (2000), 5525-5561.
MSC (2000): Primary 05E10, 52C20; Secondary 05B45, 20C30
Posted: August 8, 2000
MathSciNet review: 1781275
Retrieve article in: PDF
This article is available free of charge

Abstract | References | Similar articles | Additional information

Abstract: Let $\mathbf{T}$ be a finite set of tiles, and $\mathcal{B}$ a set of regions $\Gamma $ tileable by $\mathbf{T}$. We introduce a tile counting group $\mathbb{G} (\mathbf{T}, \mathcal{B})$ as a group of all linear relations for the number of times each tile $\tau \in \mathbf{T}$ can occur in a tiling of a region $\Gamma \in \mathcal{B}$. 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.

References:

[BW]
A. Bjorner, M. Wachs, Generalized quotients in Coxeter groups., Trans. Amer Math. Soc. 308 (1988), 1-37. MR 89c:05012

[BK]
A. Berenstein, A. Kirillov, Groups generated by involutions, Gelfand-Tsetlin patterns, and combinatorics of Young tableaux, St. Petersburg Math. J. 7 (1996), 77-127. 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), 117-166. MR 97k:52026

[CL]
J. H. Conway, J. C. Lagarias, Tilings with polyominoes and combinatorial group theory, J. Comb. Theory, Ser. A 53 (1990), 183-208. 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), 111-132, 219-234. MR 94f:52035, MR 94f:52036

[FS]
S. Fomin, D. Stanton, Rim hook lattices, St. Petersburg Math. J. 9 (1998), 1007-1016. MR 99c:05202

[GJ]
M. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, 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, Addison-Wesley, 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), 1209-1225.

[Ke]
R. Kenyon, A note on tiling with integer-sided rectangles, J. Combin. Theory, Ser. A 74 (1996), 321-332. 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), 199-193. 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), 327-340. 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), 211-247. MR 87c:05014

[TF]
H. N. V. Temperley, M. E. Fisher, Dimer problem in statistical mechanics - An exact result, Philos. Mag. 6 (1961), 1061-1063. MR 24:B2436

[T]
W. Thurston, Conway's tiling group, Amer. Math. Monthly 97 (1990), 757-773. 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 06520-8283
Address at time of publication: Department of Mathematics, MIT, Cambridge, Massachusetts 02139
Email: paki@math.yale.edu, paki@math.mit.edu

DOI: 10.1090/S0002-9947-00-02666-0
PII: S 0002-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
Posted: August 8, 2000
Copyright of article: Copyright 2000, American Mathematical Society




AMS and Social Media LinkedIn Facebook Podcasts Twitter YouTube RSS Feeds Blogs Wikipedia