= Solution
Track the first row after any prefix of the input <permutation>. Its $j$th entry is the smallest possible final value of an <increasing subsequence> of <length> $j$ in that prefix. This minimum-tail <invariant> follows inductively from the row-insertion update.
Indeed, when a new value $z$ replaces the first first-row entry larger than it, at position $r$, the previous entry in position $r-1$ is smaller than $z$ when $r>1$. An <increasing subsequence> ending there can be extended by $z$, so $z$ supplies a new attainable tail of <length> $r$. It improves the old length-$r$ <minimum>. The minima for shorter lengths were already smaller than $z$ and remain unchanged; a longer subsequence ending at $z$ is impossible because its previous tail would have to be smaller than $z$, contradicting the choice of $r$. If no first-row entry exceeds $z$, it appends and creates a new longest subsequence. This proves the <invariant> at every step.
In particular, the number of first-row cells is the <maximum> increasing-subsequence <length>. At the final tableau it is $\lambda_1$, so
$$
\boxed{\text{No increasing subsequence of }\sigma\text{ has length }\lambda_1+1.}
$$
This proves the required nonextension assertion, even without requiring the first-row tuple itself to occur as a subsequence.
That occurrence is not automatic for a general <permutation>. For example the word $2,4,3,1$ gives $P$ with rows $(1,3),(2),(4)$. Its first-row tuple $(1,3)$ is not a subsequence of the word, because one occurs after three. The first row collects <minimum> tails for different subsequence lengths; those tails need not come from one common subsequence. If the source's premise is read as an additional hypothesis that the tuple does occur, the preceding maximum-length proof establishes its claimed maximality directly.
\Image[/past-exam-of-the-representation-theory-of-symmetric-groups-course-of-the-university-of-oxford/2011-rsk-examples.png]
{title=Two explicit row-insertion calculations and their recording tableaux}
{description=The upper example is the adjacent transposition exchanging three and four, which gives identical insertion and recording tableaux of shape four plus one. The lower example has first insertion row one, three, although one occurs after three in its input word.}
The <invariant> is the <first row of RSK as a minimum-tail table>.
Back to article page
