On the diameter of permutation groups (Q1197618)

The authors give an asymptotic universal upper bound for the diameter of all Cayley graphs of all permutation groups of degree \(n\), namely, they show that for any set of permutations \(S\) in \(S_ n\), every permutation in the subgroup generated by \(S\) can be expressed as a product of length at most \(\exp((n\cdot\ln n)^{1/2}(1+o(1)))\) of factors belonging to \(S\cup S^{-1}\). This estimate is the best possible, since by an old result of Landau the same asymptotics holds for the largest order of an element in \(S_ n\). In an earlier paper [J. Comb. Theory, Ser. A 49, 175-179 (1988; Zbl 0649.20002)] the authors proved the same upper bound for the diameter of all Cayley graphs of \(S_ n\) and \(A_ n\). However, they conjecture that in fact the diameter of any Cayley graph of \(A_ n\) is less than \(n^ C\) for some absolute constant \(C\). This would imply a considerable improvement for transitive groups, since another result of the present paper asserts that the diameter of Cayley graphs of transitive groups is less than \(\exp(C\cdot\ln^ 3 n)\cdot \text{diam}(A_ m)\), where \(C\) is an absolute constant and \(m\) is the degree of the greatest alternating composition factor of the group in question. For the proof the authors develop a quite complex ``asymptotic structure theorem'' for permutation groups. In order to prove the estimates, some consequences of the classification of finite simple groups are invoked. Remark: The statement of Proposition 3.2 holds only for nonabelian composition factors \(G_{i-1}/G_ i\). However, the proofs using this proposition carry through with a trivial modification; all other statements remain correct as stated.