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$
5
  • $\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, 2022 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, 2022 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, 2022 at 14:06
  • $\begingroup$ Opening this question, I was curious what the Weyl group with one element was $\endgroup$ Nov 30, 2022 at 7:39
  • $\begingroup$ With regard to it being an "open question" how many commutation classes there are, we at least know specific values up to $n=16$, see oeis.org/A006245, where there is also some Maple code I posted for computing it (I was the first one to compute a(12)). In terms of a closed form, which might be what you consider the "open" part of the question, given how difficult it has been to find the first $16$ values I'd bet a lot of money that there's no closed form expression for this number. It has a lot of combinatorial interpretations and I think it is sharp-P hard to compute it. $\endgroup$ Aug 15, 2023 at 21:29

2 Answers 2

12
$\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.

$\endgroup$
9
$\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 and acknowledge you have read our privacy policy.

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