On the diameter of Cayley graphs of the symmetric group

DOI10.1016/0097-3165(88)90033-7MaRDI QIDQ1105690zbMATH OpenOpenAlexFDO

Authors László Babai, Ákos Seress

Publication date 1988

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(88)90033-7

zbMATH Keywords

alternating groupCayley graphsdiameterssymmetric group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Subgroups of symmetric groups (20B35) Representations of finite symmetric groups (20C30) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

Review text

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.

Recommendations

• Bounds on the diameter of Cayley graphs of the symmetric group
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• Some results on diameters of Cayley graphs
• Diameters of Cayley graphs of Chevalley groups
• scientific article; zbMATH DE number 1375161
• scientific article; zbMATH DE number 1774953
• On diameter two Cayley graphs
• The diameter of power graphs of symmetric groups
• On the diameter and bisector size of Cayley graphs

Cites work

• Computing short generator sequences
• scientific article; zbMATH DE number 3137403 (Why is no real title available?)
• scientific article; zbMATH DE number 3032896 (Why is no real title available?)
• On the degree of transitivity of permutation groups: A short proof
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• Permutations of bounded degree generate groups of polynomial diameter
• Small-diameter Cayley graphs for finite simple groups
• The Probability of Generating the Symmetric Group
• The probability of generating the symmetric group
• The probability of generating the symmetric group

Cited in

(56)

• Vertex reconstruction in Cayley graphs
• On the diameter of permutation groups
• Processor interconnection networks from Cayley graphs
• On the diameter of a Cayley graph of a simple group of Lie type based on a conjugacy class
• On the diameter of a graph related to p-regular conjugacy classes of finite groups
• The correct diameter of trivalent Cayley graphs.
• Some Cayley graphs for simple groups
• Diameters of Chevalley groups over local rings.
• Diameters of random Cayley graphs of finite nilpotent groups
• On short expressions for cosets of permutation subgroups
• Conjugation diameter of the symmetric groups
• Logarithmic diameter bounds for some Cayley graphs
• On groups with unbounded Cayley graphs
• On the spectral gap and the diameter of Cayley graphs
• The Weisfeiler-Leman algorithm and the diameter of Schreier graphs
• Diameters of Cayley graphs generated by transposition trees
• On the diameter of permutation groups.
• Applications of character estimates to statistical problems for symmetric group
• Some results on diameters of Cayley graphs
• Probabilistic and asymptotic aspects of finite simple groups.
• Growth in SL2 over finite fields
• Poly-log diameter bounds for some families of finite groups
• On the generating graph of direct powers of a simple group.
• scientific article; zbMATH DE number 1375161 (Why is no real title available?)
• Bounds on the diameter of Cayley graphs of the symmetric group
• scientific article; zbMATH DE number 1229603 (Why is no real title available?)
• scientific article; zbMATH DE number 1245638 (Why is no real title available?)
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• Diameter of a direct power of a finite group
• The diameter of power graphs of symmetric groups
• Short laws for finite groups and residual finiteness growth
• Uniform diameter bounds for some families of Cayley graphs
• On the automorphism groups of strongly regular graphs. II.
• Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group
• The Diameter of a Conjugacy Class Graph of Finite Groups
• The diameter of products of finite simple groups
• Diameters of graphs of reduced words and rank-two root subsystems
• Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
• The girth of Cayley graphs over Sylow 2-subgroups of the symmetric groups \(S_{2^n}\) with diagonal bases
• An improved diameter bound for finite simple groups of Lie type
• Growth in groups: ideas and perspectives
• On the diameter and bisector size of Cayley graphs
• On the strictness of a bound for the diameter of Cayley graphs generated by transposition trees
• Diameters of finite simple groups: sharp bounds and applications
• A sum-bracket theorem for simple Lie algebras
• The unitary Cayley graph of a semiring
• Fundamental groups and group presentations with bounded relator lengths
• Diameter search algorithms for directed Cayley graphs
• On the diameter of Cayley graphs of classical groups with generating sets containing a transvection
• Upper bounds for the diameter of a direct power of non-abelian solvable groups
• The directed Cayley diameter and the Davenport constant
• Almost-Ramanujan expanders from arbitrary expanders via operator amplification
• Connectivity labeling in faulty colored graphs
• Nilprogressions and groups with moderate growth
• Small-diameter Cayley graphs for finite simple groups
• Some problems on Cayley graphs

This page was built for publication: On the diameter of Cayley graphs of the symmetric group

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1105690)