Up to now, what are the difference ways we know to define RSK correspondence? I already know:

  1. By insertion and recording tableau.
  2. Ball construction or Viennot's geometric construction.
  3. Growth diagram proposed by Sergey Fomin.

Do you know other models?

  • 5
    $\begingroup$ There is a very enlightening description of RSK in terms of piecewise-linear maps that goes back to Igor Pak: eudml.org/doc/121696 $\endgroup$ Feb 3, 2020 at 17:39
  • 1
    $\begingroup$ See also the presentation of Robin Sulzgruber: dx.doi.org/10.4310/JOC.2020.v11.n2.a3 $\endgroup$ Feb 3, 2020 at 17:41
  • 2
    $\begingroup$ There is also a direct connection of RSK to important topics in representation theory like Hecke algebras, Kazhdan-Lusztig theory, Springer fibers, etc. and that perspective is probably the most 'canonical'. But it sounds like you are interested in combinatorial constructions. $\endgroup$ Feb 3, 2020 at 17:52
  • 2
    $\begingroup$ Do you know about the relation between KL cells and Knuth equivalence? See e.g. arxiv.org/abs/math/9910117 for the basics along these lines. $\endgroup$ Feb 3, 2020 at 18:06
  • 2
    $\begingroup$ Greene's theorem describes the shape of the insertion tableau in terms of unions of increasing subsequences of the permutation $w=a_1\cdots a_n$. Thus we can build up the insertion tableau $P(w)$ one step at a time by applying Greene's theorem to the subpermutations (subsequences) of $w$ consisting of the numbers $1,2,\dots,i$. We can similarly compute the recording tableau $Q(w)$ since $Q(w)=P(w^{-1})$. $\endgroup$ Feb 8, 2020 at 17:13

1 Answer 1


Here, slightly edited, is the first paragraph of Steinberg's paper, An occurrence of the Robinson–Schensted correspondence.

Let $V$ be an $n$-dimensional vector space over an infinite field, $\mathscr F$ the flag manifold of $V$, $u$ a unipotent transformation of $V$, and $\lambda$ the type of $u$, a partition of $n$ whose parts are the sizes of the Jordan blocks for $u$. … The components of $\mathscr F_u$, the variety of flags fixed by $u$, correspond naturally to the standard tableaux of shape $\lambda$. The purpose of this note is to show that the "relative position" of any two components of $\mathscr F_u$ (in general an element of the Weyl group, in the present case an element of $S_n$) is given, in terms of the corresponding tableaux, by the Robinson–Schensted correspondence.

  • $\begingroup$ Thanks Timothy! $\endgroup$
    – Mihawk
    Feb 4, 2020 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy