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

• 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.$ Jan 22, 2014 at 8:51
• I don't understand the conjectured value for $F(k,n)$. Do you mean it should not depend on $n$? Jan 22, 2014 at 16:47
• 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. Jan 22, 2014 at 22:38

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