Seminari del Dipartimento



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
org: CAPUTO Pietro

Copyright© 2014 Dipartimento di Matematica e Fisica