Mixing of random walks on random graphs and intersections of branching random walks

In this thesis, we analyse the mixing properties of random walks on various random graph models, and we discuss a question about the intersection probabilities of branching random walks. We consider three different random graph models that each have some underlying structure and some additional randomness on top of that. The first model (which we only discuss briefly) is a sequence of weighted random graphs (G_n^*) that can be obtained as follows. We start with a sequence (G_n) of finite graphs, and a sequence (\eps_n) of weights, and for each G_n we add edges corresponding to a uniformly chosen perfect matching, assigning weight \eps_n to these edges and weight $1$ to the original edges of G_n. In 2020 Hermon, Sly and Sousi~\cite{random_matching} studied this model in the case \eps_n\equiv1 and they showed that a random walk on G_n^* exhibits cutoff. In this model we allow the weights \eps_n to tend to 0 and we study how quickly they can decay so that the added edges still induce cutoff. For two families of graphs we give a complete answer to this question and we also find a general sufficient condition. The second model is a `small-world network' that is defined as follows. We start with a $d$-dimensional torus G<sub>n</sub>=\Z<sub>n</sub><sup>d</sup> and for each pair $\{x,y\}$ of vertices, we add an edge between them with probability p<sub>x,y</sub>=\frac{Z}{|x-y|<sup>d</sup>}, independently for different pairs, where $Z$ is chosen such that the expected number of added edges is 1 for each vertex. We consider a simple or lazy random walk on this random graph \til{G}<sub>n</sub> and for $d\ge3$ we show that the mixing time is of order $\log n$, and there is no cutoff. The third model is a randomly twisted hypercube, which is a random perturbation of a Boolean hypercube defined as follows. The 0-dimensional twisted hypercube G<sup>(0)</sup> consists of a single vertex, and for $n\ge1$ the $n$-dimensional one $\Gn$ is obtained by considering two independent copies of G<sup>(n-1)</sup> and adding edges corresponding to a uniform perfect matching between their vertices. %This model was introduced by Dudek et al~\cite{randomly_twisted_hypercubes} in 2018, who focused on studying its connectivity properties. Later it was also studied by Benjamini et al~\cite{twisted_hypercubes_structure_randomness}, who also asked about. We consider a simple or lazy random walk on $\Gn$ and show that the mixing time is of order $n$ and there is no cutoff. We also prove that the cover time is of order n2<sup>n</sup>. Finally, we discuss a question about branching random walks. A branching random walk is a random walk $\Scal$ on \Z<sup>d</sup> indexed by the `infinite invariant tree' $\T$ which is a random infinite tree consisting of an infinite spine, and random finite trees attached to it on both sides. It can be thought of as a higher dimensional generalisation of a simple random walk, and it can also be viewed as a more approachable model resembling properties of the infinite incipient cluster of a critical bond percolation. As a step towards understanding the geometry of the range of a branching random walk, we study the intersection between two such walks. In 8 dimensions, which is the critical dimension for this question, we establish the precise order of the non-intersection probability between one walk $\Scal$ indexed by one side of the tree, and an independent one $\til{\Scal}$ indexed by both sides of an independent tree. This is analogous to the result by Lawler~\cite{intersections_of_RWs} from the '90s for two independent simple random walks on \Z⁴. We also consider a notion of size, called branching capacity, defined in terms of the escape probabilities of a branching random walk, and prove a weak law of large numbers for the branching capacity of a branching random walk range on \Z⁸.

Name dc:type.qualificationname

Doctor of Philosophy (PhD)

Level dc:type.qualificationlevel

Doctoral

Grantor dc:publisher.institution

University of Cambridge

Year dc:date.issued

2025

Author dc:creator

• Baran, Zsuzsanna

Advisor dc:contributor.advisor

• Sousi, Perla

• random graphs
• mixing time
• branching random walks

Licence

• https://www.repository.cam.ac.uk/bitstreams/790fc838-8985-4f63-a2d2-27dca93c0e26/download
• http://purl.org/NET/rdflicense/allrightsreserved

Language dc:language

eng

DOI dc:identifier.doi

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

OAI identifier oai:identifier

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