Robinson–Schensted correspondence

Robinson–Schensted correspondence is a bijective combinatorial construction associating permutations with pairs of Young tableaux. Developed through work connected to Gilbert Robinson, C. Schensted, and later refined by Donald Knuth and Marcel-Paul Schützenberger, the correspondence links representation theory, symmetric group combinatorics, and algebraic geometry via tableaux enumerations. It underpins results in the theory of symmetric functions, the study of longest increasing subsequences, and connections to random matrix theory.

Introduction

The origin of the correspondence traces to Gilbert Robinson and C. Schensted, with subsequent expansions by Donald Knuth, Richard Stanley, and Marcel-Paul Schützenberger. It plays a central role in the calculus of Young tableaux used in the representation theory of the symmetric group and the general linear group, as developed by Frobenius, Hermann Weyl, and Élie Cartan. Applications span combinatorial proofs in the style of Percy MacMahon, algorithms related to the Schensted insertion influenced by John von Neumann and Alan Turing era concerns, and probabilistic connections explored by Craig Tracy and Harold Widom in random matrix theory.

Definitions and constructions

The basic construction takes a finite permutation from the symmetric group and produces a pair of standard Young tableaux of identical shape using Schensted insertion, an algorithm formalized by C. Schensted and later systematized by Donald Knuth. Definitions rely on Young diagrams originally studied by Alfred Young, and the notion of standard and semistandard tableaux developed in the work of Alfred Young and Richard Littlewood. The insertion algorithm iteratively places values into a tableau using bumping rules influenced by the combinatorics in the work of Percy MacMahon and connections to the hook-length formula of Frame, Robinson, and Thrall. Recording of insertion history yields the second tableau; this duality is central in proofs by Marcel-Paul Schützenberger and in the RSK algorithm extensions attributed to Knuth.

Properties and theorems

Key theorems include bijectivity between permutations and pairs of standard Young tableaux (same shape), the Greene invariants relating to increasing and decreasing subsequences as studied by C. Greene, and Schensted's theorem equating the length of the longest increasing subsequence to the first row length of the insertion tableau. The correspondence preserves descent sets linked to work by Louis Solomon and connects with the Robinson–Schensted–Knuth (RSK) correspondence which generalizes to matrices, a generalization exploited by Richard Stanley in enumerative formulas and by Alain Lascoux in symmetrization contexts. Schützenberger's involution and the jeu de taquin procedure relate to promotion and evacuation operators considered in the works of Dominique Foata and Gian-Carlo Rota. Connections to the representation theory of the symmetric group appear through the Specht modules studied by W. Specht and James, and further relate to characters investigated by Frobenius.

Variants and generalizations

Variants include the RSK correspondence, the Burge correspondence, and q-analogues developed in the representation-theoretic programs of George Lusztig and Jimbo. Generalizations to semistandard tableaux connect with the theory of Schur functions in the writings of Issai Schur and with Hall–Littlewood polynomials studied by Philip Hall. Other extensions link to crystal bases in the work of Masaki Kashiwara and representation theory of quantum groups investigated by Vladimir Drinfeld. Geometric and probabilistic generalizations interact with the longest increasing subsequence problem as studied by Jinho Baik and Kurt Johansson and with measures on partitions considered by Anatoly Vershik and Sergei Kerov.

Examples and applications

Concrete examples illustrate mapping simple permutations to tableau pairs using Schensted insertion, with classical cases treated in expositions by Donald Knuth and Richard Stanley. Applications include the analysis of longest increasing subsequences with impacts on interacting particle systems researched by Craig Tracy and Harold Widom, enumerative identities for plane partitions tied to Percy MacMahon's work, and algorithmic implications for sorting networks explored in the context of John von Neumann-era computation and later in theoretical computer science by Michael Rabin and Andrew Yao. In representation theory, the correspondence provides combinatorial models for decomposition multiplicities in the works of George Mackey and Alfred Young, and in algebraic geometry it informs Schubert calculus studied by Hermann Schubert and William Fulton.

Category:Combinatorics