Small-diameter Cayley graphs for finite simple groups (Q914696): Difference between revisions

Given a finite group G and a generating set S of G, the Cayley graph \(\Gamma\) (G,S) has vertex set G and edge set \(\{\{\) g,sg\(\}\) : \(g\in G\); \(s\in S\cup S^{-1}\}\). Let diam \(\Gamma\) (G,S) denote the least integer d such that every element of G can be expressed as a word of length \(\leq d\) with letters in \(S\cup S^{-1}\). It is shown that there exists a constant C such that every noncyclic finite simple group G is generated by a set S with \(| S| \leq 7\) for which diam \(\Gamma\) (G,S) is at most C \(\log_ 2| G|.\) The authors believe that one could impose \(| S| =2\). They prove that the alternating group \(A_ n\) is generated by a 2-element set S such that diam \(\Gamma\) (A\({}_ n,S)=O(n \log n)\). A 2-element set S is given such that diam \(\Gamma\) (PSL(2,q),S)\(=O(\log q)\) when q is prime, but the authors' methods do not suffice when q is a prime power.