Skip to content Skip to navigation

Random Cayley graphs

Monday, May 11, 2020 - 4:00pm

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:

  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.