You are here

Geometric Functional Analysis and Probability Seminar

ThursdaySep 26, 201913:30
Geometric Functional Analysis and Probability SeminarRoom 155
Speaker:Jonathan Hermon Title:Random Cayley graphsAbstract:opens in new windowin html    pdfopens in new window

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 \gg 1$ is large in terms of

$\mathrm{rank}(G)$. As conjectured by Aldous and Diaconis, the cutoff time is 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 its mixing time in this model is as rapid as that of $\mathbb{Z}_2^d$ and likewise, that the slowest mixing $p$-group of a given size is $\mathbb{Z}_p$.

(Joint work with Sam Thomas.)