Diámetro del grupo simétrico

Question

Deje $\Sigma_n\subset G$ ser un conjunto de generadores del grupo simétrico $S_n$. Es bien conocida conjetura de que el diámetro del grafo de Cayley $\Gamma(S_n,\Sigma_n)$ es en la mayoría de las $n^C$ para algunos absoluta constante $C$. (El diámetro del grafo de Cayley es sólo el máximo de $\ell(g)$ para $g\in S_n$ donde $\ell(g)$ es la longitud de la menor palabra en $A \cup A^{-1}$ igual a $g$.)

Para $\Sigma_n$ fijas tamaño, el diámetro no puede ser menos que un número constante de veces $\log |S_n|$, es decir, un número constante de veces $n\log n$.

Es claro y conocido que, para $\Sigma_n = \{(1 2),(1 2 \dotsb n)\}$, el diámetro de $\Gamma(S_n, \Sigma_n)$ está a menos de una constante por $n^2$. (También es en la mayoría de los que.)

Hay ejemplos de grupos electrógenos $\Sigma_n$ para que el diámetro es mayor que $n^{2+\epsilon}$ por cada (o infinitas) $n$? Mayor que $n^2 (\log n)^A$ para algunos $A>0$ y una infinidad de $n$?

Answer 1

Lo que sigue es una respuesta incompleta. Yo estoy en el medio de bosques rusos, así que preferiría tener a alguien hacer un seguimiento de todos los árbitros, etc. pero mirando en la recompensa de la fecha de caducidad decidido que vale la pena afirmando lo que se conoce.

La respuesta es NO a todo, pero eso es una conjetura no es un teorema. He visto esta conjetura dicho varias veces en diversas formas, aquí hay dos que me parece interesante:

1) el diámetro de cada conectado Cayley gráfico de $\Gamma$ a $S_n$ es $O(n^2)$,

2) para cada S(1) los generadores de $S_n$, el tiempo de mezcla del vecino más cercano r.w. en el correspondiente grafo de Cayley $\Gamma$ es $O(n^3\log n)$.

Desde el tiempo de mezcla es mayor que el diámetro, la segunda implica también un límite en el diámetro así. La segunda conjetura fue declarado por Diaconis y Saloff-Coste en algún lugar, y es también agudo para una transposición y de ciclo largo como en la pregunta (ver Saloff-Coste de la encuesta). La primera conjetura es una fecha de folclore y el recuerdo de la lectura en distintos lugares; aparece por ejemplo en este papel (p. 425) por Gamburd y a mí.

ACTUALIZACIÓN
Ver este artículo reciente Diaconis ("Algunas de las cosas que hemos aprendido..", 2012), donde se reitera la conjetura 2) en la Pregunta 2 sobre p.9.