MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For those who are unfamiliar with the terminology, I'll explain a little.

The symmetric group $S_n$, as a type A Coxeter group, has generators $\{s_1,\ldots,s_{n-1}\}$ with relations (1) $s_i^2$ for all $i$; (2) $(s_is_j)^2$ for $|i-j|>1$; and (3) $(s_is_j)^3$ for $|i-j|=1$. For $\pi\in S_n$, we denote by $\ell(\pi)$ the length of a shortest word (product of generators) $s_{i_1}\cdots s_{i_\ell}$ which is equal to $\pi$. The right weak Bruhat order on $S_n$ is the partial order defined as the transitive closure of the cover relations: $\pi<\pi s_i$ if $\ell(\pi)<\ell(\pi s_i)$ for some generator $s_i$. For any partially ordered set, we say that a subset $C$ of its elements is convex if, whenever $x,y\in C$ with $x<y$ it happens that the entire interval $[x,y]\subset C$.

If we write our permutations in one-line format, the usual right action of the generator $s_i$ is to swap the entries in positions $i$ and $i+1$. E.g. if $\pi=632514\in S_6$ in one-line format, then $\pi s_3 = 635214$. An elementary Knuth transformation associates two permutations which differ by one of these generators under the following conditions, described in terms of their one-line notations: $$ \ldots xyz \ldots \quad\sim\quad \begin{cases} \;\ldots xzy \ldots &\text{if } y<x<z \text{ or } z<x<y \\ \;\ldots yxz \ldots &\text{if } y<z<x \text{ or } x<z<y \end{cases} $$ For example, $632514\sim 635214$ and $635214\sim 635241$. The transitive closure of these associations, denoted $\sim$, is called Knuth equivalence or plactic equivalence.

Now the question: If $C$ is a plactic equivalence class of permutations viewed as a subset of $S_n$, with $S_n$ having the weak right Bruhat order, is $C$ necessarily convex? It is true for the examples I have worked out by hand. If it is true in general, then is it a known result? If so, could someone provide a citation?

share|cite|improve this question
Same plactic class means RSK gives the same insertion tableau (but different recording tableau), right? Also, is the analogous question for dual equivalence and left Bruhat order equivalent to this question? – Alexander Woo Aug 25 '11 at 3:46
Correct on both counts. – Kurt Luoto Aug 25 '11 at 18:28
A good person to ask would be Muge Taskin (former student of Vic Reiner, now at Bo─čaziçi University in Turkey). She doesn't appear to be a MathOverflow user but you can find her website through Vic's page, under students. I have a vague recollection of asking Muge this question and getting an affirmative answer. But I may be remembering wrong. – Nathan Reading Jun 16 '12 at 2:05
Bump (oops). Taskin's arXiv:math/0509174v2, in its Definition 2.3, implicitly says that the "weak order" on the set of SYTs is a partial order. Doesn't this imply that plactic classes of permutations are convex? If so, then how is it proven? – darij grinberg Apr 9 '15 at 5:54
Oh. It seems that if $u \leq v$ in the right weak Bruhat order, then the shape of the RSK insertion tableau $P\left(u\right)$ (weakly) dominates the shape of the RSK insertion tableau $P\left(v\right)$. Or so I understand Taskin's paper. This, of course, would immediately prove that plactic classes are convex... – darij grinberg Apr 9 '15 at 5:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.