Robinson–Schensted correspondence

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 Template:Harvs, 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 Template:Harvs, 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 _{\lambda \in {𝒫}_n}(t_{\lambda }{)}^2=n!$

where ${𝒫}_n$ denotes the set of partitions of Template:Mvar (or of Young diagrams with Template:Mvar squares), and Template:Math denotes the number of standard Young tableaux of shape Template:Mvar.

The Schensted algorithm

The Schensted algorithm starts from the permutation Template:Mvar written in two-line notation

$\sigma =\left(\begin{array}{ccccc}1& 2& 3& \cdots & n\\ {\sigma }_1& {\sigma }_2& {\sigma }_3& \cdots & {\sigma }_n\end{array}\right)$

where Template:Math, and proceeds by constructing sequentially a sequence of (intermediate) ordered pairs of Young tableaux of the same shape:

$(P_0,Q_0),(P_1,Q_1),\dots ,(P_n,Q_n),$

where Template:Math are empty tableaux. The output tableaux are Template:Math and Template:Math. Once Template:Math is constructed, one forms Template:Math by inserting Template:Math into Template:Math, and then Template:Math by adding an entry Template:Mvar to Template:Math in the square added to the shape by the insertion (so that Template:Math and Template:Math have equal shapes for all Template:Mvar). Because of the more passive role of the tableaux Template:Math, the final one Template:Math, which is part of the output and from which the previous Template:Math are easily read off, is called the recording tableau; by contrast the tableaux Template:Math are called insertion tableaux.

Insertion

Insertion of (4):
• (4) replaces (5) in the first row
• (5) replaces (8) in the second row
• (8) creates the third row

The basic procedure used to insert each Template:Math 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 Template:Mvar and a value Template:Mvar not present as entry of Template:Mvar; it produces as output a new tableau denoted Template:Math and a square Template:Mvar by which its shape has grown. The value Template:Mvar appears in the first row of Template:Math, either having been added at the end (if no entries larger than Template:Mvar were present), or otherwise replacing the first entry Template:Math in the first row of Template:Mvar. In the former case Template:Mvar is the square where Template:Mvar is added, and the insertion is completed; in the latter case the replaced entry Template:Mvar is similarly inserted into the second row of Template:Mvar, and so on, until at some step the first case applies (which certainly happens if an empty row of Template:Mvar is reached).

More formally, the following pseudocode describes the row-insertion of a new value Template:Mvar into Template:Mvar.

1. Set Template:Math and Template:Mvar to one more than the length of the first row of Template:Mvar.
2. While Template:Math and Template:Math, decrease Template:Mvar by 1. (Now Template:Math is the first square in row Template:Mvar with either an entry larger than Template:Mvar in Template:Mvar, or no entry at all.)
3. If the square Template:Math is empty in Template:Mvar, terminate after adding Template:Mvar to Template:Mvar in square Template:Math and setting Template:Math.
4. Swap the values Template:Mvar and Template:Math. (This inserts the old Template:Mvar into row Template:Mvar, and saves the value it replaces for insertion into the next row.)
5. Increase Template:Mvar by 1 and return to step 2.

The shape of Template:Mvar grows by exactly one square, namely Template:Mvar.

Correctness

The fact that Template:Math has increasing rows and columns, if the same holds for Template:Mvar, 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 Template:Math is either empty in Template:Mvar or holds a value greater than Template:Mvar; step 5 re-establishes this property because Template:Math now is the square immediately below the one that originally contained Template:Mvar in Template:Mvar. Thus the effect of the replacement in step 4 on the value Template:Math 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 Template:Math if present, observe that Template:Math holds after step 5, and that decreasing Template:Mvar in step 2 only decreases the corresponding value Template:Math.

Constructing the tableaux

The full Schensted algorithm applied to a permutation Template:Mvar proceeds as follows.

1. Set both Template:Mvar and Template:Mvar to the empty tableau
2. For Template:Mvar increasing from Template:Mvar to Template:Mvar compute Template:Math and the square Template:Mvar by the insertion procedure; then replace Template:Mvar by Template:Math and add the entry Template:Mvar to the tableau Template:Mvar in the square Template:Mvar.
3. Terminate, returning the pair Template:Math.

The algorithm produces a pair of standard Young tableaux.

Invertibility of the construction

It can be seen that given any pair Template:Math of standard Young tableaux of the same shape, there is an inverse procedure that produces a permutation that will give rise to Template:Math by the Schensted algorithm. It essentially consists of tracing steps of the algorithm backwards, each time using an entry of Template:Mvar to find the square where the inverse insertion should start, moving the corresponding entry of Template:Mvar 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 Template:Mvar on one side, and pairs of standard Young tableaux of equal shape and containing Template:Mvar squares on the other side.

Properties

One of the most fundamental properties, but not evident from the algorithmic construction, is symmetry:

• If the Robinson–Schensted correspondence associates tableaux Template:Math to a permutation Template:Mvar, then it associates Template:Math to the inverse permutation Template:Math.

This can be proven, for instance, by appealing to Viennot's geometric construction.

Further properties, all assuming that the correspondence associates tableaux Template:Math to the permutation Template:Math.

• In the pair of tableaux Template:Math associated to the reversed permutation Template:Math, the tableau Template:Math is the transpose of the tableau Template:Mvar, and Template:Math is a tableau determined by Template:Mvar, independently of Template:Mvar (namely the transpose of the tableau obtained from Template:Mvar by the Schützenberger involution).
• The length of the longest increasing subsequence of Template:Math is equal to the length of the first row of Template:Mvar (and of Template:Mvar).
• The length of the longest decreasing subsequence of Template:Math is equal to the length of the first column of Template:Mvar (and of Template:Mvar), as follows from the previous two properties.
• The descent set Template:Math} of Template:Mvar equals the descent set Template:Math} of Template:Mvar.
• Identify subsequences of Template:Mvar with their sets of indices. It is a theorem of Greene that for any Template:Math, the size of the largest set that can be written as the union of at most Template:Mvar increasing subsequences is Template:Math. In particular, Template:Math equals the largest length of an increasing subsequence of Template:Mvar.
• If Template:Mvar is an involution, then the number of fixed points of Template:Mvar equals the number of columns of odd length in Template:Mvar.

Applications

Application to the Erdős–Szekeres theorem

The Robinson-Schensted correspondence can be used to give a simple proof of the Erdős–Szekeres theorem.

See also

• Viennot's geometric construction, which provides a diagrammatic interpretation of the correspondence.
• Plactic monoid: the insertion process can be used to define an associative product of Young tableaux with entries between 1 and Template:Mvar, which is referred to as the Plactic monoid of order Template:Mvar.

References

• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation.

Further reading

• Template:Cite book

External links

• Template:Eom
• Williams, L., Interactive animation of the Robinson-Schensted algorithm