MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added some backticks to pacify the formatting programs

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 \emph{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 \emph{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 \emph{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: the subsequence of adjacent letters (integers) $\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, $xyz$ can be replaced by 632514\sim 635214$and$xzy$if either 635214\sim 635241$. The transitive closure of these associations, denoted $x \sim$, is called \emph{Knuth equivalence} or \emph{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?

1

# Are plactic classes convex under the right weak Bruhat order?

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 \emph{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 \emph{convex} if, whenever $x,y\in C$ with $x 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 \emph{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: the subsequence of adjacent letters (integers)$xyz$can be replaced by$xzy$if either$x

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?