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.