A question about set of inversion

Question

Let $w \in S_n$ and $inv(w) = \{(i,j): i,j \in \{1,\ldots,n\}, i<j, w(i)>w(j)\}$ the inversion set of $w$. Let ${\bf i}=(i_1,\ldots,i_m)$ be a sequence such that $s_{i_1}\cdots s_{i_m}$ is a reduced expression of $w$. There is a bijection $f_{\bf i}: \{1,\ldots,m\} \to inv(w)$ given by $f_{\bf i}(k) = s_{i_1}s_{i_2} \cdots s_{i_k} \cdots s_{i_2}s_{i_1}$.

For example, let $w=s_1s_2s_1$ and ${\bf i}=(1,2,1)$. Then $f_{\bf i}(1)=s_1=(1,2)$, $f_{\bf i}(2)=s_1s_2s_1=(1,3)$, $f_{\bf i}(3)=s_1s_2s_1s_2s_1=(2,3)$.

Suppose that $$ (f_{\bf i}(1), \ldots, f_{\bf i}(m)) = (\ldots, (i,j), \ldots, (i,k), \ldots, (j,k), \ldots) $$ for some $i<j<k$. Is it possible to change $(\ldots, (i,j), \ldots, (i,k), \ldots, (j,k), \ldots)$ to the form $(\ldots, (i,j), (i,k), (j,k), \ldots)$ using the following two kinds of moves?

1. if $\{a,b\} \cap \{c,d\} = \emptyset$, $a,b,c,d \in \{1,\ldots,n\}$, then we can change $(\ldots, (a,b), (c,d), \ldots)$ to $(\ldots, (c,d), (a,b), \ldots)$.

2. we can change $(\ldots, (a,b), (a,c), (b,c), \ldots)$ to $(\ldots, (b,c), (a,c), (a,b), \ldots)$ and vise versa, where $a,b,c\in \{1,\ldots,n\}$.

Are there some references about this? Thank you very much.

Answer 1

(I'm starting by rephrasing the question, because it makes sense in terms of Coxeter groups. Skip down further for the simple answer for permutations.)

The two moves you describe are called braid moves in Section 3.3 of Björner and Brenti's Combinatorics of Coxeter groups (and this is standard terminology). (However, braid moves are usually defined in terms of the reduced expressions, not the inversion sequence. Furthermore, that section deals, more generally, with Coxeter groups.) Their Theorem 3.3.1(ii) says that any two reduced expressions for $w$ can be related by a sequence of braid moves.

Your question is a bit more subtle, and is equivalent to the following question: Given a reduced expression for $w$ whose reflection sequence is $(\ldots,(i,j),\ldots,(i,k),\ldots,(j,k),\ldots)$ is there also a reduced expression for $w$ whose reflection sequence is $(\ldots,(j,k),\ldots,(i,k),\ldots,(i,j),\ldots)$?

(If the answer to the original question is yes, the one more braid move will provide a positive answer to my rephrasing. If the answer to my rephrasing is yes, then there must have been a step at which a braid move changed $(\ldots,(i,j),(i,k),(j,k),\ldots)$ to $(\ldots,(j,k),(i,k),(i,j),\ldots)$. Just before that step, we have found a positive answer to the original question.

The answer to both questions is undoubtedly "yes" for Coxeter groups in general, although I'm having trouble thinking of a quick proof or reference in the short time I have before I have to get back to work. (I would love it if someone else supplies one.) [UPDATE: There are good reasons I couldn't find a quick proof! See David Speyer's comment and answer below.] But here is a quick proof for the symmetric group:

The fact that the inversion sequence is $(\ldots,(i,j),\ldots,(i,k),\ldots,(j,k),\ldots)$ implies in particular that the one-line notation for the permutation has $\cdots k \cdots j \cdots i \cdots$. A reduced expression amounts to a sequence of swaps of adjacent entries in the permutation, always putting entries into numerical order, ending at the identity permutation. (This corresponds to removing the rightmost letter in the reduced expression at each step.) The given expression exchanges the $j$ and $k$ first, but we need to be able to exchange the $i$ and $j$ first. We can do this as long as we first move away all entries that are between them. This is possible because entries less than $j$ can be moved left of $j$ and entries greater than $i$ can be moved right of $i$.

Answer 2

Following up on what Nathan writes, the result I take him to be describing for Coxeter groups in general is false! Consider the Coxeter group $D_4$, with generators $s_0$, $s_1$, $s_2$, $s_3$ where $s_0$ is the center of the Coxeter diagram. Let $$w=s_0 s_1 s_2 s_3 s_0 s_1 s_2 s_3 s_0.$$ The $1^{\mathrm{st}}$, $5^{\mathrm{th}}$ and $9^{\mathrm{th}}$ inversions in the reflection sequence are the reflections of an $A_2$-parabolic but, in every reduced word for $w$, the reflections occur in this order, not the reverse. (This is easy to see because every reduced word for $w$ starts with $s_0$.)

Stembridge's "fully commutative conjecture" asks for something weaker. It states that, if $\mathrm{Inv}(w)$ contains all reflections of some non-commutative rank two parabolic $u W_P u^{-1}$, then there should be two reduced words for $w$ which differ by a braid move -- but it does not require that the braid move reverses the given parabolic!