corresponding representation of GL(n, C), when restricted to SL(n, C), is

just the adjoint representation of SL(n, C).)

The symmetric functions s» (x1 , . . . , xn ) are known as Schur functions

(in the variables x1 , . . . , xn ) and play an important role in many aspects of

representation theory, the theory of symmetric functions, and enumerative

combinatorics. In particular, they are closely related to the irreducible rep-

resentations of a certain ¬nite group, namely, the symmetric group Sk of all

permutations of the set {1, 2, . . . , k}. This relationship is best understood by

a “duality” between GL(n, C) and Sk discovered by Issai Schur (1875“1941).

Recall that we are regarding GL(n, C) as acting on an n-dimensional

vector space V . Thus GL(n, C) also acts on the kth tensor power V —k of V .

The group Sk also acts on V —k by permuting tensor coordinates. Schur™s

famous “double centralizer” theorem asserts that the actions of GL(n, C) and

Sk centralize each other, i.e., every endomorphism of V —k commuting with

the action of GL(n, C) is a linear combination of the actions of the elements

of Sk , and vice versa. From this one can show that the action of the group

Sk — GL(n, C) on V —k breaks up into irreducible constituents in the form

V —k = M » — F» , (20)

»

where (a) denotes a direct sum of vector spaces, (b) » ranges over all

partitions of k into at most n parts, (c) F» is the irreducible GL(n, C)-

module corresponding to », and M » is an irreducible Sk -module. Thus when

27

k ¤ n, » ranges over all partitions of k. The p(k) irreducible Sk -modules M »

are pairwise nonisomorphic and account for all the irreducible Sk -modules.

Hence the irreducible Sk -modules are naturally indexed by partitions of k.

Using the Schensted correspondence (or otherwise), it is easy to prove the

identity

(x1 + x2 + · · · + xn )k = f » s» (x1 , . . . , xn ),

»

where » ranges over all partitions of k and f » denotes as usual the number

of SYT of shape ». Comparing with equation (20) and using the fact that

the character of GL(n, C) acting on V —k is (x1 + · · · + xn )k , we see that

dim M » = f » . Thus the f » ™s for » a partition of k are the degrees of the

irreducible representations of Sk . Since the sum of the squares of the degrees

of the irreducible representations of a ¬nite group G is equal to the order

(number of elements) of G, we obtain equation (18) (with n replaced by k).

We have only given the briefest glimpse of the connections between tableaux

combinatorics and representation theory, but we hope that it gives the reader

with su¬cient mathematical background the ¬‚avor of this subject.

5 Increasing and decreasing subsequences.

In this section we discuss an unexpected connection between the Schensted

correspondence and the enumeration of a certain class of permutations. This

connection was discovered by Schensted and was his reason for inventing his

famous correspondence. If w = a1 a2 · · · an is a permutation of 1, 2, . . . , n,

then a subsequence v of length k of w is a sequence of k distinct terms of

w appearing in the order in which they appear in w. In symbols, we have

v = ai1 ai2 · · · aik , where i1 < i2 < · · · < ik . For instance, some subsequences

of the permutation 6251743 are 2573, 174, 6, and 6251743. A subsequence

b1 b2 · · · bk of w is said to be increasing if b1 < b2 < · · · < bk , and decreasing if

b1 > b2 > · · · > bk . For instance, some increasing subsequences of 6251743 are

67, 257, and 3, while some decreasing subsequences are 6543, 654, 743, 61,

28

and 3.

We will be interestested in the length of the longest increasing and de-

creasing subsequences of a permutation w. Denote by i(w) the length of the

longest increasing subsequence of w, and by d(w) the length of the longest

decreasing subsequence. By careful inspection one sees for instance that

i(6251743) = 3 and d(6251743) = 4. It is intuitively plausible that there

should be some kind of tradeo¬ between the values i(w) and d(w). If i(w) is

small, say equal to k, then any subsequence of w of length k + 1 must con-

tain a pair of decreasing elements, so there are “lots” of pairs of decreasing

elements. Hence we would expect d(w) to be large. An extreme case occurs

when i(w) = 1. Then there is only one choice for w, namely, n, n ’ 1, . . . , 1,

and we have d(w) = n.

How can we quantify the feeling that that i(w) and d(w) cannot both be

small? A famous result of Pal (??) Erd˝s (1913“1996) and George Szekeres

o

(b. 1911), obtained in 1935, gives an answer to this question and was one of

the ¬rst results in the currently very active area of extremal combinatorics.

Let w be a permutation of 1, 2, . . . , n. The Erd˝s-Szekeres theorem states

o

that if p and q are positive integers for which n > pq, then either i(w) > p

or d(w) > q. Moreover, this result is best possible in the sense that if

n = pq then we can ¬nd at least one permutation w such that i(w) = p and

d(w) = q. An equivalent way to formulate the Erd˝s-Szekeres theorem is by

o

the inequality

i(w) · d(w) ≥ n,

showing clearly that i(w) and d(w) cannot both be small. For instance, both

√

can™t be less than n, the square root of n.

After Erd˝s and Szekeres proved their theorem, an extremely elegant

o

proof was given in 1959 by Abraham Seidenberg (1916“1988) based on a

ubiquitous mathematical tool known as the pigeonhole principle. This prin-

ciple states that if m + 1 pigeons ¬‚y into m pigeonholes, then at least one

pigeonhole contains more than one pigeon. As trivial as the pigeonhole prin-

ciple may sound, it has numerous nontrivial applications. The hard part in

applying the pigeonhole principle is deciding what are the pigeons and what

are the pigeonholes.

29

We can now describe Seidenberg™s proof of the Erd˝s-Szekeres theorem.

o

Given a permutation w = a1 a2 · · · an of 1, 2, . . . , n, we de¬ne numbers r1 , r2 ,

. . . , rn and s1 , s2 , . . . , sn as follows. Let ri be the length of the longest in-

creasing subsequence of w that ends at ai , and similarly let si be the length

of the longest decreasing subsequence of w that ends at ai . For instance,

if w = 6251743 as above then s4 = 3 since the longest decreasing subse-

quences ending at a4 = 1 are 621 and 651, of length three. More gen-

erally, we have for w = 6251743 that (r1 , . . . , r7 ) = (1, 1, 2, 1, 3, 2, 2) and

(s1 , . . . , s7 ) = (1, 2, 2, 3, 1, 3, 4).

Key fact. The n pairs (r1 , s1 ), (r2 , s2 ), . . . , (rn , sn ) are all distinct.

To see why this fact is true, suppose i and j are numbers such that i < j

and ai < aj . Then we can append aj to the end of the longest increasing

subsequence of w ending at ai to get an increasing subsequence of greater

length that ends at aj . Hence rj > ri . Similarly, if i < j and ai > aj , then

we get sj > si . Therefore we cannot have both ri = rj and si = sj , which

proves the key fact.

Now suppose n > pq as in the statement of the Erd˝s-Szekeres theorem.

o

We therefore have n distinct pairs (r1 , s1 ), (r2 , s2 ), . . . , (rn , sn ) of positive

integers. If every ri were at most p and every si were at most q, then there

are only pq possible pairs (ri , si ) (since there are at most p choices for ri

and at most q choices for si ). Hence two of these pairs would have to be

equal. (This is where the pigeonhole principle comes in ” we are putting

the “pigeon” i into the “pigeonhole” (ri , si ) for 1 ¤ i ¤ n. Thus there are

n pigeons, where n > pq, and at most pq pigeonholes.) But if two pairs

are equal, then we contradict the key fact above. It follows that for some

i either ri > p or si > q. If ri > p then there is an increasing subsequence

of w of length at least p + 1 ending at ai , so i(w) > p. Similarly, if si > q

then d(w) > q, completing the proof of the main part of the Erd˝s-Szekeres o

theorem.

It remains to show that the result is best possible, as explained above. In

other words, given p and q, we need to exhibit at least one permutation w

of 1, 2, . . . , pq such that i(w) = p and d(w) = q. It is easy to check that the

30

following choice of w works:

w = (q ’ 1)p + 1, (q ’ 1)p + 2, . . . , qp, (q ’ 2)p + 1, (q ’ 2)p + 2, . . . , (q ’ 1)p,

. . . , 2p + 1, 2p + 2, . . . , 3p, p + 1, p + 2, . . . , 2p, 1, 2, . . . , p. (21)

This completes the proof of the Erd˝s-Szekeres theorem.

o

Though the Erd˝s-Szekeres theorem is very elegant, we can ask for even

o

more information about increasing and decreasing subsequences. For in-

stance, rather than exhibiting a single permutation w of 1, 2, . . . , pq satisfying

i(w) = p and d(w) = q, we can ask how many such permutations there are.

This much harder question can be answered by using an unexpected connec-

tion between increasing and decreasing subsequences on the one hand, and

the Schensted correspondence on the other.

There are two fundamental properties of the Schensted correspondence

that are needed for our purposes. Suppose we apply the Schensted correspon-

dence to a permutation w = a1 a2 · · · an of 1, 2, . . . , n, getting two column-

strict plane partitions P and Q whose parts are 1, 2, . . . , n. The ¬rst property

we need of the Schensted correspondence is a simple description of the ¬rst

row of P .

Property 1. Suppose that the ¬rst row of P is b1 b2 · · · bk . Then bi is the

last (rightmost) term in w such that the longest decreasing subsequence of w

ending at that term has length i.

For instance, suppose w = 843716925. Then

9765

P = 832 .

41

The ¬rst row of P is 9765. Consider the third element of this row, which is

6. Then 6 is the rightmost term of w for which the longest decreasing subse-

quence of w ending at that term has length three. Indeed, 876 is a decreasing

subsequence of length three ending at 6, and there is none longer. The terms

to the right of 6 are 9, 2, and 5. The longest decreasing subsequences ending

at these terms have length 1, 4, and 4, respectively, so 6 is indeed the right-

most term for which the longest decreasing subsequence ending at that term

has length three.

31

See the Box for a proof by induction of Property 1.

BOX. Proof of Property 1. Recall that w = a1 a2 · · · an . We prove

by induction on j that after the Schensted algorithm has been applied to

a1 a2 · · · aj , yielding a pair (Pj , Qj ) of column-strict plane partitions, then

the ith entry in the ¬rst row of Pj is the rightmost term of the sequence

a1 a2 · · · aj such that the longest decreasing subsequence ending at that term

has length i. Once this is proved, then set j = n to obtain Property 1.

The assertion is clearly true for j = 1. Assume true for j. Suppose

that the ¬rst row of Pj is c1 c2 · · · cr . By the induction hypothesis, ci is the

rightmost term of the sequence a1 a2 · · · aj such that the longest decreasing

subsequence ending at that term has length i. We now insert aj+1 into the

¬rst row of Pj according to the rules of the Schensted algorithm. It will bump

the leftmost element ci of this row which is less than aj+1 . (If there is no

element of the ¬rst row of Pj which is less than aj+1 , then aj+1 is inserted at

the end of the row. We then set i = r + 1, so that aj+1 is in all cases the ith

element of the ¬rst row of Pj+1 .) We need to show that the longest decreasing

subsequence of the sequence a1 a2 · · · aj+1 ending at aj+1 has length i, since

clearly aj+1 will be the rightmost element of a1 a2 · · · aj+1 with this property

(since it is the rightmost element of the entire sequence).

If i = 1, then aj+1 is the largest element of the sequence a1 a2 · · · aj+1 , so

the longest decreasing subsequence ending at aj+1 has length one, as desired.

If i > 1, then there is a decreasing subsequence of a1 a2 · · · aj of length i ’ 1

ending at ci’1 . Adjoining aj+1 to the end of this subsequence produces a

decreasing subsequence of length i ending at aj+1 . It remains to show that

there cannot be a longer decreasing subsequence ending at aj+1 . If there

were, then there would be some term as in w to the left of aj+1 and larger

than aj+1 such that the longest decreasing subsequence ending at as has

length i. Thus when as is inserted into Ps’1 during the Schensted algorithm,

it becomes the ith element of the ¬rst row. It can only be bumped by terms

larger than as . In particular, when aj+1 is inserted into the ¬rst row, the

ith element is larger than as , which is larger than aj+1 . This contradicts the

de¬nition of the bumping procedure and completes the proof.

32

Figure 4: The Young diagram of a partition and its conjugate

The second property we need of the Schensted correspondence was ¬rst

proved by Schensted. To describe this property we require the following

de¬nition. If » is a partition, then the conjugate partition » of » is the

partition whose Young diagram is obtained by interchanging the rows and

columns of the Young diagram of ». In other words, if » = (»1 , »2 , . . .), then

the column lengths of the Young diagram of » are »1 , »2 , . . .. For instance,

if » = (5, 3, 3, 2) then » = (4, 4, 3, 1, 1), as illustrated in Figure 4.

Property 2. Suppose that when the Schensted correspondence is applied

to a permutation w = a1 a2 · · · an , we obtain the pair (P, Q) of reverse SYT.

Let w = an an’1 · · · a1 , the reverse permutation of w. Suppose that when

¯

¯¯

the Schensted correspondence is applied to w, we obtain the pair (P , Q) of

¯

¯ ¯

reverse SYT. Then the shape of P (or Q) is conjugate to the shape of P (or

Q).

Actually, an even stronger result than Property 2 is true, though we don™t

¯

need it for our purposes. The reverse SYT P is actually the transpose of P ,

obtained by interchanging the rows and columns of P . (The connection

¯

between Q and Q is more subtle and has led to much interesting work.) The

proof of Property 2 is too complicated for inclusion here, though it is entirely

elementary.

33