Phase transition for cutoff for random walks on random graphs

In this thesis, we analyse the cutoff phenomenon on two different random graph models. First, we consider a variant of the configuration model with an embedded community structure and study the mixing properties of a simple random walk on it. Every vertex has a given number of internal, degint ≥ 3, and outgoing, degout, half-edges. Given a stochastic matrix Q, we pick a random perfect matching of the half-edges subject to the constraint that each vertex v has degint(v) neighbours inside its community and the proportion of outgoing half-edges from community i matched to a half-edge from community j is Q(i,j). Assuming the number of communities is constant and that they all have comparable sizes, we prove the following dichotomy: a simple random walk on the resulting graph exhibits cutoff if and only if the product of the Cheeger constant of Q and log n (where n is the number of vertices) diverges. In [5], Ben-Hamou established a dichotomy for cutoff for a non-backtracking random walk on a similar random graph model with 2 communities. We prove that the same characterisation of cutoff holds for a simple random walk. In the second part of the thesis, we analyse a graph G* obtained from a finite deterministic graph G = (V,E) by considering a random perfect matching of V and adding the corresponding edges to G with weight ε, while assigning weight 1 to the original edges of G. For various sequences of graphs Gn and corresponding weights εn, we establish if the (weighted) random walk on G*n has cutoff. In particular, we show a phase transition for two families of graphs, graphs with polynomial growth of balls, and graphs where the entropy of the simple random walk grows linearly up to the time of order log|Vn|. These include in particular tori, expander families and locally expanding families. We also show that this phase transition is sharp in the case of expander graphs and vertex transitive graphs with polynomial growth of balls.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2023

Author dc:creator

• Šarković, Andela

Advisor dc:contributor.advisor

• Sousi, Perla

• cutoff
• entropy
• mixing time
• random graphs

Licence

• https://www.repository.cam.ac.uk/bitstreams/6504934c-653b-466b-b338-21cd32e0f2f3/download
• https://www.rioxx.net/licenses/all-rights-reserved/

Language dc:language

eng

DOI dc:identifier.doi

https://doi.org/10.17863/CAM.108327

OAI identifier oai:identifier

oai:www.repository.cam.ac.uk:1810/367915