Permutation Group Question

Question

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

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)$.