Random Cayley graphs
We consider the random Cayley graph of a finite group G formed by picking k random generators uniformly at random:
(1) We prove universality of cutoff (for the random walk) and a concentration of measure phenomenon in the Abelian setup (namely, that all but $o(|G|)$ elements lie at distance $\in [R-o(R),R+o(R)]$ from the origin, where R is the minimal ball in $\mathbb{Z}^k$ of size at least $|G|$), provided $k-d(G)\gg 1$ where $d(G)$ is the size of the smallest generating set of G. As conjectured by Aldous and Diaconis, the cutoff time is typically independent of the algebraic structure (it is given by the time at which the entropy of a random walk on $\mathbb{Z}^k$ is $\log |G|$).
(2) We prove analogous results for the Heisenberg $H_{p,d}$ groups of $d \times d$ uni-upper triangular matrices with entries defined mod p, for p prime and d fixed or diverging slowly.
(3) Lastly, we resolve a conjecture of D. Wilson that if G is a group of size at most $2^d$ then for all k the mixing time of random walk on a Cayley graph of G with k random generators is as rapid as that of $\mathbb{Z}_2^d$ and likewise.
(Joint work with Sam Thomas.)