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

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.