SEMINARIO Probabilita'

Sam Thomas (Cambridge, UK)

Titolo: Cutoff for Random Walk on Random Cayley Graphs

Lunedi' 02 Settembre 2019 ORE 14:30

Dipartimento di Matematica e Fisica Universita' degli Studi Roma Tre Largo San Leonardo Murialdo,1 - Pal.C - Aula 211

Abstract Consider the random Cayley graph of a finite group $G$ with respect to $k$ generators chosen uniformly at random, with $1 ll log k ll log|G|$: the vertices are the group elements, and $g,h in G$ are connected if there exists a generator $z$ so that $g = hz$ or $gz = h$. A conjecture of Aldous and Diaconis asserts that the simple random walk on this graph exhibits cutoff, at a time which depends only on $|G|$ and $k$, not on the algebraic structure of the group $G$ (ie universally in $G$). We verify this conjecture for a wide class of Abelian groups. Time permitting, we discuss extensions to the case where the underlying group $G$ is non-Abelian. There the cutoff time cannot be written only as a function of $|G|$ and of $k$; it depends on the algebraic structure. This is joint work with Jonathan Hermon.