Geometry of random Cayley graphs of abelian groups

DOI10.1214/22-AAP1899MaRDI QIDQ6146786zbMATH OpenFDO

Authors Jonathan Hermon, Sam Olesker-Taylor

Publication date 15 January 2024

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.02801, https://projecteuclid.org/journals/annals-of-applied-probability/volume-33/issue-5/Geometry-of-random-Cayley-graphs-of-Abelian-groups/10.1214/22-AAP1899.full

zbMATH Keywords

diameterrandom Cayley graphsrelaxation timespectral gaptypical distance

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Expander graphs (05C48) Random graphs (graph-theoretic aspects) (05C80) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15) Processes in random environments (60K37)

Abstract: Consider the random Cayley graph of a finite Abelian group $G$ with respect to $k$ generators chosen uniformly at random, with $1lllogklllog|G|$. Draw a vertex $UsimoperatornameUnif(G)$. We show that the graph distance $operatornamedist(mathsfid,U)$ from the identity to $U$ concentrates at a particular value $M$, which is the minimal radius of a ball in $mathbb{Z}^k$ of cardinality at least $|G|$, under mild conditions. In other words, the distance from the identity for all but $o(|G|)$ of the elements of $G$ lies in the interval $[M-o(M),M+o(M)]$. In the regime $kgtrsimlog|G|$, we show that the diameter of the graph is also asymptotically $M$. In the spirit of a conjecture of Aldous and Diaconis (1985), this $M$ depends only on $k$ and $|G|$, not on the algebraic structure of $G$. Write $d(G)$ for the minimal size of a generating subset of $G$. We prove that the order of the spectral gap is $|G{|}^{-2/k}$ when $k-d(G)asympk$ and $|G|$ lies in a density-$1$ subset of $mathbbN$ or when $k-2d(G)asympk$. This extends, for Abelian groups, a celebrated result of Alon and Roichman (1994). The aforementioned results all hold with high probability over the random Cayley graph.

Recommendations

• The diameter of a random Cayley graph of \({\mathbb{Z}}_q\)
• The thresholds for diameter 2 in random Cayley graphs
• Asymptotic metric behavior of random Cayley graphs of finite abelian groups
• Random Cayley digraphs of diameter 2 and given degree
• Random Cayley graphs and expanders

Cites work

• Asymptotic metric behavior of random Cayley graphs of finite abelian groups
• Cayley graphs without a bounded eigenbasis
• Cutoff on all Ramanujan graphs
• Diameter of Ramanujan graphs and random Cayley graphs
• Diameters of random Cayley graphs of finite nilpotent groups
• Diameters of random circulant graphs
• Enumeration and random walks on finite groups
• Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales
• scientific article; zbMATH DE number 2159656 (Why is no real title available?)
• scientific article; zbMATH DE number 1405807 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing and cut-off in cycle walks
• Nilprogressions and groups with moderate growth
• On random random walks
• On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs
• Probability on trees and networks
• Random Cayley digraphs of diameter 2 and given degree
• Random Cayley graphs and expanders
• Random Cayley graphs are expanders: a simple proof of the Alon-Roichman theorem
• Random random walks on \(\mathbb{Z}_2^d\)
• Random walks supported on random points of Z/nZ
• Shuffling Cards and Stopping Times
• Simple proofs of two results on convolutions of unimodal distributions
• Small-Bias Sets for Nonabelian Groups
• The diameter of a random Cayley graph of \({\mathbb{Z}}_q\)

Cited in

(2)

• Random balanced Cayley complexes
• Spectral gap of nonreversible Markov chains

This page was built for publication: Geometry of random Cayley graphs of abelian groups

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