# Commutation classes of reduced decompositions of the longest element of the Weyl group with one element

For the symmetric group on $$n$$ objects $$S_n$$ the question of how to write its longest element $$w_0$$ as a reduced decomposition is an important combinatorical problem. As example, in this question the number of such decompositions is discussed.

Following Stembridge, we define a relation $$∼$$ on the set of reduced expressions for $$w_0$$. Let $$\mathbf{w}$$ and $$\mathbf{w}'$$ be two reduced expressions for $$w_0$$ and define $$\mathbf{w} \sim \mathbf{w}'$$ if we can obtain $$\mathbf{w}'$$ from $$\mathbf{w}$$ by applying a single commutation. Now, define the equivalence relation $$\simeq$$ by taking the reflexive transitive closure of $$\sim$$. Each equivalence class under $$\simeq$$ is called a commutation class.

The question of the number of commutation classes (of reduced expressions for $$w_0 \in S_n$$) is still an open problem. However, is there an formula for the number of equivalence classes containing just one element?

• Do you mean that you consider $S_n$ as a Coxeter group with generating set $s_1 = (12)$, $s_2 = (23)$, $s_3 = (34)$, etc.? What do you mean by a "single commutation"? Do you mean that you replace a single instance of $s_i s_j$ by $s_j s_i$ where $s_i$ and $s_j$ are commuting generators? Nov 24 at 13:59
• @TomDeMedts: yes, and this set-up is very common, so I think the question is clear as it is. Nov 24 at 14:03
• Not an answer to your question, but sort of related: there has been work done on computing the expected number of braid moves that one can apply to a random reduced expression for $w_0$: see Reiner (doi.org/10.1016/j.ejc.2004.06.010), Tenner (ajc.maths.uq.edu.au/pdf/62/ajc_v62_p147.pdf), Schilling et al. (doi.org/10.1016/j.ejc.2016.10.008) Nov 24 at 14:06
• Another non-answer comment: we can create the graph of reduced expressions, with two kinds of edges - say red and blue - corresponding to the commutation and (long) braid moves. By the Tits-Matsumoto lemma, this graph is connected, so each vertex either has a red or blue edge coming out of it. The result of Reiner I cited above says that the total number of blue edges in this graph is one half the number of vertices. You are asking for an enumeration/classification of vertices that have only blue edges coming out of them. Nov 24 at 16:44

The reduced words that are in their own commutation classes are:

• $$s = [123\cdots(n-2)(n-1)(n-2)\cdots321][23\cdots(n-3)(n-2)(n-3)\cdots32][3\cdots(n-4)(n-3)(n-4)\cdots3]\cdots$$
• the reversal of $$s$$ (writing the word in reverse order)
• the complement of $$s$$ (mapping each letter $$i$$ to $$n-i$$)
• the reverse complement of $$s$$

This is just one word in $$S_2$$ and two words in $$S_3$$ (no big surprises there!). Otherwise it is four words. For example, in $$S_6$$, they are

• 123454321234323
• 323432123454321
• 543212345432343
• 343234543212345

On a separate note, to add to the list of related topics, you might want to look at Fishel et al. (https://doi.org/10.1016/j.ejc.2018.07.002) about how commutation classes and braid classes interact.

New contributor
Bridget Tenner is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

I believe that for $$n \geq 4$$ there will be exactly $$4$$ such reduced words. One such word, call it $$R_n$$ can be constructed by starting with $$s_{n-1}s_{n-2} \cdots s_2s_1s_2 \cdots s_{n-2}s_{n-1}$$ and appending $$R_{n-1}$$ with all indices shifted up by 1. For example, $$R_6=s_5s_4s_3s_2s_1s_2s_3s_4s_5s_4s_3s_2s_3s_4s_3.$$ Three more words can be obtained by replacing each $$s_i$$ with $$s_{n-i}$$, reversing the word, or doing both.

For $$n=4,5,6$$ these are the only possibilities, and this probably shouldn't be too hard to argue in general.