<<

. 5
( 14 .)



>>

closely related to the famous “Eightfold Way” of particle physics. (The
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

<<

. 5
( 14 .)



>>