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 (Nguyen et al. 2026, Appendix A).

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.