## § 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.
#### § 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] \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}$.