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

Abstract

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_n=\Z_n^d$ and for each pair ${x,y}$ of vertices, we add an edge between them with probability $p_{x,y}=\frac{Z}{|x-y|^d}$, 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}_n$ 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^{(0)}$ consists of a single vertex, and for $n\ge1$ the $n$-dimensional one $\Gn$ is obtained by considering two independent copies of $G^{(n-1)}$ 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^n$. Finally, we discuss a question about branching random walks. A branching random walk is a random walk $\Scal$ on $\Z^d$ 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^4$. 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^8$.