Skip to main content
1 of 5
Kurt Luoto
  • 331
  • 3
  • 9

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<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) $xyz$ can be replaced by $xzy$ if either $x<y<z$ or $z<y<x$, or they can be replaced by $yxz$ if either $x<z<y$ or $y<z<x$. 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?

Kurt Luoto
  • 331
  • 3
  • 9