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, provided $k-d(G) >> 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 $Z^k$ is $\log |G|$). 
2. We prove analogous results for the Heisenberg groups  of  $d\times d$ uni-upper triangular matrices with entries defined $\mod p$, for $p$ prime.
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 $Z_2^d$.

This is based on joint work with Sam Thomas.

Zoom Seminar Link