Phase transition for cutoff on graphs with an added weighted random matching

Link to Join MS Teams Talk

This talk will be broadcast at 15:00 GMT 13th December on MS Teams only.

Meeting ID: 393 527 089 878
Passcode: dsm7py

Abstract

Lately there is an increasing interest in studying the mixing properties of (random walks on) random graphs. In particular there has been multiple results showing that some given random graph model exhibits the cutoff phenomenon.

We consider a model that only has a little bit of randomness: we consider some sequence $(G_n)$ of given base graphs and for each $G_n$ we add the edges of a uniform random matching with a weight $\varepsilon_n$, obtaining a weighted random graph $G_n^*$.

For $\varepsilon_n\equiv 1$ it has been shown that this added randomness is sufficient to ensure cutoff. For $\varepsilon_n\equiv0$ we clearly haven’t done anything to our graphs, so $(G_n^*)$ has cutoff if and only if $(G_n)$ does. But what happens in-between? How quickly can we let $\varepsilon_n$ tend to 0 so that it still guarantees cutoff?

For a wide range of base graphs $(G_n)$ we are able to answer this question.

This is joint work with Jonathan Hermon, Andjela Sarkovic, and Perla Sousi.

About Zsuzsa

Zsuzsa is currently a third year PhD student at the University of Cambridge, under the supervision of Perla Sousi.