×

zbMATH — the first resource for mathematics

Small-diameter Cayley graphs for finite simple groups. (English) Zbl 0702.05042
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.
Reviewer: M.E.Watkins

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20D06 Simple groups: alternating groups and groups of Lie type
20F05 Generators, relations, and presentations of groups
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96, (1986) · Zbl 0661.05053
[2] Alon, N.; Milman, V.D., Λ_{1}, isoperimetric inequalities for graphs, and superconcentrators, J. comb. theory. ser. B, 38, 73-88, (1985) · Zbl 0549.05051
[3] Babai, L.; Erdös, P., Representation of group elements as short products, in theory and practice of combinatorics, (), 27-30
[4] L. Babai and A. Seress, On the diameter of Cayley graphs of symmetric groups, J. Comb. Theory. Ser. A (to appear). · Zbl 0649.20002
[5] Brooks, R., The spectral geometry of a tower of coverings, J. diff. geom., 23, 97-107, (1986) · Zbl 0576.58033
[6] Brooks, R., Combinatorial problems in spectral geometry, in curvature and topology of Riemannian manifolds, (), 14-32
[7] Carter, R., Simple groups of Lie type, (1972), John Wiley Chichester · Zbl 0248.20015
[8] Chavel, I., Eigenvalues in Riemannian geometry, (1984), Academic Press London
[9] Gates, W.H.; Papadimitriou, C.H., Bounds for sorting by prefix reversal, Disc. math., 27, 47-57, (1979) · Zbl 0397.68062
[10] Lubotzky, A.; Phillips, R.; Sarnak, P., (), 240-246
[11] Lubotzky, A.; Phillips, R.; Sarnak, P., Ramanujan graphs, Combinatorica, 8, 261-277, (1988) · Zbl 0661.05035
[12] Margulis, G.A., Graphs without short cycles, Combinatorica, 2, 71-78, (1982) · Zbl 0492.05044
[13] G. A. Margulis, Arithmetic groups and graphs without short circuits (Russian; to appear).
[14] Preparata, F.; Vuillemin, J., The cube-connected cycles: a versatile network for parallel computation, Commun. ACM, 24, 300-309, (1981)
[15] Selberg, A., On the estimation of Fourier coefficients of modular forms, AMS proc. symp. pure math., 8, 1-15, (1965)
[16] Steinberg, R., Generators for simple groups, Can. J. math., 14, 277-283, (1962) · Zbl 0103.26204
[17] Stone, H.S., Parallel processing with the perfect shuffle, IEEE trans. comput, C-20, 153-161, (1971) · Zbl 0214.42703
[18] Suzuki, M., On a class of doubly transitive groups, I. ann. math, 75, 105-145, (1962) · Zbl 0106.24702
[19] Tits, J., LES groupes simples de Suzuki et ree, Sem. bouraki, 210, (1960) · Zbl 0267.20041
[20] Ward, H.N., On Ree’s series of simple groups, Trans. AMS, 121, 62-89, (1966) · Zbl 0139.24902
[21] Weil, A., Sur LES courbes algebriques et LES varietes que s’en d6duisent, Act. sci. ind, 1041, (1948) · Zbl 0036.16001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.