Namespaces
Variants
Actions

Robinson-Schensted correspondence

From Encyclopedia of Mathematics
Jump to: navigation, search

A bijection between certain sequences of numbers and pairs of Young tableaux (cf. Young tableau), defined by means of a combinatorial algorithm. In its basic form, the Robinson–Schensted correspondence gives a bijection between the symmetric group , whose elements are represented by the sequences , and pairs of standard Young tableaux of order with equal shapes. The two tableaux are usually referred to as and , or as the -symbol and -symbol of the permutation.

The -symbol can be obtained by repeatedly applying the following so-called Schensted insertion procedure to the terms of the sequence, from left to right, to enter them into an initially empty tableau . To insert a number , it is placed in the first row of , either by replacing the first entry greater than in that row, or if there is no such entry, by adding it to the end of the row. If a number was replaced, is placed in the next row using the same rule, and so on, until at some step no number is replaced. The -symbol of records the successive shapes of by having entry in the square added to the shape of by insertion of ; the final value of is the -symbol of . E.g., for one has

Given standard Young tableaux , of the same shape, this algorithm can be reversed to determine the permutation with these - and -symbols.

The correspondence has a fundamental but non-trivial symmetry: replacing by interchanges and . There are more symmetries, which require another algorithmically defined correspondence, namely a shape-preserving involution of the set of standard Young tableaux that is due to M.-P. Schützenberger [a9]. For instance, reversing the sequence corresponding to transposes both and , while also applying this involution to . Details can be found in [a3] and [a6].

A generalization of this correspondence is obtained by allowing arbitrary sequences of numbers taken from some fixed set ; the same algorithm then defines a bijection between the set of such sequences and pairs , of equal shape, where is still a standard Young tableau of order , but is now a semi-standard Young tableau (see Young tableau) with entries in . This form gives the decomposition of the character of the representation of the general linear group with , into irreducible characters (which are Schur polynomials , see Symmetric polynomial): each standard Young tableau of shape corresponds to a factor , and each semi-standard Young tableau of shape and type (or weight) corresponds to a term of . A further generalization, which restores the symmetry between and , is defined in [a2], and an even further generalization, in which , , and are all pictures, is defined in [a12]; it probably provides the most natural setting for the Robinson–Schensted correspondence.

Having the same -symbol defines an equivalence relation on sequences of numbers called plactic equivalence. It is generated by relations for and for (cf. [a2]); therefore, the set of equivalence classes forms a monoid under concatenation, called the plactic monoid, which has many interesting properties, see [a4].

There exist other algorithmic descriptions of the correspondence than the one given above. In fact, the description originally given by A. Robinson in an (incomplete) attempt to prove the Littlewood–Richardson rule [a7] is rather different. Also, a very simple game, called the jeu de taquin, defined by Schützenberger [a10] gives a non-deterministic procedure for computing the -symbol. Besides providing useful enumerative identities, the correspondence itself has various useful interpretations, e.g., it defines the Kazhdan–Lusztig cells in the symmetric groups [a1], and it has interpretations in terms of the geometry of the flag manifold of general linear groups [a11], and of straightening [a5].

References

[a1] D. Kazhdan, G. Lusztig, "Representations of Coxeter groups and Hecke algebras" Invent. Math. , 53 (1979) pp. 165–184
[a2] D.E. Knuth, "Permutations, matrices and generalized Young tableaux" Pacific J. Math. , 34 (1970) pp. 709–727
[a3] D.E. Knuth, "The art of computer programming III. Sorting and searching" , Addison-Wesley (1975) pp. 48–72
[a4] A. Lascoux, M.P. Schützenberger, "Le monoïde plaxique" Quad. Ricerca Scient. C.N.R. , 109 (1981) pp. 129–156
[a5] B. Leclerc, J.-Y. Thibon, "The Robinson–Schensted correspondence, crystal bases, and the quantum straightening at " Electronic J. Combinatorics , 3 : 2 (1996)
[a6] M.A.A. van Leeuwen, "The Robinson–Schensted correspondence and Schützenberger algorithms, an elementary approach" Electronic J. Combinatorics , 3 : 2 (1996)
[a7] G. de B. Robinson, "On the representations of the symmetric group" Amer. J. Math. , 60 (1938) pp. 745–760
[a8] C. Schensted, "Longest increasing and decreasing subsequences" Canadian J. Math. , 13 (1961) pp. 179–191
[a9] M.P. Schützenberger, "Quelques remarques sur une construction de Schensted" Math. Scand. , 12 (1963) pp. 117–128
[a10] M.P. Schützenberger, "La correspondance de Robinson" D. Foata (ed.) , Combinatoire et Représentation du Groupe Symétrique , Lecture Notes in Mathematics , 579 , Springer (1976) pp. 59–113
[a11] R. Steinberg, "An occurrence of the Robinson–Schensted correspondence" J. Algebra , 113 (1988) pp. 523–528
[a12] A.V. Zelevinsky, "A generalisation of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence" J. Algebra , 69 (1981) pp. 82–94
How to Cite This Entry:
Robinson–Schensted correspondence. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Robinson%E2%80%93Schensted_correspondence&oldid=22993