Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 103 / 6

A near Young tableau is a filling of a Young diagram by distinct entries from a totally ordered alphabet, increasing along rows and down columns; the entries need not be $1,\dots ,n$. For row insertion of $x$, scan the first row for its leftmost entry larger than $x$. If one exists, replace it by $x$ and insert the displaced entry into the next row by the same rule. Otherwise append $x$ to the row and stop. Continue until a new outer-corner box is appended.

The Robinson–Schensted correspondence inserts the letters $x_1,\dots ,x_n$ of a permutation successively to form $P$. Whenever the $k$th insertion creates a new cell, put $k$ in that cell of a second tableau $Q$. Row insertion preserves increasing rows and columns, so $P$ is standard; the sequence of growing diagrams makes $Q$ standard, with the same shape. To reverse the construction, remove the box carrying the largest label in $Q$, and reverse the bumping in $P$: in each row above, exchange the carried entry with the rightmost smaller entry, continuing up to the first row. The final expelled entry is the last letter of the permutation. Repeating recovers the whole permutation, establishing the bijection with pairs of standard Young tableaux of a common shape.

For the bumping inequality, each displaced entry is the first entry strictly larger than the incoming one. Thus every step replaces a larger entry with a smaller entry and carries that larger value downwards. Consequently the bumped values strictly increase:

Suppose an entry $y$ is bumped from column $j$ of row $i$. If row $i+1$ already contains a cell in column $j$, its entry is greater than $y$ by the strict column condition in the original near Young tableau. When $y$ is inserted into that row, the first entry greater than $y$ therefore occurs in a column at most $j$.

If the next row is shorter than $j$, either a bump occurs earlier or $y$ is appended in column ${\lambda }_{i+1}+1\le j$. This also handles the final appended box. Each successive bumping position is therefore weakly to the left of the previous one. The bumping columns satisfyThis is the row-insertion bumping-path monotonicity needed to preserve the Young-diagram shape and column order.

Every old box either remains untouched or has its entry replaced by a strictly smaller incoming value. Thus on all boxes of the original diagram,The appended box has no old entry to compare; equivalently, extend the old filling by $+\infty$ outside its diagram if the inequality is to be written for every position.

We now prove the unheaded longest increasing subsequence assertion. After any prefix of the permutation has been inserted, write the first-row entries as $b_1<\cdots <b_r$. The useful invariant is: $b_j$ is the smallest possible final value of an increasing subsequence of length $j$ in that prefix, and $r$ is the greatest possible subsequence length. It holds for the empty prefix.

Suppose the next letter $x$ enters the first row in column $j$. Then $b_{j-1}<x$, if $j>1$, while $b_j>x$ if column $j$ already exists. A subsequence of length $j-1$ ending at $b_{j-1}$ can be extended by $x$, giving a subsequence ending at $x$ of length $j$; for $j=1$, the singleton suffices. A longer subsequence ending at $x$ would have an earlier length-$j$ prefix ending below $x$, contradicting the minimality of $b_j$. If $j=r+1$, the previous prefix has no subsequence longer than $r$, giving the same upper bound.

Replacing $b_j$ by $x$, or appending it at $j=r+1$, preserves the invariant. It lowers the smallest final value at length $j$. At smaller lengths, existing minima are already below $x$, so they cannot improve; no subsequence of greater length can end at $x$. The lower rows do not change this first-row update. Induction proves that the longest increasing subsequence ending in $x_k$ has length exactly the column in which $x_k$ first enters.

Taking the maximum over all letters gives Schensted's first-row theorem:This concerns the column of the incoming letter in the first row, not the column of the new box that eventually appears at the end of the bumping path.

A generalised permutation is a finite multiset of pairs $(a,b)$ from two ordered alphabets, written as a two-row array, or biword. It may equivalently be specified by a finite-support matrix of nonnegative integer multiplicities $m_{a,b}$. The condition that no column is repeated means $m_{a,b}\in \{0,1\}$: each ordered pair occurs at most once. It does not forbid repeated entries in either individual row.

For this class use the dual Robinson–Schensted–Knuth correspondence. Order the columns by nondecreasing top entry $a$, and by strictly decreasing bottom entry $b$ when the top entries agree. Insert the bottom entries in that order by ordinary semistandard row insertion, which bumps the leftmost entry strictly greater than the incoming entry. Record the corresponding top entry in each newly created cell. Let $T$ be the insertion tableau and $U$ the recording tableau.

Ordinary row insertion permits repeated entries, preserving weak increase along rows and strict increase down columns; therefore $T$ is a semistandard Young tableau. The recording entries are inserted in nondecreasing order, so $U$ weakly increases along both rows and columns before considering strictness. Within one block of equal top entries, the bottom entries are strictly decreasing. The standard row-bumping comparison lemma says that a later, smaller input creates a new box strictly below the box created by the preceding input. Thus the boxes carrying one repeated top entry form a vertical strip, with at most one in each row. Consequently $U$ has strictly increasing rows and weakly increasing columns, so $U^t$ is semistandard.

Knuth's generalized insertion theorem, in this dual ordering, makes the map a bijection between finite $0$-$1$ matrices and these pairs. Its reverse description is also transparent: remove the largest recording entry, choosing its lowest box when it repeats, and reverse row insertion in $T$. Repeating recovers bottom entries in the reverse of the specified ordering. Equal top entries recover distinct bottom entries, which is exactly the no-repeated-column condition. ThusThe descending tie rule matters; the usual ascending tie rule would instead give two ordinary Semistandard Young tableaux.

Finally, the type of a tableau means its entry-multiplicity vector. Row insertion rearranges and bumps entries without changing their multiplicities. HenceThus the bottom-row multiplicities of the generalised permutation give the type of $T$, while the top-row multiplicities give the type of $U$; transposing $U$ does not change its type.