Cutoff for Random Walk on Random Cayley Graphs

Add to your list(s) Download to your calendar using vCal

• Sam Thomas (Statslab)
• Tuesday 22 October 2019, 14:00-15:00
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB.

If you have a question about this talk, please contact Perla Sousi.

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

This talk is part of the Probability series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• DPMMS Lists
• DPMMS info aggregator
• DPMMS lists
• Hanchen DaDaDash
• Interested Talks
• MR12, CMS, Wilberforce Road, Cambridge, CB3 0WB
• Probability
• School of Physical Sciences
• Statistical Laboratory info aggregator
• bld31

Note that ex-directory lists are not shown.