In mathematics, the Robinson–Schensted correspondence is a bijective correspondence between permutations and pairs of standard Young tableaux of the same shape. It has various descriptions, all of which are of algorithmic nature, it has many remarkable properties, and it has applications in combinatorics and other areas such as representation theory. The correspondence has been generalized in numerous ways, notably by Knuth to what is known as the Robinson–Schensted–Knuth correspondence, and a further generalization to pictures by Zelevinsky.
The simplest description of the correspondence is using the Schensted algorithm, a procedure that constructs one tableau by successively inserting the values of the permutation according to a specific rule, while the other tableau records the evolution of the shape during construction. The correspondence had been described, in a rather different form, much earlier by Robinson, in an attempt to prove the Littlewood–Richardson rule. The correspondence is often referred to as the Robinson–Schensted algorithm, although the procedure used by Robinson is radically different from the Schensted algorithm, and almost entirely forgotten. Other methods of defining the correspondence include a nondeterministic algorithm in terms of jeu de taquin.
The bijective nature of the correspondence relates it to the enumerative identity
\sumλ\inl{Pn}
| 2= | |
| (t | |
| λ) |
n!
where
l{P}n
The Schensted algorithm starts from the permutation written in two-line notation
\sigma=\begin{pmatrix}1&2&3& … &n\ \sigma1&\sigma2&\sigma3& … &\sigman\end{pmatrix}
where, and proceeds by constructing sequentially a sequence of (intermediate) ordered pairs of Young tableaux of the same shape:
(P0,Q0),(P1,Q1),\ldots,(Pn,Qn),
where are empty tableaux. The output tableaux are and . Once is constructed, one forms by inserting into, and then by adding an entry to in the square added to the shape by the insertion (so that and have equal shapes for all). Because of the more passive role of the tableaux, the final one, which is part of the output and from which the previous are easily read off, is called the recording tableau; by contrast the tableaux are called insertion tableaux.
The basic procedure used to insert each is called Schensted insertion or row-insertion (to distinguish it from a variant procedure called column-insertion). Its simplest form is defined in terms of "incomplete standard tableaux": like standard tableaux they have distinct entries, forming increasing rows and columns, but some values (still to be inserted) may be absent as entries. The procedure takes as arguments such a tableau and a value not present as entry of ; it produces as output a new tableau denoted and a square by which its shape has grown. The value appears in the first row of, either having been added at the end (if no entries larger than were present), or otherwise replacing the first entry in the first row of . In the former case is the square where is added, and the insertion is completed; in the latter case the replaced entry is similarly inserted into the second row of, and so on, until at some step the first case applies (which certainly happens if an empty row of is reached).
More formally, the following pseudocode describes the row-insertion of a new value into .[1]
The shape of grows by exactly one square, namely .
The fact that has increasing rows and columns, if the same holds for, is not obvious from this procedure (entries in the same column are never even compared). It can however be seen as follows. At all times except immediately after step 4, the square is either empty in or holds a value greater than ; step 5 re-establishes this property because now is the square immediately below the one that originally contained in . Thus the effect of the replacement in step 4 on the value is to make it smaller; in particular it cannot become greater than its right or lower neighbours. On the other hand the new value is not less than its left neighbour (if present) either, as is ensured by the comparison that just made step 2 terminate. Finally to see that the new value is larger than its upper neighbour if present, observe that holds after step 5, and that decreasing in step 2 only decreases the corresponding value .
The full Schensted algorithm applied to a permutation proceeds as follows.
The algorithm produces a pair of standard Young tableaux.
It can be seen that given any pair of standard Young tableaux of the same shape, there is an inverse procedure that produces a permutation that will give rise to by the Schensted algorithm. It essentially consists of tracing steps of the algorithm backwards, each time using an entry of to find the square where the inverse insertion should start, moving the corresponding entry of to the preceding row, and continuing upwards through the rows until an entry of the first row is replaced, which is the value inserted at the corresponding step of the construction algorithm. These two inverse algorithms define a bijective correspondence between permutations of on one side, and pairs of standard Young tableaux of equal shape and containing squares on the other side.
One of the most fundamental properties, but not evident from the algorithmic construction, is symmetry:
This can be proven, for instance, by appealing to Viennot's geometric construction.
Further properties, all assuming that the correspondence associates tableaux to the permutation .
The Robinson-Schensted correspondence can be used to give a simple proof of the Erdős–Szekeres theorem.
. James Alexander Green . Polynomial representations of GLn . With an appendix on Schensted correspondence and Littelmann paths by K. Erdmann, J. A. Green and M. Schocker . 2nd corrected and augmented . 1108.20044 . Lecture Notes in Mathematics . 830 . Berlin . . 3-540-46944-3 . 2007 .