On the diameter of Cayley graphs of the symmetric group (Q1105690): Difference between revisions

It is conjectured that there exists a constant C such that for every nonabelian simple group G, every Cayley graph of G has diameter at most \((\log_ 2| G|)^ C\). As a first step toward its proof, it is shown that if G is either \(S_ n\) or \(A_ n\), then every Cayley graph of G has diameter at most \(\exp[(n \ln n)^{1/2}(1+o(1))]\). A concluding section surveys known upper bounds for the diameters of Cayley graphs \(\Gamma(G,S)\) of the group G when all or some of the generating sets are subject to given conditions.