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?

  • 4
    $\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$ – Sam Hopkins Feb 3 at 17:39
  • 1
    $\begingroup$ See also the presentation of Robin Sulzgruber: dx.doi.org/10.4310/JOC.2020.v11.n2.a3 $\endgroup$ – Sam Hopkins Feb 3 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$ – Sam Hopkins Feb 3 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$ – Sam Hopkins Feb 3 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$ – Richard Stanley Feb 8 at 17:13

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.

| cite | improve this answer | |
  • $\begingroup$ Thanks Timothy! $\endgroup$ – Mihawk Feb 4 at 4:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.