Recall the definition of skew Young tableaux and their Schur functions and . When , we get the usual Schur functions .The reason we consider skew tableaux is
- they are related to skew characters of to be discussed later.
- the argument for symmetry goes through easily for the skew case as well.
Proposition 1 is symmetric.
Proof: Recall the definition
Let be the type of a SSYT of shape and be with two entries switched. be the set of SSYT of with type . It would suffice to find a bijection between and , since adjacent transpositions generate and switching and in is equivalent to switching the number of SSYTs of type and . The bijection is defined as following: take any . Delete all the columns of with both and . For the remaining filled in diagram, each row consist of a bunch of ‘s and ‘s, say row has ‘s and ‘s. The in the spaces occupied by ‘s and ‘s in row , fill in the first spaces with ‘s and the last spaces with ‘s, i.e., switching the number of ‘s and ‘s, while preserving the weak increasingness. The resulting diagram when combined with the deleted columns will still be a valid SSYT for , and clearly is of type , hence defines a bijection.
Definition 2 The Kostka numbers are the change of basis coefficients from skew-Schur to monomial. Clearly
where is any SSYT of with type , viewed as a partition .
By definition of Schur function in terms of the ,’s, the number of SSYT of shape and type .
Proposition 3 If , , then in dominance ordering.
Norbert Wiener proved this when he was 16, but it’s not hard. Proof: The assumption implies the existence of some SSYT of shape type . Then
- T has 1’s, all of which must fit in the first row of .
- 1’s and 2’s all fit in the first 2 rows of .
The claim follows from the definition of dominance relation.
From the above proof, is also clear. Thus
i.e., under any total refinement of the dominance ordering, is unipotent lower triangular.
Corollary 4 is a -basis for , because the change of basis equations are monic.
As a remark, computing is -P complete. But some special cases can be computed:
- is anything, , then , the dimension of the irrep of associated with .
- anything, , .
Proposition 5 (Sketched inline item 2) enumerates
- saturated paths in patitions from to . Proof follows from the item below.
- Ballot sequences: suppose we have candidates in an election, votes for in the end, . How many ways can these be drawn so that candidate is never behind ? This number is , where . If , it specializes to the Catalan number . Finally if is a Ballot sequence, we can build SYT by placing in row if : eg., . We use the latter notation to denote Young tableau with two rows: first row being 123, second being 45. Thus we have a bijection between the Ballot sequence and Young tableaux with type (hence a proof).
- Lattice paths in , where is the number of parts of . Of course this is just a restatement of item 1.
There is a version of Kolmogorov Smirnov statistics defined in terms of . Next we talk about one of the big topics in the course: Robinson-Schensted-Knuth algorithm. Patience sorting: a toy version of Solitaire (whose winning probability is not computed). Take a well-shuffled deck of cards. Turn the cards up one at a time:
- play low card or high card
- if turn up higher than any showing, start a new pick
- objective is to have as few piles as possible
Greedy algorithm is to put each card in the left most possible pile. Then For , let the length of the longest increasing subsequence of . then
- Any strategy of patience sorting on the deck has at least piles.
- Greedy achieves this.
Proof: The first point is clear, since the cards in any increasing subsequence must be on different piles by the rule of the game. To show that greedy is good, let be the pile card is in. Define for each card a pointer function the last card to be placed on pile before is placed on . is undefined on cards in the first pile (but it’s ok). Now start at any card in the last pile . Then it’s predecesor , because otherwise one could put card on top of in pile . Continuing, we get an increasing subsequence in reverse order .
In fact Patience sorting is provably the fastest algorithm for computing . We also have , where is a metric on (found in Knuth vol III), given by the minimum number of deletion and insertion moves needed to go from to , i.e., pairwise rotation. Motivation: Pick at random, what is the distribution of ? Ulam’s problem: . proved by Virshick-Kerov, and Logam-Shepp (1979)
where satisfies the Painleve II ODE
with as , where is the Airy function. Baik-Deift-Johansson have shown that the largest eigenvalue of GUE properly normalized also converges to , the Tracy-Widom distribution.