Geometry of Random Cayley Graphs of Abelian Groups

Consider the random Cayley graph of a finite Abelian group $G$ with respect to $k$ generators chosen uniformly at random, with $1\ll \log k\ll \log \mathrm{\mid }G\mathrm{\mid }$. Draw a vertex $U\sim \mathrm{Unif}(G)$. We show that the graph distance $\mathrm{dist}(\mathsf{i}\mathsf{d},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 $\mathrm{\mid }G\mathrm{\mid }$, under mild conditions. In other words, the distance from the identity for all but $o(\mathrm{\mid }G\mathrm{\mid })$ of the elements of $G$ lies in the interval $[M-o(M),M+o(M)]$. In the regime $k\gtrsim \log \mathrm{\mid }G\mathrm{\mid }$, 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 $\mathrm{\mid }G\mathrm{\mid }$, 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 $\mathrm{\mid }G{\mathrm{\mid }}^{-2\mathrm{/}k}$ when $k-d(G)\asymp k$ and $\mathrm{\mid }G\mathrm{\mid }$ lies in a density-$1$ subset of $\mathbb{N}$ or when $k-2d(G)\asymp k$. 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.