1
$\begingroup$

Consider on the symmetric group $\mathfrak{S}_r$ the generating system $\{\tau_i;\,1\le i\le r-1\}$ with $\tau_i = \langle i,i+1\rangle$ and the corresponding word length norm $N$. Now let $\tau\in\mathfrak{S}_r$ and $1\le i\le r-1$ with $\tau^{-1}(i)<\tau^{-1}(i+1)$. Can we deduce $N(\tau_i\circ \tau)>N(\tau)$?

$\endgroup$
3
  • 1
    $\begingroup$ This looks like homework to me... if not: what is the number of inversions of $\tau$ and $\tau_i\circ\tau$? $\endgroup$
    – grok
    Jan 27, 2019 at 16:59
  • 1
    $\begingroup$ It is no homework; I need it for something completely different (building a spanning tree in a large complex). ;) Regarding your hint: Well … as far as I see it, the number of inversions increases by 1 from $\tau$ to $\tau_i\circ \tau$ since we only get the additional inversion pair $(\tau^{-1}(i),\tau^{-1}(i+1))$. I never compared the number of inversions to the world length norm wrt. to the above generating system. Is it obvious that it is the same? $\endgroup$
    – FKranhold
    Jan 27, 2019 at 17:10
  • 1
    $\begingroup$ @FKranhold yes it is: transposing two neighbours changes the number of inversions at most by 1. On the other hand, for any permutation $\pi$ different from the identical you may find two inverted neighbours, transposing them you decrease the number of inversions by 1, this process terminates after inv$(\pi)$ steps. $\endgroup$ Jan 27, 2019 at 21:34

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.