Let $\Sigma\_n\subset G$ be a set of generators of the symmetric group $S\_n$. It is a well-known conjecture that the diameter of the Cayley graph $\Gamma(S\_n,\Sigma\_n)$ is at most $n^C$ for some absolute constant $C$. (The diameter of the Cayley graph is just the maximum of $\ell(g)$ for $g\in S\_n$, where $\ell(g)$ is the length of the shortest word on $A \cup A^{-1}$ equal to $g$.)


For $\Sigma\_n$ of bounded size, the diameter cannot be less than a constant times $\log |S\_n|$, i.e., a constant times $n\log n$.


It is clear and well-known that, for $\Sigma\_n = \{(1 2),(1 2 \dotsb n)\}$, the diameter of $\Gamma(S\_n, \Sigma\_n)$ is at least a constant times $n^2$. (It is also at most that.)


Are there any examples of generating sets $\Sigma\_n$ for which the diameter is larger than $n^{2+\epsilon}$ for every (or infinitely many) $n$? Larger than $n^2 (\log n)^A$ for some $A>0$ and infinitely many $n$?



Diameter of symmetric group
What follows is an incomplete answer. I am in the middle of Russian woods, so would rather have somebody else trace all the refs, etc. but looking at the bounty expiration date decided that it's worth stating what is known.


The answer is NO to all, but that's a conjecture not a theorem. I have seen this conjecture stated several times in various forms, here are two I find interesting:



> 
> 1) the diameter of every connected
>  Cayley graph $\Gamma$ on $S\_n$ is $O(n^2)$,
> 
> 
> 2) for every O(1) generators of $S\_n$,
>  the *mixing time* of the nearest neighbor r.w. on the corresponding Cayley graph $\Gamma$ is $O(n^3\log n)$.
> 
> 
> 


Since the mixing time is greater than the diameter, the second implies also a bound on the diameter as well. The second conjecture was stated by Diaconis and Saloff-Coste someplace, and is also sharp for a transposition and long cycle as in the question (see Saloff-Coste's [survey](http://www-stat.stanford.edu/~cgates/PERSI/papers/rwfg.pdf)). The first conjecture is a dated folklore and I remember reading it in various places; it appears e.g. in [this paper](http://www.math.ucla.edu/~pak/papers/Gamburd-Pak.pdf) (p. 425) by Gamburd and me.


UPDATE   

See [this](http://www-stat.stanford.edu/~cgates/PERSI/papers/somethings.pdf) recent paper by Diaconis ("Some things we've learned..", 2012) where he reiterates conjecture 2) in Question 2 on p.9. 


