Robinson-Schensted correspondence

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

The $P$-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 $T$. To insert a number $m$, it is placed in the first row of $T$, either by replacing the first entry greater than $m$ in that row, or if there is no such entry, by adding it to the end of the row. If a number $m'$ was replaced, $m'$ is placed in the next row using the same rule, and so on, until at some step no number is replaced. The $Q$-symbol of $\pi$ records the successive shapes of $T$ by having entry $i$ in the square added to the shape of $T$ by insertion of $\pi(i)$; the final value of $T$ is the $P$-symbol of $\pi$. E.g., for $\pi = (2,6,3,5,1,7,4)$, one has

      ┌───┬───┬───┬───┐     ┌───┬───┬───┬───┐
      │ 1 │ 3 │ 4 │ 7 │     │ 1 │ 2 │ 4 │ 6 │
      ├───┼───┼───┴───┘     ├───┼───┼───┴───┘
  P = │ 2 │ 5 │         Q = │ 3 │ 7 │        
      ├───┼───┘             ├───┼───┘        
      │ 6 │                 │ 5 │         
      └───┘                 └───┘             

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

The correspondence has a fundamental but non-trivial symmetry: replacing $\pi$ by $\pi^{-1}$ interchanges $P$ and $Q$. 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 $\pi$ transposes both $P$ and $Q$, while also applying this involution to $Q$. Details can be found in [a3] and [a6].

A generalization of this correspondence is obtained by allowing arbitrary sequences of $n$ numbers taken from some fixed set $\{1,\ldots,m\}$; the same algorithm then defines a bijection between the set of such sequences and pairs $P$,$Q$ of equal shape, where $Q$ is still a standard Young tableau of order $n$, but $P$ is now a semi-standard Young tableau (see Young tableau) with entries in $\{1,\ldots,m\}$. This form gives the decomposition of the character of the representation $V^{{\otimes}n}$ of the general linear group $GL(V)$ with $\dim V = m$, into irreducible characters (which are Schur polynomials $S_{\{\lambda\}}$, see Schur functions in algebraic combinatorics): each standard Young tableau $Q$ of shape $\lambda$ corresponds to a factor $S_{\{\lambda\}}$, and each semi-standard Young tableau $P$ of shape $\lambda$ and type (or weight) $\mu$ corresponds to a term $x^\mu$ of $S_{\{\lambda\}}$. A further generalization, which restores the symmetry between $P$ and $Q$, is defined in [a2], and an even further generalization, in which $\pi$, $P$ and $Q$ are all pictures, is defined in [a12]; it probably provides the most natural setting for the Robinson–Schensted correspondence.

Having the same $P$-symbol defines an equivalence relation on sequences of numbers called plactic equivalence. It is generated by relations $acb \leftrightarrow cab$ for $a \le b < c$ and $bac \leftrightarrow bca$ for $a < b \le c$ (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 $P$-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].

Comments

The tableaux $P$ and $Q$ are also known as the insertion tableau and the recording tableau respectively.

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 $q=0$" 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
[b1]	Richard P. Stanley, Enumerative Combinatorics Cambridge University Press (2001) ISBN 0-521-78987-7