Cutoff for Random Walk on Random Cayley Graphs

With Sam Thomas (Statslab)

Cutoff for Random Walk on Random Cayley Graphs

Consider the random Cayley graph of a finite group G with respect to k generators chosen uniformly at random, with 1 << log k << 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.

Joint work with Jonathan Hermon

Add to your calendar or Include in your list

The latest CCIMI seminar took place earlier this week with an engaging talk from Silvia Gazzola from @MathsatBath.… View on Twitter