7
$\begingroup$

I am curious about the following result concerning the Robinson-Schensted insertion procedure. I can formulate a proof via the Schützenberger evacuation operator, but I have struggled to find such an argument in the literature, although I believe it should be well-known.

Let $w\in S_n$ be a permutation on $[1,n]$. Given an interval $I\subseteq[1,n]$, write $w\vert_I$ for the partial permutation whose values are those of $I$. Given a standard tableau $T$ on $n$ boxes, write $T\vert_I$ for the skew tableau obtained by restricting $T$ to the values of $I$.

Finally, we let $P(-)$ denote the Schensted insertion (partial) tableau for a (partial) permutation. The result says that for every $w\in S_n$ and every interval $I$, we have:

$$P(w\vert_I)=\mathsf{rect}(P(w)\vert_I)$$

where $\mathsf{rect}$ is the rectification of a skew tableau via jeu-de-taquin.

Any comments would be appreciated!

Improve this question
$\endgroup$
6
  • $\begingroup$ Hi Fern, and welcome to MO! That's a really good question! (Also, I can see how this might be interesting to you, wrt the KL-basis and your talk at FPSAC) $\endgroup$
    – Per Alexandersson
    Commented Aug 10, 2022 at 7:03
  • 1
    $\begingroup$ Related: mathoverflow.net/a/140739 $\endgroup$
    – darij grinberg
    Commented Aug 10, 2022 at 9:45
  • 3
    $\begingroup$ I think the easiest way to prove this should be via plactic equivalence. Two semistandard tableaux of straight shape are equal if and only if their reading words are plactically (= Knuth-)equivalent. Plactic equivalence is preserved under rectification and RS-insertion, and is respected by restriction to an interval. Poof, done! Fomin's appendix to EC2 should have all the relevant references, although all of them will have to be generalized from standard to semistandard. $\endgroup$
    – darij grinberg
    Commented Aug 10, 2022 at 9:47
  • $\begingroup$ I don't have a really good source, but I think your statement is a direct consequence of Prop. 4.2 in arxiv.org/abs/math/0604140 (which is essentially Darij's comment). $\endgroup$
    – Martin Rubey
    Commented Aug 10, 2022 at 12:17
  • 1
    $\begingroup$ A slight clarification re: Darij's second comment - you will need the dual Knuth moves, which act on consecutive values rather than consecutive positions. $\endgroup$
    – Zach H
    Commented Aug 10, 2022 at 14:38

1 Answer 1

Reset to default
1
$\begingroup$

After some thought, there is also a nice argument using the permutation tableau. For $w\in S_n$, let $W$ be the antidiagonal tableau with row-reading-word $w$. Then $P(w)=\mathrm{rect}(W)$, and so $$P(w\vert_I)=\mathrm{rect}(W\vert_I)=\mathrm{rect}(\mathrm{rect}(W)\vert_I)=\mathrm{rect}(P(w)\vert_I)$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .