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.

  • $\begingroup$ It would be nice if the person who downvoted the question would add a comment explaining why. Why not give the asker some feedback instead of just a poke in the eye? $\endgroup$ – Nathan Reading Sep 7 '17 at 13:44
  • $\begingroup$ @NathanReading All circumstances equal, it's just as likely a "fat-fingered" user who meant to upvote clicked the wrong button... It's not true that everything is meaningful! $\endgroup$ – François G. Dorais Sep 7 '17 at 22:40

(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$.

| cite | improve this answer | |
  • 1
    $\begingroup$ The result I take you to be asking for is false in $D_4$; see my answer. $\endgroup$ – David E Speyer Sep 7 '17 at 17:09
  • $\begingroup$ Interesting. So this is subtle as a Coxeter-groups question, despite being easy in $S_n$. $\endgroup$ – Nathan Reading Sep 7 '17 at 18:00

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!

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.