Lemma 6 do not change under Knuth moves.
- and are related by , where if , then . This follows fromm the definition of .Therefore if and only if .
- Fix , suppose the lemma is false. Say . After a Knuth move of , we arrive at , and have without loss of generality.
Claim: For any increasing subsequences in , , the fact implies that , and for some . Now after the Knuth move switching and , we can still fit all three symbols into the union of two increasing subsequences by combining the part before in with the part after in and vice versa, i.e. a cross breeding of the two subsequences. (See Fomin’s appendix of Stanley volume 2 for more detail)
Given a standard Young tableau, e.g.
the reading of is given by .
Lemma 7 Any is Knuth equivalent to the reading word of the insertion tableau.
Proof: It is enough to show that if is some partial Young tableau and , then
For this it is enough to consider the insertion operation for one row. For example, if , ,
From the fact that Knuth moves don’t change ‘s, we arrive at
Corollary 8 and have the same for all .
Lemma 9 Let , then .
Proof: For a permutation sequence arising from the reading of a standard Young tableau, the insertion procedure of RSK algorithm applied to it simply places the rows (which are increasing subsequences) on top of each other, because they displace the previous top rows in a systematic left to right way. Thus the proof is by inspection.
Proof: (of Greene’s theorem; for statement see the end of previous lecture) We may assume by the above corollary and lemma that , for some .
- the rows of give increasing subsequences of , so .
- the columns of T gives decreasing subsequences, .
- Consider a box on the rim of . For example
the boxes on the rim are . Say the box we chose is in position e.g. in the numerical example above. Then
- an increasing subsequence and a decreasing subsequence can intersect in at most one place. Thus . For example, the case is intuitively clear. thus for all on the rim. Therefore
since for every , there is some such that is on the rim, this proves the theorem.
Corollary 10 (Easy) is consant on Knuth classes.
Theorem 11 if and only if .
Proof: Fix k, let be the subpermutation of using . For example, if , then , . Let be insertion tableau for , insertion tableau for . Because don’t affect , is just subtableau with . Take .
Crucial observation: any Knuth move either doesn’t change or is a Knuth move on . Since a tableau is uniquely determined by a sequence of shapes
and all shapes are unchanged by Knuth moves, we have .
Jeu de Taquin, evacuation:
Motivation: consider . What about ?
Theorem 12 . Here is an involution, has the same shape obviously.
Here comes Jeu de Taquin on . Removing top left corner and slide the small one in
Play the sequence backward and label the th newly added position by (i.e., a bookkeeping tableau), we get the standard Young tableau :
As a corollary, if , and , then