10
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$ Commented Aug 25, 2011 at 3:46
  • $\begingroup$ Correct on both counts. $\endgroup$
    – Kurt Luoto
    Commented Aug 25, 2011 at 18:28
  • $\begingroup$ 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. $\endgroup$ Commented Jun 16, 2012 at 2:05
  • $\begingroup$ 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? $\endgroup$ Commented Apr 9, 2015 at 5:54
  • $\begingroup$ 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... $\endgroup$ Commented Apr 9, 2015 at 5:57

0

You must log in to answer this question.

Browse other questions tagged .