Tags: #theorem

Statement

Let $w$ be a permutation and $\lambda$ be its Schensted shape. Then, ${\lambda }_1$ is the length of the longest increasing subsequence of $w$.

Proof

For each $i$, let $B_i$ for $i=1,\dots ,{\lambda }_1$ be the entries of $w$ that were originally inserted by the Schensted insertion algorithm in the $i$th column of the first row. (this will happen to look like the $i$th columns of the resulting $P$ tableaux read from bottom to up).

For example, if we had $w=3,5,2,4,7,1,6$, then
$B_1=\{3,2,1\}$
$B_2=\{5,4\}$
$B_3=\{7,6\}$

We make two observations:

1. The entries of each $B_i$ are decreasing
   1. This is because every time we add something to bump an entry in the first row down, we are adding something that is smaller than whatever we bumped
2. For all $i\ge 2$ and $x\in B_i$, there exists a $y\in B_{i-1}$ such that $y<x$ and $y$ is to the left of $x$ in $w$
   1. When we insert $x$ (into the first row), we can take $y$ to be the entry to the left of $x$

Then, we can start with some $x\in B_{\lambda }$ and then iteratively apply observation 2 to build a sequence of length ${\lambda }_1$ that is increasing.

To show that this is the longest increasing subsequence, we note that if we pick more than ${\lambda }_1$ elements, we would have to pick two from the same $B_i$, but the elements of $B_i$ are decreasing by (1), so this cannot happen.