Tableau combinatorics

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

Last update: 3 March 2013

Tableau combinatorics

Skew shapes and standard tableaux. A partition λ is a collection of n boxes in a corner. We shall conform to the conventions in [Mac1995] and assume that gravity goes up and to the left.

Any partition λ can be identified with the sequence λ=(λ1λ2) where λi is the number of boxes in row i of λ. The rows and columns are numbered in the same way as for matrices. In the example above we have λ=(553311). If λ and μ are partitions such that μiλi for all i we write μλ. The skew shape λ/μ consists of all boxes of λ which are not in μ. Any skew shape is a union of connected components. Number the boxes of each skew shape λ/μ along major diagonals from southwest to northeast and

writeboxi to indicate the box numberedi.

Let λ/μ be a skew shape with n boxes. A standard tableau of shape λ/μ is a filling of the boxes in the skew shape λ/μ with the numbers 1,,n such that the numbers increase from left to right in each row and from top to bottom down each column. Let

λ/μ= {standard tableaux of shapeλ/μ}.

The column reading tableau C of shape λ/μ is the standard tableau obtained by entering the numbers 1,2,,n consecutively down the columns of λ/μ, beginning with the southwest most connected component and filling the columns from left to right. The row reading tableau R of shape λ/μ is the standard tableau obtained by entering the numbers 1,2,,n left to right across the rows of λ/μ, beginning with the northeast most connected component and filling the rows from top to bottom. In general, if L is a standard tableau and wSn then wL will denote the filling of λ/μ obtained by permuting the entries of L according to the permutation w.

Proposition 2.1. [BWa1988, Theorem 7.1] Given a standard tableau L of shape λ/μ define the word of L to be permutation

wL= ( 1n L(box1) L(boxn) )

where L(boxi) is the entry in boxi of L. Let C and R be the column reading and row reading tableaux of shape λ/μ, respectively. The map

λ/μ Sn L wL

defines a bijection from λ/μ to the interval [wC,wR] in Sn (in the Bruhat-Chevalley order).

Placed skew shapes. Let +i[0,2π/ln(q2)) = { a+bia, 0b2π/ln(q2) } . If q is a positive real number then the function

+i[0,2π/ln(q2)) * x q2x=eln(q2)x

is a bijection. The elements of [0,1)+i[0,2π/ln(q2)) index the -cosets in +i[0,2π/ln(q2)).

A placed skew shape is a pair (c,λ/μ) consisting of a skew shape λ/μ and a content function

c: {boxes ofλ/μ} +i[0,2π/ln(q2)) such that

c(boxj) c(boxi), ifijand c(boxj)-c (boxi), c(boxj)=c (boxi)+1, if and only ifboxiand boxjare on adjacent diagonals, and c(boxi)= c(boxj), if and only ifboxiand boxjare on the same diagonal.

This is a generalization of the usual notion of the content of a box in a partition (see [Mac1995] I §1 Ex. 3).

Suppose that (c,λ/μ) is a placed skew shape such that c takes values in . One can visualize (c,λ/μ) by placing λ/μ on a piece of infinite graph paper where the diagonals of the graph paper are indexed consecutively (with elements of ) from southeast to northwest. The content of a box b is the index c(b) of the diagonal that b is on. In the general case, when c takes values in +i[0,2π/ln(q2)), one imagines a book with r pages of infinite graph paper where the diagonals of the graph paper are indexed consecutively (with elements of ) from southeast to northwest. The pages are numbered by values β1,,βr from the set [0,1)+i[0,2π/ln(q2)) and there is a skew shape λ(k)/μ(k) placed on page βk. The skew shape λ/μ is a union of the disjoint skew shapes λ(i)/μ(i),

λ/μ=λ(1)/ μ(1) λ(r)/μ(r),

and the content function is given by

c(b)= (page number of the page containingb)+ (index of the diagonal containingb).

Example. The following diagrams illustrate standard tableaux and the numbering of boxes in a skew shape λ/μ.

10 12 13 14 6 8 11 5 7 9 4 2 3 1 3 4 9 12 1 5 10 7 13 14 2 6 8 11 λ/μwith boxes numbered A standard tableauLof shape λ/μ

The word of the standard tableau L is the permutation wL= ( 11,6,8,2,7,1, 13,5,14,3,10,4, 9,12 ) (in one-line notation).

The following picture shows the contents of the boxes in the placed skew shape (c,λ/μ) such that the sequence ( c(box1),, c(boxn) ) is ( -7,-6,-5,-2,0 ,1,1,2,2,3,3, 4,5,6 ) .

3 4 5 6 1 2 3 0 1 2 -2 -6 -5 -7 Contents of the boxes of (c,λ/μ)

The following picture shows the contents of the boxes in the placed skew shape (c,λ/μ) such that the sequence ( c(box1),, c(boxn) ) is ( -7,-6,-5,-3/2, 1/2,3/2,5/2,5/ 2,7/2,7/2,9/2, 11/2,13/2 ) .

72 92 112 132 -6 -5 32 52 72 -7 12 32 52 -32 0 12

This “book” has two pages, with page numbers 0 and 12.

Lemma 2.2. Let (c,λ/μ) be a placed skew shape with n boxes and let L be a standard tableau of shape λ/μ. Let L(i) denote the box containing i in L. The content sequence

( c(L(1)),, c(L(n)) )

uniquely determines the shape (c,λ/μ) and the standard tableau L.

Proof.

Proceed by induction on the number of boxes of L. If L has only one box then the content sequence (c(L(1))) determines the placement of that box. Assume that L has n boxes. Let L be the standard tableau determined by removing the box containing n from L. Then L is also of skew shape and the content sequence of L is ( c(L(1)),, c(L(n-1)) ) . By the induction hypothesis we can reconstruct L from its content sequence. Then c(L(n)) determines the diagonal which must contain box n in L. So L and c(L(n)) determine L uniquely.

Notes and References

This is an excerpt of the preprint entitled Skew shape representations are irreducible authored by Arun Ram in 1998.

Research supported in part by National Science Foundation grant DMS-9622985, and a Postdoctoral Fellowship at Mathematical Sciences Research Institute.

page history