Re ent Progress

in Algebrai Combinatori s

Ri hard P. Stanley1
Department of Mathemati s
Massa husetts Institute of Te hnology
Cambridge, MA 02139
e-mail: rstan[Link]
version of 19 Mar h 2002

1 Introdu tion.

Algebrai ombinatori s is alive and well at the dawn at the new millenium.
Algebrai ombinatori s is diÆ ult to de ne pre isely; roughly speaking it in-
volves obje ts that an be interpreted both ombinatorially and algebrai ally,
e.g., as the ardinality of a ombinatorially de ned set and the dimension of
an algebrai ally de ned ve tor spa e. Sometimes the ombinatorial inter-
pretation is used to obtain an algebrai result, and sometimes vi e versa.
Mathemati ians have been engaged in algebrai ombinatori s at least sin e
Euler (in parti ular, his work on partitions), but it wasn't until the 1960's,
primarily under the in uen e of Gian-Carlo Rota, that there was a systemati
attempt to establish the foundations of algebrai ombinatori s and bring it
into the mathemati al mainstream. This e ort has been highly su essful,
and algebrai ombinatori s has by now be ome a mature and thriving dis-
ipline.
We have hosen three major breakthroughs to highlight re ent work in
algebrai ombinatori s. All three areas have initiated a urry of further
work and suggest many further dire tions of resear h to keep pra titioners
of algebrai ombinatori s o upied well into the new entury. Our hoi e
of topi s was partially in uen ed by the relative ease in des ribing the main
results to nonexperts in algebrai ombinatori s. Mu h other outstanding
work has been done that is not dis ussed here.
1 Partially supported by NSF grant #DMS-9988459.

1
2 The saturation onje ture.

The saturation onje ture on erns ertain integers known as Littlewood-

Ri hardson oeÆ ients. Given the theme of this paper, it is not surprising
that they have both an algebrai and a ombinatorial de nition. First we
dis uss the algebrai de nition, whi h is more natural than the ombinatorial
one.
Let GL(n; C ) denote the group of all invertible transformations from an n-
dimensional omplex ve tor spa e V to itself. After hoosing an ordered basis
for V we may identify GL(n; C ) with the group of n  n nonsingular matri es
over the omplex numbers (with the operation of matrix multipli ation).
Consider the map ' : GL(2; C ) ! GL(3; C ) de ned by
2 2 3
  a 2 ab b2

' a db = 4 a ad + b bd 5 :
2
2 d d2
This an be he ked to be a group homomorphism (and hen e a representa-
tion of GL(2; C ) of degree 3). Moreover, the entries of '(A) are polynomial
fun tions of the entries of A. Hen e ' is a polynomial representation of
GL(2; C ). If A 2 GL(2; C ) has eigenvalues x; y , then it an also be he ked
that '(A) has eigenvalues x2 ; xy; y 2. De ne the hara ter har ' of ' to be
the tra e of '(A), regarded as a fun tion of the eigenvalues x; y of A. Hen e
har ' = x2 + xy + y 2 :
It was rst shown by S hur that the polynomial representations of GL(n; C )
are ompletely redu ible, i.e., a dire t sum of irredu ible representations. The
nequivalent irredu ible polynomial representations ' of GL(n; C ) are in-
dexed by partitions  = (1 ; : : : ; n) of length at most n, i.e., i 2 Z and
1 


 n  0. Moreover, har ' is a symmetri fun tion s (x1 ; : : : ; xn )
that had been originally de ned by Cau hy and Ja obi and is now known as
a S hur fun tion. A well-known property of S hur fun tions is their stability :
s (x1 ; : : : ; xn ; 0) = s (x1 ; : : : ; xn ):
For this reason we an let n ! 1 and onsider the S hur fun tion s in
in nitely many variables x1 ; x2 ; : : : and spe ialize to x1 ; : : : ; xn when deal-
ing with GL(n; C ). For more information on symmetri fun tions and the
representation theory of GL(n; C ), see [8℄[30℄[37℄.

2
 If A : V ! V and B : W !W are linear transformations on nite-
dimensional ve tor spa es, then
tr(A B ) = tr(A)
tr(B );
where A B denotes the tensor (or Krone ker) produ t of A and B , a ting
on V W . Hen e if , , and  are partitions and we set
 = mult(' ; ' ' ) ;


the multipli ity of ' in the tensor produ t ' ' (when written as a dire t
sum of irredu ible representations), then
X
s s =  s :
 


The nonnegative integers  are known as Littlewood-Ri hardson o-

eÆ ients, and the Littlewood-Ri hardson rule [8, Ch. 5℄[30, xI.9℄[37, Ap-
pendix A1.3℄ gives a ombinatorial interpretation of them (whi h we will not
state here). If m is a positive integer and  = (1 ; 2 ; : : :) a partition, then
write m = (m1 ; m2 ; : : :).
Saturation onje ture. If m
m;m 6= 0, then 
 6= 0.
The saturation onje ture was proved re ently by Allen Knutson and
Teren e Tao [26℄[27℄ using a new honey omb model for des ribing Littlewood-
Ri hardson oeÆ ients. An elegant exposition of the proof was given by
Anders Bu h [5℄, and a detailed survey of all the material in this se tion (and
more) was given by William Fulton [9℄. A proof of the saturation onje ture
based on representations of quivers was later given by Harm Derksen and
Jerzy Weyman [7℄.
Why is the proof of the saturation onje ture an important breakthrough?
The answer is that it is related in a surprising way to a number of other topi s.
The rst on erns the eigenvalues of hermitian matri es. Let A; B; C be n  n
hermitian matri es. Hen e their eigenvalues are real. Denote the eigenvalues
of A as
: 1 


 n;

3
and similarly and for B and C . Considerable attention has been given
to the following problem.
Problem. Chara terize those triples ( ; ; ) for whi h there exist her-
mitian matri es A + B = C with eigenvalues , , and .
By taking tra es we see that
X X X
i = i+ i: (1)
After mu h work by a number of resear hers, A. Horn onje tured a omplete
hara terization of triples ( ; ; ), onsisting of (1) together with linear
inequalities of the form
X X X
k  i+ j; (2)
k2K i2I j 2J
for ertain sets
I; J; K  f1; : : : ; ng; jI j = jJ j = jK j:
For instan e, when n = 2 Horn's inequalities (whi h are easy to show that
together with (1) hara terize ( ; ; ) in this ase) be ome
1  1 + 1
2  2 + 1

2  1 + 2:

For n = 3 there are twelve inequalities, as follows:

1  1 + 1

2  min( 1 + 2; 2 + 1)
3  min( 1 + 3; 2 + 2; 3 + 1)

1 + 2  1 + 2 + 1 + 2

1 + 3  min( 1 + 2 + 1 + 3; 1 + 3 + 1 + 2)
2 + 3  min( 1 + 2 + 2 + 3; 1 + 3 + 1 + 3; 2 + 3 + 1 + 2 ):

The onne tion between the Saturation Conje ture and Horn's onje ture
was given by Alexander Klya hko [24℄.

4
 Theorem. The Saturation Conje ture implies Horn's onje ture.
A more pre ise onne tion between Littlewood-Ri hardson oeÆ ients
and eigenvalues of hermitian matri es is provided by the following result,
impli it in the work of He kman [22℄ and more expli it in Klya hko [24℄.
Theorem. Let ; , and be partitions of length at most n. The Sat-
uration Conje ture implies that the following two onditions are equivalent:

 6= 0.
 There exist n  n hermitian matri es A + B = C with eigenvalues ; ,
and .

Sin e equation (2) onsists of linear inequalities, the two theorems above
show that the nonvanishing of depends on (expli it) linear inequalities
among the oordinates of ; ; . Thus for xed n the points ( ; ; ) 2 R 3n
for whi h 6= 0 are the integer points in a ertain onvex one. Hen e the
subje t of polyhedral ombinatori s is losely asso iated with the theory of
Littlewood-Ri hardson oeÆ ients. For further information on this point of
view, see [41℄.
The theorems stated above involve hermitian matri es. It is known [9,
Thm. 3℄ that exa tly the same results hold for the lass of real symmetri
matri es.
There are a number of other situations in whi h Littlewood-Ri hardson
oeÆ ients play a surprising role. These situations are thoroughly dis ussed
in [9℄. We mention one of them here. Given a partition  = (1 ; 2 ; : : :) and
a prime p, let G be a ( nite) abelian p-group of type , i.e.,
G



= Z=p1 Z  Z=p Z 


:
2

 (p) denote the number of subgroups

Given further partitions  and  , let g
H of G of type  su h that the quotient group G=H has type  .
Theorem.
 (p) is a polynomial fun tion of p with integer oeÆ-
(a) g
ients.

5
  (p) 6= 0 if and only if
(b) For any prime p we have that g  6= 0.


The polynomial g  (t) is alled a Hall polynomial after the pioneering
work of Philip Hall [20℄. Hall established the above theorem, ex ept that in
part (b) he only showed that g  (t) vanishes identi ally (as a polynomial in
t) if and only if  = 0. Subsequently Miller Maley [31℄ showed that the
polynomial g (t + 1) has nonnegative oeÆ ients, from whi h (b) follows.
For an exposition of the basi properties of Hall polynomials, see [30, Chs. II
and III.2℄. The theory of Hall polynomials holds in the more general ontext
of the ring of integers (i.e., the unique maximal order) of a division algebra
of nite rank over a p-adi eld [30, Remark 3, p. 179℄ or even more generally
for q -primary latti es [38, Thm. 4.81℄.

3 The n! and ( n + 1)n 1 onje tures.

The n! and (n + 1)n 1 onje tures on ern the a tion of the symmetri group
Sn on two sets (x1 ; : : : ; xn) and (y1; : : : ; yn) of n variables. In order to appre-
iate these onje tures, knowledge of the situation for one set of n variables
is of value. We therefore rst review this theory (for whi h the proofs are
mu h easier). Sn a ts on the polynomial ring A = C [x1 ; : : : ; xn ℄ by permut-
ing variables, i.e., for w 2 Sn let w
xi = xw(i) and extend to all of A in the
obvious way. Let
ASn = ff 2 A : w
f = f 8w 2 Sn g;
the ring of invariants of the a tion of Sn on A. The invariant polynomials
f 2 ASn are the symmetri polynomials in the variables x1 ; : : : ; xn (over C ).
The \fundamental theorem of symmetri fun tions" asserts that
ASn = C [e1 ; : : : ; en ℄;
a polynomial ring in the algebrai ally independent elementary symmetri
fun tions X
ek = xi1


xik :
1i1 <


<ik n
Regard n as xed and de ne the ring
R = A=(e1 ; : : : ; en ):

6
The ring R inherits the usual grading from A, i.e.,
R = R0  R1 


;
where Ri is spanned by (the images of) all homogeneous polynomials of
degree i in the variables x1 ; : : : ; xn . Be ause the generators e1 ; : : : ; en of RSn
are algebrai ally independent of degrees 1; 2; : : : ; n, it is easy to see that
dimC R = n!;
and more generally,
X
dimC (Ri ) q i = (1 + q )(1 + q + q 2 )


(1 + q +


+ q n 1 ); (3)
i

the standard \q -analogue" of n!.

Sin e the ideal (e1 ; : : : ; en ) of R is Sn -invariant, Sn a ts on R. Moreover,
this a tion respe ts the grading of R, i.e., w
Ri = Ri for all w 2 Sn. Thus
R is in fa t a graded Sn -module, and we an ask, as a re nement of (3),
for the multipli ity of ea h irredu ible representation of Sn in Ri . For the
a tion on R as a whole the situation is simple to des ribe (and not diÆ ult
to prove): R a ords the regular representation of Sn, i.e., the multipli ity of
ea h irredu ible representation is its degree (or dimension).
To des ribe the Sn-module stru ture of Ri , we need some understanding
of the (inequivalent) irredu ible representations of Sn. They are indexed
by partitions  of n (denoted
P
 ` n), i.e,  = (1 ; : : : ; `) 2 Z` where
1 


 ` > 0 and i = n. The dimension of the irredu ible Sn-
module M indexed by  ` n is denoted by f  and is equal to the number
of standard Young tableaux (SYT) of shape , i.e., the number of ways to
insert the numbers 1; 2; : : : ; n (without repetition) into an array of shape 
(i.e., left-justi ed with i entries in row i) so that every row and olumn is
in reasing. For instan e f (3;2) = 5, as shown by the ve SYT
123 124 125 134 135 :
45 35 34 25 24
There is also a simple expli it formula (e.g., [30, Exam. I.5.2℄[37, Cor. 7.21.6℄),
known as the hook-length formula, for f  .

7
 Sin e R a ords the regular representation of Sn , the multipli ity of M
in R is equal to f  . Thus we would like to des ribe the multipli ity of M
in Ri as the number of SYT T of shape  with some additional property
depending on i. This property is the value of the major index of T , denoted
MAJ(T ). It is de ned by
X
MAJ(T ) = i;
i+1 below i in T

where the sum ranges over all entries i of T su h that i + 1 appears in a

lower row than i. For instan e, the SYT of shape (3; 2; 2) shown below has
MAJ(T ) = 2 + 3 + 6 = 11.
126
T = 35 :
47
The following result is due independently to Lusztig (unpublished) and Stan-
ley [36, Prop. 4.11℄.
Theorem. Let  ` n. Then
mult(M ; Ri ) = #fSYT T : shape(T ) = ; MAJ(T ) = ig:

For example, let n = 5. There are three SYT with ve entries and major
index 3, namely,
1235 123 145
4 45 2 :
3
It follows that
R3 
= M41  M32  M311 :
There is another des ription of R whi h leads to a di erent generalization to
two sets of n variables. Given any polynomial P (x1 ; : : : ; xn ) over C , de ne P
to be the omplex ve tor spa e spanned by P and all its partial derivatives
of all orders. For instan e  (x + y )2 has dimension three, one basis being
f(x + y)2; x + y; 1g. Let
Y
Vn = (xi xj ): (4)
1i<j n

8
It is easy to see that
R= Vn
as graded Sn -modules. In parti ular, dim(Vn ) = n! and Vn a ords the
regular representation of Sn.
Adriano Garsia and Mark Haiman had the idea of generalizing the above
onstru tions of R and Vn to two sets x = (x1 ; : : : ; xn ) and y = (y1 ; : : : ; yn )
of n variables. For the rst generalization, let Sn a t diagonally on B =
C [x; y ℄, i.e.,
w
xi = xw(i) ; w
yi = yw(i) :
Let
B Sn = ff 2 B : w
f = f 8w 2 Sn g;
the ring of invariants of the a tion of Sn on B . It is no longer the ase
that B Sn is generated by algebrai independent elements. (For general in-
formation about rings of invariants of nite groups, see for instan e [35℄[36℄.)
However, we an still de ne
R(2) = S=I;
where I is the ideal of B generated by elements of B Sn with zero onstant
term. The (n + 1)n 1 onje ture of Garsia and Haiman [12℄[13℄ was re ently
proved by Haiman [19℄, based on te hniques he developed to prove the n!
onje ture dis ussed below, together with a theorem of Bridgeland, King,
and Reid on the M Kay orresponden e.
Theorem ((n + 1)n 1
onje ture). dimC R(2) = (n + 1)n 1

Just as R had the additional stru ture of a graded Sn-module, similarly

R is a bigraded Sn-module. In other words,
(2)

M
R(2) = Rij(2) (ve tor spa e dire t sum);
i;j

where Rij(2) is the subspa e of R(2) spanned by (the images of) polynomials
that are homogeneous of degree i in the x variables and degree j in the y
variables, and moreover Rij(2) is invariant under the a tion of Sn on R(2) . For
instan e, when n = 4 it an be omputed that
R2(2);1 
= 2M211  M22  M31 :

9
In parti ular,
dimC R2(2);1 = 2f 211 + f 22 + f 31 = 2
3 + 2 + 3 = 12:
Garsia and Haiman stated in [11℄ (see also [17, Conj. 7.5℄) a ompli ated
onje tured formula for mult(M ; Rij(2) ). Haiman's proof of the (n + 1)n 1
onje ture mentioned above a tually establishes this stronger onje ture of
Garsia and Haiman. A onsequen e of Haiman's result asserts the following
[11℄[17, p. 246℄. Let be the anti-invariant subspa e of R(2) , i.e.,
= ff 2R (2)
: w
f = sgn(w)f 8f 2 Sng;
where sgn(w) denotes the sign of the permutation w. Then
 
1 2n
dimC = ;
n+1 n
a Catalan number. James Haglund [16℄ onje tured and Garsia and Haglund
[10℄ proved a ombinatorial interpretation of the bigrading, i.e., a om-
binatorial interpretation of the numbers dimC ij . For some information
on the ubiquitious appearan e of Catalan (and related) numbers through-
out mathemati s, see [37, Exer. 6.19{6.38℄ and the addendum at www-
[Link]/rstan/e .html.
The number dimC R(2) = (n + 1)n 1 has a number of ombinatorial inter-
pretations, e.g., it is the number of forests of rooted trees on n verti es [37,
Prop. 5.3.2℄ or the number of parking fun tions of length n [37, Exer. 5.49℄.
It is natural to ask whether one an give a ombinatorial interpretation of
dimC Rij(2) that re nes some known interpretation of (n + 1)n 1 . At present
this question is open.
We turn to the se ond generalization of R due to to Garsia and Haiman.
First we need to de ne a generalization of the Vandermonde produ t (4) to
two sets of variables. Let  ` n. Coordinatize the squares of the diagram of
 by letting (i 1; j 1) be the oordinate of the square in the ith row and
j th olumn. For instan e, the oordinates of the squares of the diagram of
 = (3; 2) are given by

10
 0,0 0,1 0,2

1,0 1,1

Let (i1 ; j1 ); : : : ; (in ; jn ) be the oordinates of the squares of the diagram

of  (in some order), and de ne the n  n determinant
D = xirs yrjs r;s=1;:::;n :

For instan e,
1 y1 y12 x1 x1 y1
1 y2 y22 x2 x2 y2
D32 = 1 y3 y32 x3 x3 y3 :
1 y4 y42 x4 x4 y4
1 y5 y52 x5 x5 y5
Note that if  onsists of a single row (i.e.,  onsists of the single part n)
then D = Vn (y ), while if  onsists of a single olumn then D = Vn (x).
The n! onje ture of Garsia and Haiman [12℄[13℄, later proved by Haiman
[18℄, is the following assertion.
Theorem (n! onje ture). For any  ` n, we have
dimC D = n!:

The spa e D , just as R(2) , is a bigraded Sn-module. For ea h i; j 0

and  ` n, we an ask for a \des ription" of the integer mult M ; (D )ij .
Garsia and Haiman [12℄[13℄ gave su h a des ription, and Haiman [17, Thm.
5.4℄ showed that it a tually followed from the n! onje ture. The Garsia-
Haiman des ription involves the theory of Ma donald symmetri fun tions,
a generalization of S hur fun tions due to I. G. Ma donald [29℄[30, Ch. VI℄
and urrently of great interest in several di erent areas, su h as the represen-
tation theory of quantum groups, aÆne He ke algebras, and the Calegero-
Sutherland model in parti le physi s (see [18℄ for referen es). We won't

11
de ne Ma donald symmetri fun tions here but will give a brief indi ation
of Haiman's result.
Let ;  ` n. The oeÆ ient of x = x1 1 x2 2


in the S hur fun tion s
is known as a Kostka number, denoted K , and has a simple ombinato-
rial interpretation in terms of semistandard Young tableaux [30, (5.13)℄[37,
x7.10℄. In the theory of Ma donald polynomials there arises naturally a two-
parameter generalization K (q; t) of the Kostka number K = K (0; 1). A
priori K (q; t) is only a rational fun tion of q and t, but Ma donald onje -
tured that it was a polynomial with nonnegative integer oeÆ ients. In 1996{
98 several independent proofs were given that K (q; t) was indeed a poly-
nomial with integer oeÆ ients, but nonnegativity remained open. Haiman
showed the remarkable fa t that K (q; t) is essentially the bigraded Hilbert
series for the -isotypi omponent of D . More pre isely,
X  
tb() K (q; 1=t) = mult M ; (D )r;s tr q s ;
r;s0
P
where b() = (i 1)i. This formula establishes the nonnegativity of
the oeÆ ients of K (q; t), though a ombinatorial interpretation of these
oeÆ ients remains open.
Hamian's proof is based on the geometry of the Hilbert s heme Hilbn (C 2 )
of n points in the plane. (Claudio Pro esi suggested to Haiman the possible
relevan e of the Hilbert s heme.) Let X and Y be indeterminates. We an
de ne Hilbn (C 2 ) as a set by
Hilbn (C 2 ) = fI  C [X; Y ℄ : dimC C [X; Y ℄=I = ng;
i.e., all ideals I of C [X; Y ℄ su h that the quotient ring C [X; Y ℄=I is an n-
dimensional ve tor spa e. Suppose that Z = fz1 ; : : : ; zn g is a set of n distin t
points in C 2 . Let
IZ = ff 2 C [X; Y ℄ : f (z ) =


= f (zn) = 0g:
1

Then IZ is an ideal of C [X; Y ℄ su h that C [X; Y ℄=IZ an be identi ed with

the spa e of all fun tions f : Z ! C , so IZ 2 Hilbn (C 2 ). This explains
why Hilbn (C 2 ) is alled the Hilbert s heme of n points in the plane | it is
a losure of the spa e of all n-element subsets of C 2 . In fa t, Hilbn (C 2 ) has
the stru ture of a smooth irredu ible algebrai variety, of dimension 2n.

12
 The remarkable onne tions between Hilbn (C 2 ) and the n! and (n +1)n 1
onje tures are too te hni al to dis uss here, but let us give a vague hint or
two. Write H n = Hilbn (C 2 ). Given a partition  ` n, let U be the set of all
ideals I 2 H n su h that a basis for C [x; y ℄=I onsists of the (images of the)
monomials xh y k , where the (h; k)'s are the oordinates for the squares of the
diagram of . Then the sets U are open, aÆne, and over H n, suggesting
the possible relevan e of H n to the n! onje ture. Moreover, for ea h I 2 H n
there is a natural way to asso iate an n-element multiset  (I )  C 2 . The
n-element multisets ontained in C 2 form an aÆne variety Symn (C 2 ), viz.,
Symn (C 2 ) = (C 2 )n =Sn = Spe C [x1 ; : : : ; xn ; y1 ; : : : ; yn ℄Sn ;

suggesting the possible relevan e of H n to the (n + 1)n 1

onje ture. See the
papers [17℄ and [18℄ for details.
It is natural to ask about generalizing the work of Garsia and Haiman to
more than two sets of variables. However, all obvious onje tures turn out
to be false. One diÆ ult is that the Hilbert s heme Hilbn(C k ) is no longer
smooth for k > 2.
The (n + 1)n 1 and n! onje tures are just the beginning of an amazing
edi e of onje tures due to Garsia, Haiman, and their ollaborators. For
instan e, we de ned a determinant D when  is a partition of n, regarded as
a ertain subset of N  N (where N = f0; 1; 2; : : :g). In exa tly the same way
we an de ne DX for any n-element subset X of N  N . Bergeron, Garsia,
and Tesler [3℄ then onje ture (and prove in some spe ial ases) for several
lasses of subsets X that dimC (DX ) = kX n! for some positive integer kX ;
and in fa t DX , regarded as an Sn -module, a ords kX opies of the regular
representation.

4 Longest in reasing subsequen es.

Let w = a1 a2


an 2 Sn . An in reasing subsequen e of w is a subsequen e

ai1 ai2


aik of w for whi h ai1 < ai2 <


< aik . Let isn (w) denote the
length of the longest in reasing subsequen e of w 2 Sn. For instan e, if w =
274163958 2 S9 then is9 (w) = 4, exempli ed by the in reasing subsequen es

13
2469 and 1358. There has been mu h re ent interest in the behavior of the
fun tion isn (w). A survey of mu h of this work has been given by Per y Deift
[6℄.
The rst question of interest is the expe ted value E (n) of isn (w), where
w ranges uniformly over Sn. Thus
1 X
E (n) = is (w):
n! w2Sn n
Elementary arguments show that
1p p
n  E (n)  e n;
2
and Hammersley [21, Thm. 4℄ showed in 1972, using subadditive ergodi
theory, that the limit
E (n)
= nlim
!1 n
p
exists. Vershik and Kerov [40℄ (with the diÆ ult dire tion  2 shown
independently by Logan and Shepp [28℄) showed in 1977 that = 2.
The proof of Vershik-Kerov and Logan-Shepp is based on the identity
1X

E (n) = 1 f  2 ; (5)
n! `n
where  = (1 ; 2 ; : : :) and f  denotes the number of SYT of shape  as in
Se tion 3. Equation (5) is due to Craige S hensted [34℄ and is an immediate
onsequen e of the Robinson-S hensted-Knuth algorithm; see also [37, Exer.
7.109(a)℄.
The work of Vershik-Kerov and Logan-Shepp only determines the asymp-
toti behavior of the expe tation of isn(w). What about stronger results? A
major breakthrough was made by Jinho Baik, Per y Deift, and Kurt Johans-
son [1℄, and has inspired mu h further work. To des ribe their results, let
Ai(x) denote the Airy fun tion, viz., the unique solution to the se ond-order
di erential equation
Ai00 (x) = x Ai(x);

14
subje t to the ondition
e 3 x3=2
2

Ai(x)  p
2 x1=4
as x ! 1:

Let u(x) denote the unique solution to the nonlinear third order equation
u00 (x) = 2u(x)3 + xu(x); (6)
subje t to the ondition
u(x)  Ai(x); as x ! 1:
Equation (6) is known as the Painleve II equation, after Paul Painleve (1863{
1933)2. Painleve ompletely lassi ed di erential equations (from a ertain
lass of se ond order equations) whose \bad" singularities (bran h points and
essential singularities) were independent of the initial onditions. Most of the
equations in this lass were already known, but a few were new, in luding
equation (6).
Now de ne the Tra y-Widom distribution to be the probability distribu-
tion on R given by
 Z 1 
F (t) = exp (x t)u(x) dx :
2
(7)
t
It is Reasily seen that F (t) is indeed a probability distribution, i.e., F (t)  0
and 11 F (t)dt = 1. Let  be a random variable with distribution F , and
let n be the random variable on Sn de ned by
is (w) 2 n
p
n (w) = n 1=6 :
n
We an now state the remarkable results of Baik, Deift, and Johansson.
Theorem. As n ! 1, we have
n !  in distribution;
2 Inaddition to being a distinguished mathemati ian, in 1908 Painleve was the rst
passenger of Wilbur Wright, during whi h they set a ight duration re ord of 70 minutes,
and in 1917 and 1925 he held a position equivalent to Prime Minister of Fran e.

15
i.e., for all t 2 R ,
lim Prob(n  t) = F (t):
n!1

Theorem. For any m = 0; 1; 2; : : :,

lim E (m
n!1
m
n ) = E ( ):

Corollary. We have
Z Z 2
Var(isn )
lim
n!1 n1=3
= t2 dF (t) t dF (t)
= 0:8132


;
where Var denotes varian e, and
p
E (isn ) 2 n
Z
lim = t dF (t) (8)
n!1 n1=6
= 1:7711


:
The above theorems are a vast re nement of the Vershik-Kerov and Logan-
Shepp results on erning E (n), the expe tation of isn (w). The rst theorem
gives the entire limiting distribution (as n ! 1) of isn (w), while the se -
ond theorem gives an asymptoti formula for the mth moment. Note that
equation (8) may be rewritten
p
E (n) = 2 n + n1=6 + o n1=6 ;

R
where = t dF (t), thereby giving the se ond term in the asymptoti be-
havior of E (n).
We will say only a brief word on the proof of the above results, explaining
how ombinatori s enters into the pi ture. Some kind of analyti expression
is needed for the distribution of isn (w). Su h an expression is provided by
the following result of Ira Gessel [14℄, later proved in other ways by various
persons.
Theorem. Let
uk (n) = #fw 2 Sn : isn (w)  kg

16
 X x2n
Uk (x) = uk (n)
n0
n!2
X x2n+i
Bi (x) = :
n0
n! (n + i)!
Then
k
Uk (x) = det Bji j j(x) i;j =1 :

Example. We have

U2 (x) = B0 (x) B1 (x)

B1 (x) B0 (x)
= B0 (x)2 B1 (x)2 :
From this it is easy to dedu e that
 
1 2n
u2 (n) = ;
n+1 n
a Catalan number. This result was rst stated by John Mi hael Hammersley
in 1972, with the rst published proofs by Knuth [25, x5.1.4℄ and Rotem [33℄.
There is a more ompli ated expression for u3 (n) due to Gessel [14, x7℄[37,
Exer. 7.16(e)℄, namely,
n    
1 X 2j n+1 n+2
u3 (n) = ;
(n + 1) (n + 2) j =0 j
2
j+1 j+2
while no \ni e" formula for uk (n) is known for xed k > 3.
Gessel's theorem redu es the theorems of Baik, Deift, and Johansson to
\just" analysis, viz., the Riemann-Hilbert problem in the theory of integrable
systems, followed by the method of steepest des ent to analyze the asymp-
toti behavior of integrable systems. For further information see the survey
[6℄ of Deift mentioned above.
The asymptoti behavior of isn (w) (suitably s aled) turned out to be
identi al to the Tra y-Widom distribution F (t) of equation (7). It is natural
to ask how the Tra y-Widom distribution arose in the rst pla e. It seems

17
surprising that su h an \unnatural" looking fun tion as F (t) ould have
arisen independently in two di erent ontexts. Originally the Tra y-Widom
distribution arose in onne tion with the Gaussian Unitary Ensemble (GUE).
GUE is a ertain natural probability distribution on the spa e of all n  n
hermitian matri es M = (Mij ), namely,
Zn 1 e tr( M 2 ) dM;

where Zn is a normalization onstant and

Y Y
dM = dMii
d(Re Mij )d(Im Mij ):
i i<j

Let the eigenvalues of M be 1  2 


 n . The following result

marked the eponymous appearan e [39℄ of the Tra y-Widom distribution:
 p  p 
lim Prob
n!1 1 2n 2n1=6  t = F (t): (9)

Thus as n ! 1, isn (w) and 1 have the same distribution (after s aling).
It is natural to ask, rstly, whether there is a result analogous to equa-
tion (9) for the other eigenvalues k of the GUE matrix M , and, se ondly,
whether there is some onne tion between su h a result and the behavior
of in reasing subsequen es of random permutations. A generalization of (9)
was given by Tra y and Widom [39℄ (expressed in terms of the Painleve II
fun tion u(x)). The onne tion with in reasing subsequen es was onje -
tured in [1℄ and proved independently by Borodin-Okounkov-Olshanski [4℄,
Johannson [23℄, and Okounkov [32℄. Given w 2 Sn, de ne integers 1 ; 2 ; : : :
by letting 1 +


+ k be the largest number of elements in the union of k
in reasing subsequen es of w. For instan e, let w = 247951368. The longest
in reasing subsequen e is 24568, so 1 = 5. The largest union of two in reas-
ing subsequen es is 24791368 (the union of 2479 and 1368), so 1 + 2 = 8.
(Note that it is impossible to nd a union of length 8 of two in reasing subse-
quen es that ontains an in reasing subsequen e of length 1 = 5.) Finally w
itself is the union of the three in reasing subsequen es 2479, 1368, and 5, so
1 + 2 + 3 = 9. Hen e (1 ; 2 ; 3 ) = (5; 3; 1) (and i = 0 for i > 3). Read-
ers familiar with the theory of the Robinson-S hensted-Knuth algorithm will
re ognize the sequen e (1 ; 2 ; : : :) as the shape of the two standard Young
tableaux obtained by applying this algorithm to w, a well-known result of

18
Curtis Greene [15℄[37, Thm. A1.1.1℄. (In parti ular, 1  2 


, a fa t
whi h is by no means obvious.) The result of [4℄[23℄[32℄ asserts that as as
n ! 1, k and k are equidistributed, up to s aling.
The Tra y-Widom distribution arose ompletely independently in the be-
haviour of isn (w) and GUE matri es. Is this onne tion just a oin iden e?
The work of Okounkov [32℄ provides a onne tion, via the theory of random
topologies on surfa es.

19
Referen es

[1℄ J. Baik, P. Deift, and K. Johansson, On the distribution of the length of

the longest in reasing subsequen e of random permutations, J. Amer.
Math. So . 12 (1999), 1119{1178, [Link]/98101053 .
[2℄ A. Berenstein and A. Zelevinsky, Triple multipli ities for sl(r + 1) and
the spe trum of the exterior algebra of the adjoint representation, J.
Algebrai Combinatori s 1 (1992), 7{22.
[3℄ F. Bergeron, A. Garsia, and G. Tesler, Multiple left regular representa-
tions generated by alternants, J. Combinatorial Theory (A) 91 (2000),
49{83.
[4℄ A. Borodin, A. Okounkov, and G. Olshanski, Asymptoti s of Plan herel
measures for symmetri groups, J. Amer. Math. So . 13 (2000), 481{
515, [Link]/9905032.
[5℄ A. Bu h, The saturation onje ture (after A. Knutson and T. Tao),
Enseign. Math. 46 (2000), 43{60, [Link]/9810180.
[6℄ P. Deift, Integrable systems and ombinatorial theory, Noti es Amer.
Math. So . 47 (2000), 631{640.
[7℄ H. Derksen and J. Weyman, Semi-invariants of quivers and saturation
for Littlewood-Ri hardson oeÆ ients, J. Amer. Math. So . 13 (2000),
467{479.
[8℄ W. Fulton, Young Tableaux, London Mathemati al So iety Student
Texts 35, Cambridge University Press, Cambridge, 1997.
[9℄ W. Fulton, Eigenvalues, invariant fa tors, highest weights, and S hubert
al ulus, Bull. Amer. Math. So . 37 (2000), 209{249, [Link]/9908012.
[10℄ A. M. Garsia and J. Haglund, A proof of the q; t-Catalan positivity on-
je ture, Dis rete Math., to appear, [Link]/jhaglund.
[11℄ A. M. Garsia and M. Haiman, A remarkable q; t-Catalan sequen e and
q -Lagrange inversion, J. Algebrai Combin. 5 (1996), 191{244.
3 [Link], [Link], [Link] and hep-th refer to se tions of the LANL preprint
ar hive [Link].

20
[12℄ A. M. Garsia and M. Haiman, A graded representation model for Ma -
donald's polynomials, Pro . Nat. A ad. S i. U.S.A. 90 (1993), 36-7{
3610.
[13℄ A. M. Garsia and M. Haiman, Some natural bigraded Sn -modules and
q; t-Kostka oeÆ ients, Ele tron. J. Combin. 3 (1996), RP24.
[14℄ I. Gessel, Symmetri fun tions and P-re ursiveness, J. Combinatorial
Theory (A) 53 (1990), 257{285.
[15℄ C. Greene, An extension of S hensted's theorem, Advan es in Math. 14
(1974), 254-265.
[16℄ J. Haglund, Conje tured statisti s for the q; t-Catalan numbers, Ad-
van es in Math., to appear, [Link]/jhaglund.
[17℄ M. Haiman, Ma donald polynomials and geometry, in New perspe tives
in algebrai ombinatori s (Berkeley, CA, 1996{97) (L. J. Billera, et
al., eds.), MSRI Publ. 38, Cambridge Univ. Press, Cambridge, 1999,
pp. 207-254.
[18℄ M. Haiman, Hilbert s hemes, polygraphs, and the Ma donald
positivity onje ture, J. Amer. Math. So . 14 (2001), 941{1006,
www/[Link]/mhaiman.
[19℄ M. Haiman, Vanishing theorems and hara ter formulas for
the Hilbert s heme of points in the plane, preliminary draft,
www/[Link]/mhaiman; abbreviated version in Physi s
and Combinatori s (A. N. Kirillov and N. Liskova, eds.), World S i-
enti , London, 2001, pp. 1{21.
[20℄ P. Hall, The algebra of partitions, in Pro . 4th Canadian Math. Congress
(Ban ), 1959, pp. 147{159.
[21℄ J. M. Hammersley, A few seedlings of resear h, in Pro . Sixth Berkeley
Symposium on Mathemati al Statisti s and Probability, vol. 1, University
of California Press, Berkeley/Los Angeles, 1972, pp. 345{394.
[22℄ G. J. He kman, Proje tions of orbits and asymptoti behavior of mul-
tipli ities for ompa t onne ted Lie groups, Invent. Math. 67 (1982),
333{356.

21
[23℄ K. Johansson, Dis rete orthogonal polynomial ensembles and the
Plan erel measure, Ann. Math. 153 (2001), 259{296, [Link]/9906120.
[24℄ A. A. Klya hko, Stable bundles, representation theory and Hermitian
operators, Sele ta Math. 4 (1998), 419{445.
[25℄ D. E. Knuth, The Art of Computer Programming, vol. 3, Sorting and
Sear hing, Addison-Wesley, Reading, Massa husetts, 1973; se ond edi-
tion, 1998.
[26℄ A. Knutson and T. Tao, The honey omb model of GLn (C ) tensor prod-
u ts I: proof of the saturation onje ture, J. Amer. Math. So . 12 (1999),
1055{1090, [Link]/9807160.
[27℄ A. Knutson and T. Tao, Honey ombs and sums of Hermitian matri es,
Noti es Amer. Math. So . 48 (2001), 175{186, [Link]/0009048.
[28℄ B. F. Logan and L. A. Shepp, A variational problem for random Young
tableaux, Advan es in Math. 26 (1977), 206{222.
[29℄ I. G. Ma donald, A new lass of symmetri fun tions, A tes 20e
Seminaire Lotharingien, Publ. I.R.M.A., Strasbourg, 1992, pp. 5{39.
[30℄ I. G. Ma donald, Symmetri Fun tions and Hall Polynomials, se ond
ed., Oxford University Press, Oxford, 1995.
[31℄ F. M. Maley, The Hall polynomial revisited, J. Algebra 184 (1996),
363{371.
[32℄ A. Okounkov, Random matri es and random permutations, Internat.
Math. Res. Noti es 2000, 1043{1095, [Link]/9903176.
[33℄ D. Rotem, On a orresponden e between binary trees and a ertain type
of permutation, Inf. Pro . Letters 4 (1975/76), 58{61.
[34℄ C. E. S hensted, Longest in reasing and de reasing subsequen es,
Canad. J. Math. 13 (1961), 179{191.
[35℄ L. Smith, Polynomial Invariants of Finite Groups, A K Peters, Wellesley,
Massa husetts, 1995.

22
[36℄ R. Stanley, Invariants of nite groups and their appli ations to ombi-
natori s, Bull. Amer. Math. So . (new series) 1 (1979), 475{511.
[37℄ R. Stanley, Enumerative Combinatori s, vol. 2, Cambridge University
Press, Cambridge, 1999.
[38℄ G. Tesler, Semi-primary latti es and tableaux algorithms, Ph.D. thesis,
M.I.T., 1995.
[39℄ C. A. Tra y and H. Widom, Level-spa ing distributions and the Airy
kernel, Comm. Math. Phys. 159 (1994), 151{174, hep-th/9211141.
[40℄ A. M. Vershik and S. V. Kerov, Asymptoti behavior of the Plan herel
measure of the symmetri group and the limit form of Young tableaux,
Dokl. Akad. Nauk SSSR 233 (1977), 1024{1027. English translation in
Soviet Math. Dokl. 18 (1977), 527{531.
[41℄ A. Zelevinsky, Littlewood-Ri hardson semigroups, in New perspe tives
in algebrai ombinatori s (Berkeley, CA, 1996{97) (L. J. Billera, et
al., eds.), MSRI Publ. 38, Cambridge Univ. Press, Cambridge, 1999,
pp. 337{345, [Link]/9704228.

23