On the girth of random Cayley graphs

DOI10.1002/rsa.20266zbMath1230.05156arXiv0707.1833OpenAlexW2953254115MaRDI QIDQ3055767

Shlomo Hoory, Mehrdad M. Shahshahani, Aner Shalev, Alexander Gamburd, Bálint Virág

Publication date: 9 November 2010

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0707.1833

zbMATH Keywords

randomCayley graphsgirth

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Paths and cycles (05C38) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items

Diophantine properties of nilpotent Lie groups, Cutoff on graphs and the Sarnak-Xue density of eigenvalues, Learning loopy graphical models with latent variables: efficient methods and guarantees, Thin \(\text{II}_1\) factors with no Cartan subalgebras, On sensitivity in bipartite Cayley graphs, A randomized construction of high girth regular graphs, On regular hypergraphs of high girth, First-order limits, an analytical perspective, Growth and expansion in algebraic groups over finite fields, Suzuki groups as expanders., Short laws for finite groups and residual finiteness growth, Regular graphs of large girth and arbitrary degree, Expansion, random walks and sieving in \(SL_2({\mathbb{F}_p}[t)\)], Diophantine approximation on matrices and Lie groups, High-dimensional structure estimation in Ising models: local separation criterion, Approximate subgroups of linear groups., The spectrum of the random environment and localization of noise, The girth of Cayley graphs over Sylow 2-subgroups of the symmetric groups S2n with diagonal bases, Girth, words and diameter, On the shortest identity in finite simple groups of Lie type, Quantum Chaos on Random Cayley Graphs of SL 2[Z/pZ], Expander graphs in pure and applied mathematics, Expansion of coset graphs of \(\mathrm{PSL}_2(\mathrm{F}_p)\), About the length of laws for finite groups

Cites Work

• On free subgroups of semi-simple groups
• Explicit construction of regular graphs without small cycles
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Note on the girth of Ramanujan graphs
• Word maps, conjugacy classes, and a noncommutative Waring-type theorem.
• The sextet construction for cubic graphs
• Explicit constructions of graphs without short cycles and low density codes
• Spectra of elements in the group ring of SU(2)
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• Word maps have large image.
• The probability of generating a finite simple group
• Almost all subgroups of a Lie group are free
• Dimension and randomness in groups acting on rooted trees
• On the probability of satisfying a word in a group
• Projective Reed-Muller codes
• Random Cayley graphs and expanders
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• A new series of dense graphs of high girth
• Varieties and simple groups
• Residual properties of free groups and probabilistic methods
• GROUP LAWS AND FREE SUBGROUPS IN TOPOLOGICAL GROUPS
• Diophantine properties of elements of \(SO(3)\)
• Unnamed Item
• Unnamed Item