The connection to standard Young tableaux

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia

Last update: 13 November 2012

The connection to standard Young tableaux

In this section we shall show that the combinatorics of local regions is a generalization of the combinatorics of standard Young tableaux. Let us first make some general definitions, which we will show later provide generalizations of standard objects in the Young tableaux theory. This section is a (purely combinatorial) study of the local regions in the form which appears in (4.3), and therefore corresponds to the representation theory of affine Hecke algebras when q is not a root of unity.

5.1. Definition

Let γ𝔥* be dominant and let

Z(γ) = { αR+ γ,α=0 } ,P(γ)= { αR+ γ,α=1 } , (γ,J) = { wWR(w) Z(γ)=,R (w)P(γ)=J } ,

as in (4.3).

  1. A local region is a pair (γ,J) such that (γ,J) is nonempty.
  2. A ribbon is a local region (γ,J) such that γ is regular, i.e., γ,α0 for all αR.
  3. An element γC is calibratable if
    1. for all simple roots αi, 1in, γ,αi0, and
    2. for all pairs of simple roots αi and αj such that { αRij γ,α=0 } , the set { αRij γ,α=1 } contains more than two elements.
    3. A skew local region is a local region (γ,J) such that wγ is calibratable for all w(γ,J). All ribbons are skew.
    4. A column (respectively row) reading tableau is a minimal (respectively maximal) element of (γ,J) in the weak Bruhat order.
    5. If αR the α-axial distance for w(γ,J) is the value dα(w)= wγ,α.

Remarks. (1) Theorem 4.6(b) shows that, up to a shift, the set (γ,J) has a unique maximal and a unique minimal element and is an interval in the weak Bruhat order. This is the fundamental importance of the notions of the row reading and the column reading tableaux. Theorem 6.9 in Section 6 will show how Theorem 4.6(b) is a generalization of a Young tableaux result of Björner and Wachs [Bjo1988, Theorem 7.2].

(2) The definition of skew local regions is forced by the representation theory of the affine Hecke algebra (see Theorem 3.6, the classification of irreducible calibrated representations). In Proposition 6.4 below we shall show that the skew local regions and the ribbons are generalizations of the skew shapes and border strips which are used in the theory of symmetric functions [Mac1995, I, Section 5 and I, Section 3, Exercise 11]

(3) The axial distances control the denominators which appear in the construction of irreducible representations of the affine Hecke algebra in Theorem 3.5. In Section 6.1 we shall see how they are analogues of the axial distances used by A. Young [You1931] in his constructions of the irreducible representations of the symmetric group.

To summarize, a brief dictionary between local regions combinatorics and the Young tableaux combinatorics:

skew local regions skew shapesλ/μ, ribbons border strips, local regions general configurations of boxes, (γ,J) the set of standard tableaux λ/μ.

The remainder of this section and the next section explain in greater detail the conversions indicated in this dictionary.

Let {ε1,,εn} be an orthonormal basis of 𝔥*=n so that each sequence γ=(γ1,,γn)n is identified with the vector γ=iγiεi. The root system of type An-1 is given by the sets

R= { ±(εj-εi) 1i,jn } andR+= { εj-εi 1i<jn } .

The Weyl group is W=Sn, the symmetric group, acting by permutations of the εi.

5.3. Partitions, 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. We shall always use the word diagonal to mean a major diagonal. In the example above λ=(553311) and the diagonals of λ (from southwest to northeast) contain 1, 1, 1, 2, 3, 3, 2, 2, 2, and 1 box, respectively.

If λ and μ are partitions such that μiλi for all i write μλ. The skew shape λ/μ consists of all boxes of λ which are not in μ. Let λ/μ be a skew shape with n boxes. Number the boxes of each skew shape λ/μ along diagonals from southwest to northeast and

write boxito indicate the box numberedi.

See Example 5.8 below. 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 λ/μ be the set of standard tableaux of shape λ/μ. Given a standard tableau p of shape λ/μ define the word of p to be the permutation

wp= ( 1 n p(box1) p(boxn) ) (5.4)

where p(boxi) is the entry in boxi of the standard tableau.

5.5. Placed skew shapes

Let λ/μ be a skew shape with n boxes. Imagine placing λ/μ on a piece of infinite graph paper where the diagonals of the graph paper are indexed consecutively (with elements of ) from southwest to northeast.

-7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6

The content of a box b is

c(b)=diagonal number of boxb.

Identify the sequence

γ= ( c(box1), c(box2),, c(boxn) ) withγ= i=1nc (boxi)εi n. (5.6)

The pair (γ,λ/μ) is a placed skew shape. It follows from the definitions in Section 5.1 that

Z(γ) = { εj-εi j>iand boxjand boxiare in the same diagonal } and P(γ) = { εj-εi j>iand boxjandboxi are in adjacent diagonals } .


J= { εj-εi j>i boxjandboxiare in adjacent diagonals boxjis northwest ofboxi } , (5.7)

where northwest means strictly north and weakly west.

Examples 5.8. 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 tableaupof shapeλ/μ

The word of the standard tableau p is the permutation wp= ( 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 (γ,λ/μ) with γ= ( -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(γ,λ/μ)

In this case J= { ε2-ε1, ε6-ε5, ε8-ε7, ε10-ε8, ε10-ε9, ε11-ε9, ε12-ε11 } .

Theorem 5.9. Let (γ,λ/μ) be a placed skew shape and let J be as defined in (5.7). Let λ/μ be the set of standard tableaux of shape λ/μ and let (γ,J) be the set defined in Section 5.1. Then the map

λ/μ 1-1 (γ,J), p wp,

where wp is as defined in (5.4), is a bijection.


If w=(w(1)w(n)) is a permutation in Sn then

R(w)= { εj-εi j>isuch thatw (j)<w(i) } .

The theorem is a consequence of the following chain of equivalences:

The filling p is a standard tableau if and only if, for all 1i<jn,

  1. p(boxi)<p(boxj) if boxi and boxj are on the same diagonal,
  2. p(boxi)<p(boxj) if boxj is immediately to the right of boxi, and
  3. p(boxi)>p(boxj) if boxj is immediately above boxi.

These conditions hold if and only if

  1. εj-εi R(wp) if εj-εiZ(γ),
  2. εj-εi R(ep) if εj-εiP(γ)\J,
  3. εj-εi R(wp) if εj-εi J,

which hold if and only if

  1. αR(wp) if αZ(γ),
  2. αR(wp) if αP(γ)\J, and
  3. αR(wp) if αJ.

Finally, these are equivalent to the conditions R(wp)Z(γ)= and R(wp)P(γ)=J.

5.10. Places configurations

We have described how one can identify placed skew shapes (γ,λ/μ) with certain pairs (γ,J). One can extend this conversion to associate placed configurations of boxes to more general pairs (γ,J.) The resulting configurations are not always skew shapes.

Let (γ,J) be a pair such that γ=(γ1,,γn) is a dominant integral weight and JP(γ). (The sequence γ is a dominant integral weight if γ1γn and γi for all i.) If J satisfies the condition

ifβJ,αZ(γ) ,andβ-αR+ thenβ-αJ

then (γ,J) will determine a placed configuration of boxes (see Theorem 4.6). As in the placed skew shape case, think of the boxes as being placed on graph paper where the boxes on a given diagonal all have the same content. (The boxes on each diagonal are allowed to slide along the diagonal as long as they do not pass through the corner of a box on an adjacent diagonal.) The sequence γ describes how many boxes are on each diagonal and the set J determines how the boxes on adjacent diagonals are placed relative to each other. We want

γ=i=1nc (boxi)εi


  1. if εj-εiJ then boxj is northwest of boxi, and
  2. if εj-εiP(γ)\J then boxj is southeast of boxi,

where the boxes are numbered along diagonals in the same way as for skew shapes, southeast means weakly south and strictly east, and northwest means strictly north and weakly west.

If we view the pair (γ,J) as a placed configuration of boxes then the standard tableaux are fillings p of the n boxes in the configuration with 1,2,,n such that, for all i<j,

  1. p(boxi)<p(boxj) if boxi and boxj are on the same diagonal,
  2. p(boxi)<p(boxj) if boxi and boxj are on adjacent diagonals and boxj is southeast of boxi, and
  3. p(boxi)<p(boxj) if boxi and boxj are on adjacent diagonals and boxj is northwest of boxi.

As in (5.6) the permutation in (γ,J) which corresponds to the standard tableau p is wp= ( p(box1),, p(boxn) ) . The following example illustrates the conversion.

Example. Suppose γ= ( -1,-1,-1,0,0,0, 1,1,1,2,2,2 ) and

J = { ε4-ε1, ε4-ε2, ε4-ε3, ε5-ε2, ε5-ε3, ε7-ε5, ε7-ε6, ε8-ε6, ε10-ε9, ε10-ε8, ε10-ε7, ε11-ε9, ε11-ε8, ε11-ε7, ε12-ε9 } .

The placed configuration of boxes corresponding to (γ,J) is as given below.

2 2 0 1 -1 0 -1 1 2 -1 0 1 10 11 4 7 1 5 2 8 12 3 6 9 3 4 1 5 2 6 9 7 8 10 11 12 contents of boxes numbering of boxes a standard tableau

5.11. Books of placed configurations

The general case, when γ=(γ1,,γn) is an arbitrary element of n and JP(γ), is handled as follows. First group the entries of γ according to their -coset in . Each group of entries in γ can be arranged to form a sequence

β+Cβ=β+ (z1,,zk)= ( β+z1,, β+zk ) , where0β<1, zi,and z1zk.

Fix some ordering of these groups and let

γ= ( β1+Cβ1 ,,βr+ Cβr )

be the rearrangement of the sequence γ with the groups listed in order. Since γ and γ are in the same orbit it is sufficient to analyze γ (γ corresponds to the central character of the corresponding affine Hecke algebra representations and thus any convenient element of the orbit is appropriate, see Section 2.3).

The decomposition of γ into groups induces decompositions

Z(γ)= βiZβi, P(γ)= βiPβi, and,if JP(γ), then J= βiJβi,

where Jβi=JPβi. Each pair (Cβ,Jβ) is a placed shape of the type considered in the previous subsection and we may identify (γ,J) with the book of placed shapes ( (Cβ1,Jβ1) ,, (Cβr,Jβr) ) . We think of this as a book with pages numbered by the values β1,,βr and with the placed configuration determined by (Cβi,Jβi) on page βi. In this form the standard tableaux of shape γ,J are fillings of the n boxes in the book with the numbers 1,,n such that the filling on each page satisfies the conditions for a standard tableau in Section 5.10.

Example. If γ= ( 1/2,1/2,1,1,1,3 /2,-2,-2,-1/2,- 1,-1,-1,-1/2,1/ 2,0,0,0 ) then one possibility for γ is

γ= ( -2,-2,-1,-1,-1, 0,0,0,1,1,1,-1/ 2,-1/2,1/2,1/2, 1/2,3/2 ) .

In this case β1=0, β2=1/2,

β1+Cβ1 = ( -2,-2,-1,-1,-1, 0,0,0,1,1,1 ) ,and β2+Cβ2 = ( -1/2,-1/2,1/2, 1/2,1/2,3/2 ) .

If J=Jβ1Jβ2 where Jβ2= { ε14-ε13, ε17-ε16 } and

Jβ1= { ε3-ε2, ε4-ε2, ε5-ε2, ε6-ε3, ε6-ε4, ε6-ε5, ε9-ε7, ε9-ε8, ε10-ε7, ε10-ε8 }

then the book of shapes is

0 1 -2 -1 -1 0 -1 1 -1 0 1 -1 0 0 -2 0 1 Page0 Page12

where the numbers in the boxes are the contents of the boxes. The filling

1 8 2 4 3 6 5 11 7 10 14 9 13 16 12 15 17 Page0 Page12

is a standard tableau of shape (γ,J). This filling corresponds to the permutation

w= ( 2,12,4,5,9,1,13, 14,8,11,17,3,7,6, 10,16,14 ) in (γ,J) S16.

Notes and References

This is an excerpt of the paper entitled Affine Hecke algebras and generalized standard Young tableaux written by Arun Ram in 2002, published in the Academic Press Journal of Algebra 260 (2003) 367-415. The paper was dedicated to Robert Steinberg.

Research supported in part by the National Science Foundation (DMS-0097977) and the National Security Agency (MDA904-01-1-0032).

page history