Diameter of $S_n$

If $A\subset \Omega=\{1,\ldots,n\}$, then set $\mu(A)=\frac{\vert A\vert}{n}$, the normalized size of $A$. If we have a permutation $\sigma_k\in S_n$ with support $A$ and we wish smaller support, then we can use $\sigma_{k+1}=[\sigma_k,\sigma_k^\tau]$, which has support at most $3\vert A\cap A^\tau\vert$. If $\mu(A)=p$ then $E(\mu(A\cap A^\tau))=p^2$, with $\tau$ random in a transitive group. Thus replacing $\sigma$ by $[\sigma,\sigma^\tau]$ changes our proportion from $p$ to $3p^2$. Iterating, we get about $\mathop{\rm supp}\sigma_k=(3p)^{2^k}$, which quickly tends to 0 if $3p<1$. If $3p$ is bounded away from $1$, then in about $\log\log n$ steps this will hit $\frac1n$.

If $\sigma_{k+1}=[\sigma_{k},\sigma_{k}^\tau]$ and $b_k$ is the word length of $\sigma_{k}$, then $b_{k+1}=4b_k+n^c$, as the random $\tau$ has word length $n^c$. This gives $b_k\sim n^c5^k=n^c\log^c n$, which is ``quasi-polynomial'' and certainly bounded by $n^{c+\varepsilon}$.

But there is a danger that $A$ and $A^\tau$ will commute (especialy when $\vert A\vert$ is small; then $A$ and $A^{\tau}$ are likely to be disjoint).

Thus our goal is to obtain $\tau$ such that $\tau^{-1}$ keeps $x$ in the support, sends $y=x^\sigma$ out of the support, and makes $A\cap A^\tau$ small. This requires triple transitivity. We do a random walk on $\Omega^{(3)}$, the space of ordered triples with no repetition, with edges labeled by generators of our group. This graph is strongly connected by triple transitivity. After $N^c$ (now $N=n(n-1)(n-2)$) steps, the distribution of vertices will be nearly random: a random word of length $N^c$ sends a given vertex to any other vertex with probability $\frac{1\pm\varepsilon}{N}$. With probability $\frac{1\pm \varepsilon}{n(n-1)}$ it sends a given $x'$ (in $A$) to $x$ and a given $y'$ (not in $A$) to $y$. Conditioned on this, it still sends any other $z'$ to $z$ with probability $\frac{1\pm\varepsilon}{n-2}$, so by linearity of expectation, we still have the expected value of $\vert A\cap A^\tau\vert$, conditioned on $x'\mapsto x$ and $y'\mapsto y$ as $\frac{1}{n}+\frac{(\vert A\vert-2)^2}{n-2}(1\pm\varepsilon)$, which means that the proportion of $\Omega$ in the overlap is approximately the square of the proportion of $A$.