The diameter of a random Cayley graph of Z_q

DOI10.1515/GCC.2010.004MaRDI QIDQ3585197zbMATH OpenOpenAlexFDO

Authors Gideon Amir, Ori Gurel-Gurevich

Publication date 19 August 2010

Published in Groups - Complexity - Cryptology (Search for Journal in Brave)

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

zbMATH Keywords

Cayley graphrandom graphsrandom random walks

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)

Abstract: Consider the Cayley graph of the cyclic group of prime order q with k uniformly chosen generators. For fixed k, we prove that the diameter of said graph is asymptotically (in q) of order q^(1/k). The same also holds when the generating set is taken to be a symmetric set of size 2k.

Recommendations

• The thresholds for diameter 2 in random Cayley graphs
• Random Cayley digraphs of diameter 2 and given degree
• The diameters of almost all Cayley digraphs
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• Diameters of random Cayley graphs of finite nilpotent groups

Cites work

• A survey of results on random random walks on finite groups
• On random random walks
• Random Cayley graphs and expanders
• Random walks supported on random points of Z/nZ

Cited in

(11)

• Diameters of random Cayley graphs of finite nilpotent groups
• Asymptotic metric behavior of random Cayley graphs of finite abelian groups
• Diameters of random circulant graphs
• The range of thresholds for diameter 2 in random Cayley graphs
• The thresholds for diameter 2 in random Cayley graphs
• The diameters of almost all bi-Cayley graphs
• Random walks, bisections and gossiping in circulant graphs
• Girth, words and diameter
• Random Cayley digraphs of diameter 2 and given degree
• Geometry of random Cayley graphs of abelian groups
• Effective joint equidistribution of primitive rational points on expanding horospheres

This page was built for publication: The diameter of a random Cayley graph of \({\mathbb{Z}}_q\)

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