nLab Robinson-Schensted-Knuth correspondence

Idea

Robinson–Schensted correspondence is a canonical bijection between the permutations from the symmetric group $\Sigma(n)$ on $n$ letters and pairs of standard Young tableaux of the same type.

Robinson-Schensted-Knuth correspondence is a combinatorial bijection sending matrices with non-negative integer entries to pairs of semistandard Young tableaux.

Variants

• Given a word of length $n$ over the alphabet $[1, N]$, one can associate to it two tableaux of size $n$ and the same shape, one a standard Young tableaux and one a semistandard Young tableau with entries from $[1, N]$.

Related entries

• Schur-Weyl duality

References

Wikipedia: Robinson–Schensted correspondence, Robinson–Schensted–Knuth_correspondence

A textbook account is in

• William Fulton, Young Tableaux, Cambridge University Press 1997

For an overview see

• Per Alexandersson, The Robinson–Schensted–Knuth correspondence, webpage

• Christian Krattenthaler, Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. Advances in Applied Mathematics, 37(3):404–431, September 2006 (arXiv:math/0510676).

• Pierre-Loïc Méliot, Kerov’s central limit theorem for Schur–Weyl measures of parameter 1/2 (arXiv:1009.4034)

• Donald E. Knuth, Permutations, matrices, and generalized Young tableaux. Pacific Journal of Mathematics 34 (3): 709–727 (1970) doi

• Masatoshi Noumi, Yasuhiko Yamada, Tropical Robinson–Schensted–Knuth correspondence and birational Weyl group actions, in: Representation Theory of Algebraic Groups and Quantum Groups, in: Adv. Stud. Pure Math. 40, Math. Soc. Japan, Tokyo, 2004, pp. 371–442

RSK correspondence satisfies the octahedron recurrence. In the following article this is established with a point of view that RSK correspondence is a tropicalization? of Dodgson condensation rule,

• V.I. Danilov, G. A. Koshevoy, The octahedron recurrence and RSK-correspondence, Sém. Lothar. Combin. 54A (2005/07) Art. B54An, 16 pp. (electronic) published pdf arXiv:math.CO/0703414

On a bijective proof of that fact

• Miriam Farber, Sam Hopkins, Wuttisak Trongsiriwat, Interlacing networks: Birational RSK, the octahedron recurrence, and Schur function identities, Journal of Combinatorial Theory A 133 (2015) 339–371 doi

category: combinatorics