§ 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 62 57 98

(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:

123

If we ask to delete the cell $(r=1,c=3)$ (that is, the cell containing $3$), we will be left with the tableau:

23

and the element $1$. So, when we insert $1$ into $[2; 3]$ we get $[1; 2; 3]$.

We did not get

12

and the element $3$. This is because if we insert $3$ into $[1;2]$, then we get the tableau $[1,3;2]$:

1 32

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