Probabilita' Cutoff for Random Walk on Random Cayley Graphs Sam Thomas 02-09-2019 - 14:30 Largo San Leonardo Murialdo,1 - Pal.C - Aula 211
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 |