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



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


