3

Suppose it is possible, through many steps, to move from the permutation $\pi$ to the permutation $\sigma$ by multiplying, at each step, by a transposition.

Knowing that they are not necessarily conjugates, I want to find:

  1. In how many ways (The maximum number) I can move from $\pi$ to $\sigma$.

  2. bound the maximum number of steps needed to switch from $\pi$ to $\sigma$ (is there a reference).

EDIT 2 In other words, as Peter Taylor proposed:

Let $d(\pi,\sigma)$ be the length of the smallest sequence of transpositions we need to multiply by the permutation $\pi$ to take it to $\sigma$.

  1. How can I bound or even calculate the number of sequences of length $d(\pi,\sigma)$ which take $\pi$ to $\sigma$? (I am looking for any idea)

  2. How can I bound or even calculate $d(\pi,\sigma)$ (This one is answered as explained above)?

It is known that the number of transpositions in the symmetric group $S_n$ is $\frac{n(n-1)}{2}$ and also it is possible to decompose a certain permutation into disjoint cycles, but I don't how to collect these results to answer my question!

Any kind of help is appreciated.

EDIT 1: I don't think my question is a duplicate! it consists of two parts and the marked question answers only one question! The linked question is not talking about the first part of my question!

Noah16
  • 247
  • 1
    Note that the number of steps to move from $\pi$ to $\sigma$ is equal to the number of transpositions one needs to multiply together to form $\pi\sigma^{-1}$; this is a question whose answer is known. – Greg Martin Jul 01 '19 at 17:01
  • @GregMartin Thanks for the link but I don't think it answers my question especially that I am trying to bound the maximum number of possible ways to move between both permutations.

    Concerning the distance you talked about it, I found something similar where the distance equals (n - the number of cycles) but I can't find a reference!

     – Noah16 Jul 01 '19 at 17:19
  • 3
    There is no maximum. You can insert $\tau\tau^{-1}\tau\tau^{-1}...\tau\tau^{-1}$ for any transposition $\tau$, with any number of repetitions. – Lee Mosher Jul 01 '19 at 18:57
  • @LeeMosher so you mean there is no upperbound for the number of ways to move between both permutations by keep multiplying at each step by a transposition! Is this possible? – Noah16 Jul 02 '19 at 09:30
  • To strengthen Lee's point, you have a graph with cycles, so you can just go around a cycle rather than bouncing along an edge. I suspect that what you ought to be asking is "Let $d(\pi, \sigma)$ be the length of the smallest sequence of transpositions which takes $\pi$ to $\sigma$. 1. How can I bound or even calculate $d(\pi, \sigma)$? 2. How can I bound or even calculate the number of sequences of length $d(\pi, \sigma)$ which take $\pi$ to $\sigma$?" – Peter Taylor Jul 02 '19 at 11:03
  • @PeterTaylor you mixed up between the parts of my question! part 1 of my question is the same as part 2 of yours and part 2 of mine is the same as part 1 of yours! Here (the number of sequences of length d(π,σ) which take π to σ) is the same as the number of ways I can go between both permutations – Noah16 Jul 02 '19 at 11:09
  • I did that deliberately, because IMO they make more sense in that order. – Peter Taylor Jul 02 '19 at 11:29
  • @PeterTaylor ah ok I got it. So in your opinion I can't count the number of sequences? – Noah16 Jul 02 '19 at 12:18
  • No idea, although I know that at a practical level it gets difficult when the transpositions are limited to adjacent transpositions. But $d(\pi, \sigma)$ is almost certainly easier to calculate and $(\textrm{number of transpositions})(\textrm{number of transpositions } - 1)^{d(\pi, \sigma) - 1}$ is a loose upper bound for the number of paths. – Peter Taylor Jul 02 '19 at 13:36
  • @PeterTaylor could you kindly add your last comment as an answer with little more clarifications? Thanks in advance – Noah16 Jul 02 '19 at 14:10

0 Answers0