Ribbon tile invariants

Pak, Igor

doi:10.1090/S0002-9947-00-02666-0

Ribbon tile invariants
HTML articles powered by AMS MathViewer

by Igor Pak PDF

Trans. Amer. Math. Soc. 352 (2000), 5525-5561 Request permission

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

Anders Björner and Michelle L. Wachs, Generalized quotients in Coxeter groups, Trans. Amer. Math. Soc. 308 (1988), no. 1, 1–37. MR 946427, DOI 10.1090/S0002-9947-1988-0946427-X
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
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, DOI 10.1215/S0012-7094-96-08506-3
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, DOI 10.1016/0097-3165(90)90057-4
Hidegorô Nakano, Über Abelsche Ringe von Projektionsoperatoren, Proc. Phys.-Math. Soc. Japan (3) 21 (1939), 357–375 (German). MR 94
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
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
Solomon W. Golomb, Polyominoes, 2nd ed., Princeton University Press, Princeton, NJ, 1994. Puzzles, patterns, problems, and packings; With diagrams by Warren Lushbaugh; With an appendix by Andy Liu. MR 1291821
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
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.
Richard Kenyon, A note on tiling with integer-sided rectangles, J. Combin. Theory Ser. A 74 (1996), no. 2, 321–332. MR 1385374, DOI 10.1006/jcta.1996.0053
I. G. Macdonald, Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979. MR 553598
R. Muchnik, I. Pak, On tilings by ribbon tetrominoes, J. Combin. Theory, Ser. A 88 (1999), 199–193.
I. Pak, A generalization of the rim hook bijection for skew shapes, preprint, 1997.
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, DOI 10.2307/2691169
G. de B. Robinson, Representation theory of the symmetric group, Mathematical Expositions, No. 12, University of Toronto Press, Toronto, 1961. MR 0125885
R. P. Stanley, Enumerative Combinatorics. Vol. 2, Cambridge Univ. Press, 1999.
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, DOI 10.1016/0097-3165(85)90088-3
H. N. V. Temperley and Michael E. Fisher, Dimer problem in statistical mechanics—an exact result, Philos. Mag. (8) 6 (1961), 1061–1063. MR 136398
W. Thurston, Conway’s tiling group, Amer. Math. Monthly 97 (1990), 757–773. MR91k:52028