2
$\begingroup$

This post is a sequel of Diameter of symmetric group.

Let $\Sigma$ a generating subset of $S_n$, $\Gamma(S_n, \Sigma)$ the Cayley graph and $d_{\Sigma}$ the diameter of $\Gamma(S_n, \Sigma)$.
Let $s_n = min_{\Sigma}(\vert \Sigma \vert \times d_{\Sigma})$.

Question: What's the asymptotic of $s_n$ (or the best conjecture for that)?

$\endgroup$
3
  • 1
    $\begingroup$ It's related but not really a sequel to the linked post. That post concerns the issue of the max over all generating subset, which is conjecturally polynomial. Here you consider the min, which, to make the question nontrivial, you multiply with the size $d$ of the generating subset. Clearly the diameter should be $\succeq\log_d(|G|)$, which means here $\succeq n\log_d(n)$. I think it's known that a random pair in $S_n\times (S_n-A_n)$ generates $S_n$ with diameter $\preceq\log(|G|)\simeq n\log n$. This means that $s_n\simeq n\log n$. $\endgroup$
    – YCor
    Jun 28, 2015 at 9:38
  • 1
    $\begingroup$ @YCor: $n \log(n)$ is not known for random pairs. The best bound is $Cn^2(\log(n))^c)$ -- by work of Helfgott, Seress and Zuk. $\endgroup$ Jun 28, 2015 at 10:33
  • $\begingroup$ OK, I maybe I need expanders instead of just random pairs, and this gives diameter $|\log S_n|\simeq n\log n$ for generating subsets of bounded size. It's done in this paper by Kassabov ams.org/journals/era/2005-11-06/S1079-6762-05-00146-0/… $\endgroup$
    – YCor
    Jun 28, 2015 at 10:34

1 Answer 1

5
$\begingroup$

For a generating subset $S\subset S_n$ of size $d$, the $n$-ball has size $\le (2d)^n$, which implies that the diameter $D(S)$ satisfies $D\ge\log_{2d}(n!)\simeq n\log n$.

So $|S|D(S)\ge \frac{d}{\log d}\log(n!)\ge \log(n!)\sim n\log n$, and thus $s_n=\min_S |S|D(S)\succeq n\log n$.

This is attained, according to Theorem 7 in this paper by Kassabov, which implies that there exists $\ell$ and generating subsets $F_n\subset S_n$ with $D(F_n)\preceq n\log n$ and $|F_n|\le \ell$, implying $s_n\preceq n\log n$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.