A question about permutation groups: I wonder if someone who is expert in permutation group theory could answer the following question.

Let $x \in S_n$ (the symmetric group) be an involution which is the product of k disjoint transpositions.

For any permutation $y \in S_n$, let f(y) be the length of a shortest reduced word in $x, y, \mbox{ and } y^{-1}$ that equals the identity.

Finally, let F(k,n) be the maximum of f(y) over all (non-involutions) $y \in S_n$ ($n >= 2k$).

Question: Is there an easy way to determine F(k,n)?

For (very) small k the evidence suggests something like F(k,n) = 12k. For k=1 this is easy to show by a case analysis, based on how the transposition intersects the cycles of y. Even for k=2 I found the problem harder than expected. Perhaps this has been studied before?

Of course this could be restated as a question about the maximum girth of Type II, 3-regular Cayley graphs on $S_n$.

  • $\begingroup$ Note that $x$ normalizes $Y = \langle y,y^{x} \rangle.$ If the latter group has even order it contains an involution. If it has odd order, the coset $xY$ contains an involution other than $x$ unless $x$ centralizes $y.$ $\endgroup$ Jan 22, 2014 at 8:51
  • $\begingroup$ I don't understand the conjectured value for $F(k,n)$. Do you mean it should not depend on $n$? $\endgroup$ Jan 22, 2014 at 16:47
  • $\begingroup$ My feeling was that for n sufficiently large, F won't depend on n. So long as there is enough room to conjugate x so that the conjugate doesn't move anything that x moves, n won't matter. In that case, you'll have two words that commute. For small n (something like 4k?), F will probably depend on n. $\endgroup$ Jan 22, 2014 at 22:38

1 Answer 1


This is not a complete answer but maybe more an extended comment.

First, it is not hard to find an upper bound that does not depend on $n$, as you claimed. Note that $x$ has support $2k$ and hence so does $x^y$. This implies that $xx^y$ has support at most $4k$ hence is contained in some copy of $S_{4k}$. Since the word $xx^y$ has length $4$, an upper bound on $F(n,k)$ is $4$ times the maximal order of an element in $S_{4k}$.

This is not tight and can easily be improved. For example, we know that $xx^y$ is the product of two involutions, each of which is a product of $k$ disjoint transpositions. Let $g(k)$ be the maximal order of such an element. Then we have that $F(k,n)\leq 4g(k)$.

It is easy to see that $g(1)=3$ hence you recover $F(1,n)\leq 12$.

If I did not make a mistake, we have $g(2)=5$ (with an example given by $x=(12)(34)$ and $x^y=(13)(25)$ with product a $5$-cycle). This gives $F(2,n)\leq 20$, which shows that your conjecture of $12k$ is wrong.

Finally, note that there are explicit upper bounds known on the maximal order of an element of $S_{4k}$, hence you can already get explicit upper bounds on $F(n,k)$ as a function of $k$. These are probably not tight and the best way to improve them would probably to obtain upper bounds on $g(k)$.


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.