§ RSK correspondence for permutations
§ Tableaux
Tableaux of size n first needs a partition of size n in decreasing
order. Write it as λ, such that λ[i]≥0 and ∑iλ[i]=n
and λ[i] is weakly decreasing: λ[1]≥lambda[2]≥lambda[n].
For example, a partition of 9 is 4,2,2,1. This is drawn as:
* * * *
* *
* *
*
Next, we fill the tableau with numbers from [n]≡{1,…,n} such
that the rows are weakly increasing and columns are strictly increasing
(gravity acts downwards, and we always want to get bigger). These
are called Standard tableay For example,
a valid Standard tableau corresponding to the partition above is:
1 3 4 6
2 5
7 9
8
(Sidenote: here both rows and columns are strictly increasing because we have
unique numbers. If we did not, then by convention, the rows will be weakly
increasing and columns strictly increasing. I always repeat the chant
"rows weakly, columns strictly" to burn it into my brain).
§ Insertion
Say we start with some tableau T. Can we add an element x into it such that
T′=ins(T,x) is a valid tableau? Yes, and this process is called insertion.
§ Deletion
This is the reverse of insertion. Say we start with a tableau T. Can we delete
a location (i,j), such that we get a smaller tableau T′, and an element x
such that ins(T′,x)=T? Yes we can, and this process is called deletion.
§ Misoncentions about deletion
Deletion does not mean that we lose the value at (i,j). Rather, we
change the shape of the tableau to lose the cell (i,j). consider
the tableau:
1
2
3
If we ask to delete the cell (r=1,c=3) (that is, the cell containing 3),
we will be left with the tableau:
2
3
and the element 1. So, when we insert 1 into [2;3] we get [1;2;3].
We did not get
1
2
and the element 3. This is because if we insert 3 into [1;2], then we
get the tableau [1,3;2]:
1 3
2
§ Bijection between permutations and pairs of standard tableau
Given a permutation p:[n]→[n], we define two tableau
corresponding to it: the insertion tableau P and the recording tableau Q.
Informally, the insertion tableau is obtained by inserting p[1],p[2],…,p[n]
in sequence into an empty tableau. The recording tableau at step i records
where the number i was stored in the tableau. So the recording tableau
at step i, Qi has the same shape as the insertion tableau at step i,
Pi, and contains the value i at the cell where i was stored in P.
That is, Pi[Qi[i]]=i.
§ Properties of the insertion and recording tableau
We consider the set of points (i,p(i)). This is called as the
Viennot's geometric construction ,
where we reason about the graph. We will reason about the graph here, but couch
the formal arguments in terms of partial orders to be precise.
At each point (i,p(i)), imagine a rectangle with (i,p(i)) as the lower left
corner. Next, shine a flashlight from the point (0,0) towards the upper right
quadrant; the boundary that is cast by the rectangles are called as the
shadow lines.
Formally, we consider a dominance relationship where (x,y)⊲(p,q)≡x≤p∧y≤q.
Then, we get the "points on the shadow lines" by considering the Hasse diagram
of the points (i,p(i)) under the relationship ⊲. Each level of
the hasse diagram becomes one of the shadow lines. The collection of all of
these shadow lines is called as the first order shadow lines .
Next, for each anti-chain, pick the element with the smallest x-coordinate.
These points will form a chain . This chain will be first row of
the permutation tableau P.
Funnily enough, it is also one of the longest increasing subsequences of the
sequence i↦p(i) because the length of the longest chain (the longest increasing
subsequence) is equal to the number of antichains (the number of shadow lines)
§ Duality theory of ⊲
Note that ⊲ as a relation is symmetric in x and y. Thus, any order
theoretic result we prove for x will hold for y. But note that (i,p(i))
is the permutation p, while (p(i),i) is the inverse permutation (p−1).
Thus, we should expect a "duality" between the order theoretic properties of
P and p−1.