7

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!

YCor
  • 60,149
fern-gossow
  • 81
  • 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) – Per Alexandersson Aug 10 '22 at 07:03
  • 1
    Related: https://mathoverflow.net/a/140739/ – darij grinberg Aug 10 '22 at 09:45
  • 3
    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. – darij grinberg Aug 10 '22 at 09:47
  • I don't have a really good source, but I think your statement is a direct consequence of Prop. 4.2 in https://arxiv.org/abs/math/0604140 (which is essentially Darij's comment). – Martin Rubey Aug 10 '22 at 12:17
  • A common reference I've seen is Knuth's Art of Computer Programming Vol 3 sec 5.1.4, where Knuth cited Schutzenberger for this proposition: https://www.mscand.dk/article/view/10676/8697 – Sylvester W. Zhang Aug 10 '22 at 14:27
  • 1
    A slight clarification re: Darij's second comment - you will need the dual Knuth moves, which act on consecutive values rather than consecutive positions. – Zach H Aug 10 '22 at 14:38

1 Answers1

1

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)$$

fern-gossow
  • 81