8
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$ Nov 24 at 13:59
  • $\begingroup$ @TomDeMedts: yes, and this set-up is very common, so I think the question is clear as it is. $\endgroup$ Nov 24 at 14:03
  • $\begingroup$ 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) $\endgroup$ Nov 24 at 14:06
  • $\begingroup$ 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. $\endgroup$ Nov 24 at 16:44

2 Answers 2

10
$\begingroup$

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.
$\endgroup$
8
$\begingroup$

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.

$\endgroup$

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.