TOPICS
Search

Robinson-Schensted-Knuth Correspondence


The Robinson-Schensted-Knuth correspondence, abbreviated RSK, is a bijection between matrices of nonnegative integers and pairs of semistandard Young tableaux of the same shape. The entries of a matrix specify multiplicities of pairs in a two-row array ordered lexicographically. Row insertion of the second-row entries builds an insertion tableau, and recording the first-row entries builds a recording tableau. For a permutation matrix, both tableaux are standard, giving the Schensted correspondence (Knuth 1970, Nguyen et al. 2026).

Nguyen et al. (2026) extend a piecewise-linear form of RSK to d-complete posets. Their map is invertible and volume-preserving and sends nonnegative fillings satisfying a weighted hook constraint to fillings whose values weakly decrease as poset elements increase and that satisfy a corresponding sum constraint. Comparing the volumes yields a purely combinatorial proof of the multivariate hook length formula for d-complete posets.

Dequêne (2026) constructs a bijection from nonnegative integer fillings of a fixed nonempty partition shape lambda to fillings of the same shape that are weakly increasing along rows and columns, called reverse plane partitions. The construction uses a type-A_n quiver representation and is indexed by a Coxeter element of the symmetric group S_(n+1), where n is the upper-left hook length of lambda. Particular choices recover the Gansner and Hillman-Grassl correspondences.


See also

Hook Length Formula, Permutation Matrix, Schensted Correspondence, Young Tableau

Explore with Wolfram|Alpha

References

Dequêne, B. "An Extended Generalization of RSK Correspondence via A Type Quiver Representations." Elec. J. Combin. 33, P4.30, 2026. https://doi.org/10.37236/15236.Knuth, D. E. "Permutations, Matrices, and Generalized Young Tableaux." Pacific J. Math. 34, 709-727, 1970. https://doi.org/10.2140/pjm.1970.34.709.Nguyen, S.; Vulakh, J.; and Woodruff, D. "A Generalization of RSK to d-Complete Posets." Elec. J. Combin. 33, P4.1, 2026. https://doi.org/10.37236/15257.

Cite this as:

Weisstein, Eric W. "Robinson-Schensted-Knuth Correspondence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Robinson-Schensted-KnuthCorrespondence.html

Subject classifications