§ RSK correspondence for permutations

§ Tableaux

Tableaux of size nn first needs a partition of size nn in decreasing order. Write it as λ\lambda, such that λ[i]0\lambda[i] \geq 0 and iλ[i]=n\sum_i \lambda[i] = n and λ[i]\lambda[i] is weakly decreasing: λ[1]lambda[2]lambda[n]\lambda[1] \geq lambda[2] \geq lambda[n]. For example, a partition of 99 is 4,2,2,14, 2, 2, 1. This is drawn as:
* * * *
* *
* *
*
Next, we fill the tableau with numbers from [n]{1,,n}[n] \equiv \{1,\dots,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 TT. Can we add an element xx into it such that T=ins(T,x)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 TT. Can we delete a location (i,j)(i, j), such that we get a smaller tableau TT', and an element xx such that ins(T,x)=Tins(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)(i, j). Rather, we change the shape of the tableau to lose the cell (i,j)(i, j). consider the tableau:
1
2
3
If we ask to delete the cell (r=1,c=3)(r=1,c=3) (that is, the cell containing 33), we will be left with the tableau:
2
3
and the element 11. So, when we insert 11 into [2;3][2; 3] we get [1;2;3][1; 2; 3]. We did not get
1
2
and the element 33. This is because if we insert 33 into [1;2][1;2], then we get the tableau [1,3;2][1,3;2]:
1 3
2

§ Bijection between permutations and pairs of standard tableau

Given a permutation p:[n][n]p: [n] \rightarrow [n], we define two tableau corresponding to it: the insertion tableau PP and the recording tableau QQ. Informally, the insertion tableau is obtained by inserting p[1],p[2],,p[n]p[1], p[2], \dots, p[n] in sequence into an empty tableau. The recording tableau at step ii records where the number ii was stored in the tableau. So the recording tableau at step ii, QiQ_i has the same shape as the insertion tableau at step ii, PiP_i, and contains the value ii at the cell where ii was stored in PP. That is, Pi[Qi[i]]=iP_i[Q_i[i]] = i.

§ Properties of the insertion and recording tableau

We consider the set of points (i,p(i))(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))(i, p(i)), imagine a rectangle with (i,p(i))(i, p(i)) as the lower left corner. Next, shine a flashlight from the point (0,0)(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)xpyq(x, y) \lhd (p, q) \equiv x \leq p \land y \leq q. Then, we get the "points on the shadow lines" by considering the Hasse diagram of the points (i,p(i))(i, p(i)) under the relationship \lhd. 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 xx-coordinate. These points will form a chain. This chain will be first row of the permutation tableau PP. Funnily enough, it is also one of the longest increasing subsequences of the sequence ip(i)i \mapsto 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 \lhd

Note that \lhd as a relation is symmetric in xx and yy. Thus, any order theoretic result we prove for xx will hold for yy. But note that (i,p(i))(i, p(i)) is the permutation pp, while (p(i),i)(p(i), i) is the inverse permutation (p1)(p^{-1}). Thus, we should expect a "duality" between the order theoretic properties of PP and p1p^{-1}.