## § RSK correspondence for permutations

#### § Tableaux

Tableaux of size $n$ first needs a partition of size $n$ in decreasing order. Write it as $\lambda$, such that $\lambda[i] \geq 0$ and $\sum_i \lambda[i] = n$ and $\lambda[i]$ is weakly decreasing: $\lambda[1] \geq lambda[2] \geq 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] \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 $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.

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] \rightarrow [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], \dots, 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$, $Q_i$ has the same shape as the insertion tableau at step $i$, $P_i$, and contains the value $i$ at the cell where $i$ was stored in $P$. That is, $P_i[Q_i[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) \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))$ 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 $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 \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 $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}$.