On the diameter of permutation groups

Details On the diameter of permutation groups On the diameter of permutation groups

2011-09-16

arxiv.org/abs/1109.3550v2

Mathematics

Group Theory

36 pages; shorter abstract and minimal changes; submitted

Scientific paper

Given a finite group $G$ and a set $A$ of generators, the diameter $\diam(\Gamma(G,A))$ of the Cayley graph $\Gamma(G,A)$ is the smallest $\ell$ such that every element of $G$ can be expressed as a word of length at most $\ell$ in $A \cup A^{-1}$. We are concerned with bounding $\diam(G):= \max_A\diam(\Gamma(G,A))$. It has long been conjectured that the diameter of the symmetric group of degree $n$ is polynomially bounded in $n$, but the best previously known upper bound was exponential in $\sqrt{n \log n}$. We give a quasipolynomial upper bound, namely, \[\diam(G) = \exp(O((\log n)^4 \log\log n)) = \exp((\log \log |G|)^{O(1)})\] for $G = \Sym(n)$ or $G = \Alt(n)$, where the implied constants are absolute. This addresses a key open case of Babai's conjecture on diameters of simple groups. By standard results, our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree $n$.

Affiliated with

Also associated with

No associations

Rating

On the diameter of permutation groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the diameter of permutation groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the diameter of permutation groups will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-534530