Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
Nice question. What is the reference for "well-known conjecture" ? –  Alexander Chervov Jul 20 '12 at 12:57
1  
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? –  Mark Sapir Jul 21 '12 at 17:03
3  
@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$.) –  Derek Holt Jul 22 '12 at 21:53
2  
Regarding the recent exchange, I cannot resist mentioning mathoverflow.net/questions/23989 (Sorry for the off-topic.) –  quid Jul 24 '12 at 12:59
2  
@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.... –  Alexander Chervov Jul 24 '12 at 20:20
show 5 more comments

1 Answer

up vote 11 down vote accepted

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.

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

share|improve this answer
1  
Thank you. Could you add the references when you are back? Say hi to Ivan Susanin. –  H A Helfgott Jul 30 '12 at 13:28
    
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.) –  H A Helfgott Jul 31 '12 at 10:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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