Speaker: Jonathan Hermon, University of British Columbia, Canada
Abstract: We consider the random Cayley graph of a finite group $G$ formed by picking $k$ random generators uniformly at random:
- 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|$).
- We prove analogous results for the Heisenberg groups of $d\times d$ uni-upper triangular matrices with entries defined $\mod p$, for $p$ prime.
- 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.