§ RSK correspondence for permutations
Tableaux of size first needs a partition of size in decreasing
order. Write it as , such that and
and is weakly decreasing: .
For example, a partition of is . This is drawn as:
Next, we fill the tableau with numbers from 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:
* * * *
(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).
1 3 4 6
Say we start with some tableau . Can we add an element into it such that
is a valid tableau? Yes, and this process is called insertion.
This is the reverse of insertion. Say we start with a tableau . Can we delete
a location , such that we get a smaller tableau , and an element
such that ? Yes we can, and this process is called deletion.
§ Misoncentions about deletion
Deletion does not mean that we lose the value at . Rather, we
change the shape of the tableau to lose the cell . consider
If we ask to delete the cell (that is, the cell containing ),
we will be left with the tableau:
and the element . So, when we insert into we get .
We did not get
and the element . This is because if we insert into , then we
get the tableau :
§ Bijection between permutations and pairs of standard tableau
Given a permutation , we define two tableau
corresponding to it: the insertion tableau and the recording tableau .
Informally, the insertion tableau is obtained by inserting
in sequence into an empty tableau. The recording tableau at step records
where the number was stored in the tableau. So the recording tableau
at step , has the same shape as the insertion tableau at step ,
, and contains the value at the cell where was stored in .
That is, .
§ Properties of the insertion and recording tableau
We consider the set of points . 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 , imagine a rectangle with as the lower left
corner. Next, shine a flashlight from the point towards the upper right
quadrant; the boundary that is cast by the rectangles are called as the
Formally, we consider a dominance relationship where .
Then, we get the "points on the shadow lines" by considering the Hasse diagram
of the points 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 -coordinate.
These points will form a chain. This chain will be first row of
the permutation tableau .
Funnily enough, it is also one of the longest increasing subsequences of the
sequence 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 and . Thus, any order
theoretic result we prove for will hold for . But note that
is the permutation , while is the inverse permutation .
Thus, we should expect a "duality" between the order theoretic properties of