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

  • 2
    $\begingroup$ Nice question. What is the reference for "well-known conjecture" ? $\endgroup$ Jul 20 '12 at 12:57
  • 1
    $\begingroup$ How about the set $a,a^qb$ where $a$ is an $n$-cycle, $b=(1,2)$, $n$ is a prime $q\approx n/2$? It is a generating set of $S_n$. What is the diameter? $\endgroup$
    – user6976
    Jul 21 '12 at 17:03
  • 3
    $\begingroup$ @Mark: For $n \le 10$, which is as far as I can go with a simple-minded brute force computer calculation, the diameter with your proposed generators is less than with $a,b$. For $n=10$ and generators $a,a^5b$, the diameter is 32, whereas with $a,b$ it is 45. (I believe it is $n(n+1)/2$ in general for $a,b$.) $\endgroup$
    – Derek Holt
    Jul 22 '12 at 21:53
  • 2
    $\begingroup$ Regarding the recent exchange, I cannot resist mentioning mathoverflow.net/questions/23989 (Sorry for the off-topic.) $\endgroup$
    – user9072
    Jul 24 '12 at 12:59
  • 2
    $\begingroup$ @Harold Helfgott I posted links for sake of other users. Appreciate your humbleness but I would prefer if you include links on yours papers in question.... $\endgroup$ Jul 24 '12 at 20:20

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). The first conjecture is a dated folklore and I remember reading it in various places; it appears e.g. in this paper (p. 425) by Gamburd and me.

See this recent paper by Diaconis ("Some things we've learned..", 2012) where he reiterates conjecture 2) in Question 2 on p.9.

  • 1
    $\begingroup$ Thank you. Could you add the references when you are back? Say hi to Ivan Susanin. $\endgroup$ Jul 30 '12 at 13:28
  • $\begingroup$ PS. What is known about the mixing time of a random pair of generators? (There are direct consequences on this from work on the diameter for a random pair of generators (Babai-Hetyei, Babai-Hayes); in particular, we do have a polynomial bound. I wonder whether there are bounds going further than that.) $\endgroup$ Jul 31 '12 at 10:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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