Skip to main content
4 of 4
correcting stupid errors
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

Has Reifegerste's Theorem on RSK and Knuth relations received a slick proof by now?

For the notations I am using, I refer to the Appendix at the end of this post.

Here is what, for the sake of this post, I consider to be Reifegerste's theorem:

Theorem 1. Let $n\in\mathbb N$ and $i\in\mathbb N$. Let $\sigma$ and $\tau$ be two permutations in $S_n$ such that $\sigma$ and $\tau$ differ by a Knuth transformation at positions $i-1,i,i+1$. Then, the recording tableaux $Q\left(\sigma\right)$ and $Q\left(\tau\right)$ differ only by the interchange of two entries. Specifically, one of the following two cases must hold:

Case 1: In one of the two tableaux $Q\left(\sigma\right)$ and $Q\left(\tau\right)$, the letter $i+1$ lies weakly northeast of $i-1$, which in turn lies weakly northeast of $i$. The other tableau is obtained from this one by switching $i$ with $i+1$.

Case 2: In one of the two tableaux $Q\left(\sigma\right)$ and $Q\left(\tau\right)$, the letter $i$ lies weakly northeast of $i+1$, which in turn lies weakly northeast of $i-1$. The other tableau is obtained from this one by switching $i-1$ with $i$.

Remark. Theorem 1 appeared first implicitly(!) in Astrid Reifegerste's paper "Permutation sign under the Robinson-Schensted correspondence" (also in an apparently older version as arXiv:0309266v1), where it serves as an auxiliary observation in the proof of Lemma 4.1 (formulated for dual Knuth transformations instead of Knuth transformations, but that is just a matter of inverting all permutations). Then, it was explicitly stated as Corollary 4.2.1 in Jacob Post's thesis "Combinatorics of arc diagrams, Ferrers fillings, Young tableaux and lattice paths. Both sources give rather low-level proofs which involve little theory but a lot of casework and handwaving (including references to pictures, sadly not in Zelevinsky's sense of this word). They seem to be very similar. I cannot say I fully understand either. Note that there are two cases depending on which of the Knuth relations is used, and one (the $bac$-$bca$ switch) is simpler than the other (the $acb$-$cab$ switch).

Question 1. Since Reifegerste and Post, has anyone found a slick proof of Theorem 1? I can't precisely define what I mean by "slick", but a good approximation would be "verifiable without a lot of pain" and possibly "memorable". I am not asking for it to be short or not use any theory. Indeed, I have a suspicion that an approach in the style of the proof of Corollary 1.11 in Sergey Fomin's appendix to EC1 could work: Since the recording tableau of a word $w$ is determined by the RSK shapes of the prefixes of $w$, it would be enough to show that for all but one $k$, the RSK shape of the $k$-prefix of $\sigma$ equals the RSK shape of the $k$-prefix of $\tau$. Due to Fomin's Theorem 11, this reduces to showing that for all but one $k$, for all $i$, the maximum size of a union of $i$ disjoint increasing subsequences of the $k$-prefix of $\sigma$ equals the maximum size of a union of $i$ disjoint increasing subsequences of the $k$-prefix of $\tau$. This is very easy to see when $\sigma$ and $\tau$ differ by a $bac$-$bca$ Knuth transformation. I'm unable to prove this for an $acb$-$cab$ Knuth transformation, though (I can only prove it with "all but two $k$" in that case). But the approach sounds very promising to me. Alternatively, the growth diagram view on RSK could help.

Question 2. What if we let $\sigma$ and $\tau$ be arbitrary words instead of permutations? Does the possibility of repeated letters break something?

Appendix: notations.

Here are definitions for some notations I am using above:

  • A word over a set $A$ means an $n$-tuple of elements $A$ for some $n\in\mathbb N$ (where $0 \in \mathbb N$). The word $\left(a_1,a_2,...,a_n\right)$ is often written as $a_1a_2...a_n$. The entries of a word are called its letters. We identify every $a\in A$ with the one-letter word $\left(a\right)$. For any two words $u$ and $v$ over the same set $A$, we denote by $uv$ the concatenation of $u$ with $v$ (that is, the word $\left(a_1,a_2,...,a_n,b_1,b_2,...,b_m\right)$, where $\left(a_1,a_2,...,a_n\right)=u$ and $\left(b_1,b_2,...,b_m\right)=v$).

  • For any $n\in\mathbb N$, any permutation $\sigma \in S_n$ is identified with the $n$-letter word $\sigma\left(1\right) \sigma\left(2\right) ... \sigma\left(n\right)$ over $\mathbb Z$.

  • If $u$ and $v$ are two words over $\mathbb Z$, then we say that $u$ and $v$ differ by a Knuth transformation if either of the following four cases holds:

Case 1: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a < b \leq c$ such that $u = p bac q$ and $v = p bca q$.

Case 2: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a < b \leq c$ such that $u = p bca q$ and $v = p bac q$.

Case 3: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a \leq b < c$ such that $u = p acb q$ and $v = p cab q$.

Case 4: There exist words $p$ and $q$ and integers $a$, $b$, $c$ satisfying $a \leq b < c$ such that $u = p cab q$ and $v = p acb q$.

In either case, we say that $u$ and $v$ differ by a Knuth transformation at positions $i-1,i,i+1$, where $i$ is the length of the word $p$ plus $2$.

(Note that instead of "Knuth transformation", some authors say "elementary Knuth transformation" or "elementary Knuth equivalence". Contrary to what the latter wording might suggest, the "differ by a Knuth transformation" relation itself is not an equivalence relation. The reflexive-and-transitive closure of this relation is the well-known Knuth equivalence. Note also that Reifegerste's theorem is only formulated for permutations (which, viewed as words, have no two equal letters), which allows one to ignore the distinction between $a < b \leq c$ and $a \leq b < c$; but I am keeping the $\leq$s apart from the $<$s because of Question 2 which sets them apart again.)

  • If $w$ is a word, then $Q\left(w\right)$ denotes the recording tableau of $w$ under the Robinson-Schensted-Knuth correspondence.

  • Young diagrams and Young tableaux are written in English notation (so that the topmost row is the longest, and the leftmost column is the highest). Geographical terminology (like "northwest") refers to this orientation.

darij grinberg
  • 33.8k
  • 4
  • 118
  • 253