Past exam of the representation Theory of Symmetric Groups course of the University of Oxford / 2011 / 3

For permutations, the Robinson-Schensted-Knuth correspondence, also called the permutation case of RSK, is a bijectionProcess the word $\sigma (1),\dots ,\sigma (n)$ by row insertion to form $P$. To insert a new entry $a$, replace the leftmost entry of the first row larger than $a$ and bump that displaced entry into the next row by the same rule. If a row has no larger entry, append $a$ at its end and stop. Exactly one outer-corner cell is added. Record the current insertion time in that new cell of $Q$.

Rows stay increasing by the choice of the leftmost larger entry. The inequalities between successive bumped entries and the entries above them preserve increasing columns. Successive shapes are Young diagrams, so the recording labels also increase across rows and down columns. Reverse insertion at the corner labelled $n$ in $Q$ recovers the last input entry; repeating it recovers the full permutation, proving bijectivity. The more general RSK correspondence extends this construction to suitable two-line arrays and semistandard tableaux.

Write $\lambda =(a,b)$ with $a\ge b>0$. If the removed corner is in the first row, it must be its last cell, with $a>b$. Remove that entry and output it as $v$; all remaining row and column inequalities persist, and the shape is $(a-1,b)$.

If the corner is the last cell of the second row, remove its value $c$. In the first row find the rightmost entry $d<c$, replace it by $c$, and output $v=d$. Such an entry exists: the first-row cell above the removed corner has smaller value than $c$. The chosen position is therefore at least column $b$.

The new first-row entry exceeds all entries to its left, while every entry to its right is larger than $c$ by the rightmost-choice rule. After deleting the lower corner, no second-row cell remains below the changed position, since that row now has length $b-1$. Thus all column inequalities remain valid too. The resulting shape is $(a,b-1)$, omitting a zero part if $b=1$.The entries remain distinct and increasing along rows and columns, but the missing label is the ejected $v$, not necessarily the original corner value. The resulting tableau is therefore standard on its remaining ordered entry set, the generalized-standard convention in the question.

Let $a$ be the single entry in the second row of $P$. It lies in $\{2,\dots ,n\}$; the first row is all the other entries in increasing order. Consider the adjacent transposition $\sigma =(a-1,a)$, whose word isThe first $a-1$ entries append in increasing order to the first row. At insertion time $a$, the value $a-1$ bumps $a$ into the second row, creating its only cell. Every later entry appends to the first row. Thus the insertion tableau has second-row entry $a$ and all other entries in the first row, precisely $P$.

The recording tableau also has second-row entry $a$, the time of the unique bump, and all other time labels in increasing first-row order. It too is $P$. Bijectivity of the correspondence therefore givesThis includes $n=2,a=2$. It identifies the actual permutation without needing a general theorem about involutions.

This is RSK of an adjacent transposition.

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$, soThis 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.

The invariant is the first row of RSK as a minimum-tail table.