Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|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
1  
I'm wondering: did anything come out of this question? –  darij grinberg Aug 13 '13 at 19:27

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.