Return to Question

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?

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?

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: \[ \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 \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?

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?