# Hamilton cycles in weighted Erdős-Rényi graphs

Tony Johansson
Stockholm University
Stockholm, Sweden Funded by the Swedish Research Council (grant 2015-05015).

###### Abstract

Given a symmetric $n\times n$ matrix $P$ with $0\leq P(u,v)\leq 1$, we define
a random graph $G_{n,P}$ on $[n]$ by independently including any edge
$\\{u,v\\}$ with probability $P(u,v)$. For $k\geq 1$ let $\mathcal{A}_{k}$ be
the property of containing $\left\lfloor k/2\right\rfloor$ Hamilton cycles,
and one perfect matching if $k$ is odd, all edge-disjoint. With an eigenvalue
condition on $P$, and conditions on its row sums, $G_{n,P}\in\mathcal{A}_{k}$
happens with high probability if and only if $G_{n,P}$ has minimum degree $k$
whp. We also provide a hitting time version. As a special case, the random
graph process on pseudorandom $(n,d,\mu)$-graphs with $\mu\leq
d(d/n)^{\alpha}$ for some constant $\alpha>0$ has property $\mathcal{A}_{k}$
as soon as it acquires minimum degree $k$ with high probability.

##  1 Introduction

The problem of determining whether a random graph contains a Hamilton cycle,
i.e. a cycle passing through every vertex exactly once, dates back to the
inception of the study of random graphs. In 1960, Erdős and Rényi asked
whether their eponymous random graph $G_{n,p}$, obtained by including any edge
independently with probability $p$, contains a Hamilton path [8]. The problem
was settled by Komlós and Szemerédi [15], who showed that

$\lim{\mbox{Pr}\left\\{G_{n,p}\text{ is
Hamiltonian}\right\\}}=\lim{\mbox{Pr}\left\\{\delta(G_{n,p})\geq 2\right\\}},$

where $\delta$ denotes the minimum degree of a graph. This was strengthened to
a hitting time result, independently by Bollobás [5] and by Ajtai, Komlós and
Szemerédi [1], stated as follows. Suppose $G_{n,m}$ is an increasing sequence
of random graphs, where $G_{n,m}$ is obtained by adding a uniformly chosen
edge to $G_{n,m-1}$. Let $\tau_{2}$ be the smallest $m$ for which
$\delta(G_{n,m})\geq 2$. Then with high probability, $G_{n,\tau_{2}}$ is
Hamiltonian. For integers $k\geq 1$, let $\mathcal{A}_{k}$ denote the graph
property of containing $\left\lfloor k/2\right\rfloor$ Hamilton cycle, as well
as a matching of size $\left\lfloor n/2\right\rfloor$ when $k$ is odd.
Bollobás and Frieze [6] strengthened the hitting time result above to showing
that $G_{n,\tau_{k}}\in\mathcal{A}_{k}$ with high probability. For a more
thorough history, see Frieze’s recent survey on Hamilton cycles [10].

In recent years, some attention has been turned to random subgraphs of a host
graph $\Gamma_{n}$. The random subgraph $\Gamma_{n,p}$ is obtained by
including any edge of $\Gamma_{n}$ independently with probability $p$, and a
the random graph process $\Gamma_{n,m}$ on $\Gamma_{n}$ is obtained by
ordering the edges of $\Gamma_{n}$ uniformly at random. An early example is
the random bipartite graph $G_{n,n,p}$, obtained by letting
$\Gamma_{n}=K_{n,n}$. Frieze [9] determined the threshold in this case. Frieze
and Krivelevich [13] showed that if $\Gamma_{n}$ is in a certain class of
pseudorandom graphs (specified below) then
$\Gamma_{n,\tau_{2}}\in\mathcal{A}_{2}$ whp. The author [14] showed that the
same holds when $\delta(\Gamma_{n})\geq(1/2+\varepsilon)n$ for some constant
$\varepsilon>0$ (and that it need not hold when $\delta(\Gamma_{n})=n/2$).
Alon and Krivelevich [3] showed that $\Gamma_{n,\tau_{2k}}\in\mathcal{A}_{2k}$
whp for any $k=O(1)$ in three dense classes of host graphs, which include some
pseudorandom graphs and graphs with
$\delta(\Gamma_{n})\geq(1/2+\varepsilon)n$.

Both [13] and [3] consider pseudorandom graphs known as $(n,d,\mu)$-graphs. A
graph $\Gamma$ is an $(n,d,\mu)$-graph if it has $n$ vertices, every vertex
has degree $d$, and the second largest eigenvalue of its adjacency matrix is
at most $\mu$ in absolute value. We strengthen both results in the following
special case of our main theorem. Let $\tau_{\mathcal{A}_{k}}$ be the smallest
$m$ for which $\Gamma_{n,m}\in\mathcal{A}_{k}$.

######  Theorem (Theorem 1.2, pseudorandom graph case).

Let $k=O(1)$. Suppose $\Gamma_{n}$ is an $(n,d,\mu)$-graph with $\mu\leq
d(d/n)^{\alpha}$ for some constant $\alpha>0$. Then the random graph process
on $\Gamma_{n}$ has $\tau_{\mathcal{A}_{k}}=\tau_{k}$ with high probability.

In [13] it was required that $\mu=o(d^{5/2}/(n\ln n)^{3/2})$, which only holds
if $d\gg n^{3/4}(\ln n)^{3}$, while [3] asked that $\mu=O(d^{2}/n)$ and
$d=\Omega(n(\ln\ln n)/\ln n)$. This result strengthens both, with an implicit
degree bound of $d=n^{\Omega(1)}$ owing to the fact that $\mu=\Omega(d^{1/2})$
(see e.g. [18]).

Our full result concerns a more general inhomogeneous random graph. Suppose
$P$ is a symmetric $n\times n$ matrix with entries $P(u,v)\in[0,1]$. We then
define a random graph $G_{n,P}$ by independently including each edge
$\\{u,v\\}$ with probability $P(u,v)$. If $R$ is a symmetric $n\times n$
matrix with $R(u,v)\geq 0$ for all $uv$, we also define a random graph process
$G_{n,R}(t)$ as follows. Each pair $\\{u,v\\}$ is independently assigned a
random value $E(u,v)$, exponentially distributed with rate $R(u,v)$, taken to
equal $\infty$ if $R(u,v)=0$. We let

$G_{n,R}(t)=([n],\\{uv:E(u,v)\leq t\\}).$

Note that $G_{n,R}(t)$ equals $G_{n,P}$ in distribution when
$P(u,v)=1-e^{-R(u,v)t}$. Note that this framework generalizes $\Gamma_{n,p}$
and $\Gamma_{n,m}$ (now in continuous time), re-obtained by letting $R$ be the
adjacency matrix of $\Gamma_{n}$. Anastos, Frieze and Gao [4] considered
Hamiltonicity in the stochastic block model, which is $G_{n,P}$ with $P$ in a
specific class of block matrices.

For vertex sets $A,B$ we let $R(A,B)=\sum_{u\in A,v\in B}R(u,v)$. Let
$d_{R}(u)=R(u,V)$ and $d_{R}(A)=R(A,V)$. A key tool in our proof is the random
walk induced by $R$, which jumps from $u$ to $v$ with probability
$M(u,v)=R(u,v)/d_{R}(u)$. The transition matrix $M$ has real eigenvalues
$1=\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq-1$ (see e.g. [16]),
and we let $\lambda(R)=\max\\{|\lambda_{2}|,|\lambda_{n}|\\}$. Let
$\sigma(u)=d_{R}(u)/d_{R}(V)$ be the stationary distribution of the random
walk, and define $\|M\|=\max_{u,v}M(u,v)$.

######  Definition 1.1.

Let $\mathrm{RM}$ be the set of rate matrices $R$ with transition matrix $M$
such that there exist constants $\alpha\in[0,1/2)$, $\gamma>0$, $b>0$ such
that $\lambda(R)=o(1)$ and

$\lambda(R)\leq(n\|M\|)^{-\alpha-\gamma},$ (1.1)

and $R$ satisfies the following:

  1. (a)

there exists a $d=d(n)$ such that $d_{R}(u)\geq d$ for all $u$, and
$d_{R}(V)\leq bdn$.

  2. (b)

for any $A\subseteq V$,

$\sigma(A)=\frac{d_{R}(A)}{d_{R}(V)}\leq
b\left({\frac{|A|}{n}}\right)^{1-2\alpha},$ (1.2)

  3. (c)

$\|R\|\leq dn^{-\gamma}$.

We state our main result.

######  Theorem 1.2.

Let $k=O(1)$. If $R\in\mathrm{RM}$, then whp $G_{n,R}(t)$ satisfies

$\tau_{k}=\tau_{\mathcal{A}_{k}}.$

For any symmetric non-negative matrix $R$ on $V$, let

$\gamma_{k}(R)=\sum_{u\in V}d_{R}(u)^{k-1}e^{-d_{R}(u)}.$

Let $\mathrm{RM}(1)$ be the set of $R\in\mathrm{RM}$ with $\gamma_{1}(R)=1$.
Note that for any $x>0$, the graphs $G_{n,R}(\tau_{k})$ and
$G_{n,xR}(\tau_{k})$ are equal in distribution, so it is enough to prove
Theorem 1.2 for $R\in\mathrm{RM}(1)$.

######  Theorem 1.3.

Let $k=O(1)$. Suppose $P\in\mathrm{RM}$ has
$\gamma_{k}(P)\to\gamma_{k}\in[0,\infty]$. Then

$\lim_{n\to\infty}{\mbox{Pr}\left\\{G_{n,P}\in\mathcal{A}_{k}\right\\}}=e^{-\gamma_{k}}.$

Note that if $P$ has constant row sums $d_{P}(u)=d=\ln n+(k-1)\ln\ln
n+c_{n,k}$, then $\gamma_{k}=\exp\\{-\lim_{n}c_{n,k}\\}$.

##  2 Proof outline

Let us first discuss the overarching proof idea. Traditionally, many proofs of
Hamiltonicity in random graphs rely on finding so-called booster edges for a
graph $G$, which are edge $e\notin G$ such that $G\cup\\{e\\}$ is closer to
being Hamiltonian, typically meaning it contains a longer path than $G$ does.
If random edges are added to $G$, one argues that some booster is likely to be
added.

Montgomery [17] more generally defined boosters as sets $T$ of edges whose
addition gets $G$ closer to Hamiltonicity, and used sets $|T|\leq 2$. A
similar idea was used earlier in [11]. Booster pairs were also used by Alon
and Krivelevich in their recent paper [3]. In this paper we move to general
boosters, i.e. edge sets $T$ of any (constant) size whose addition improves
$G$. These are found using random alternating walks.

###  2.1 Random subgraphs

For proving Hamiltonicity, the most important property of $G_{n,R}(\tau_{k})$
is expansion (see Lemma 2.1 below for the definition). A major drawback of
$G_{n,R}(\tau_{k})$ for our purposes is its high average degree, with most
vertices having degree $\Omega(\ln n)$. We therefore define a random subgraph
$H\subseteq G_{n,R}(\tau_{k})$, which retains expansion and connectivity with
high probability while containing only $O(n)$ edges. We do not show that $H$
itself is Hamiltonian, but the graph will be important to our proof.

Recall the construction of $G_{n,R}(t)$, in which each edge $\\{u,v\\}$ is
included at a random time $E(u,v)$. Let $D\geq k$ be a constant integer and
let

$T_{D}(u)=\inf\\{t>0:d_{t}(u)\geq D\\}$

be the random time at which $u$ attains degree $D$. Define $H(t)\subseteq
G_{n,R}(t)$ by including any edge $\\{u,v\\}$ with $E(u,v)\leq t$ and
$E(u,v)\leq\max\\{T_{D}(u),T_{D}(v)\\}$. Let $H=H(\tau_{k})$. In other words,
an edge is included in $H$ if it is among the first $D$ edges attached to one
of its endpoints in $G_{n,R}(\tau_{k})$.

For a graph $G=(V,E)$ and $A\subseteq V$ we let $N(A)=\\{u\notin
A:\\{u,v\\}\in E,\text{ some $v$}\\}$ and $\widehat{N}(A)=A\cup N(A)$. The
following lemma is proved in Section 8.

######  Lemma 2.1.

Suppose $R\in\mathrm{RM}$, and let $k=O(1)$. For a large enough constant $D$,
the following holds.

  1. (i)

(Light tail) Let $\theta$ tend to infinity with $n$ and let $S_{\theta}$ be
the set of $u$ with $d_{H}(u)\geq\theta$ or $d_{R}(u)\geq\theta d$. Then with
high probability, $|\widehat{N}_{H}(S_{\theta})|=o(n)$.

  2. (ii)

(Expansion) There exists a constant $\beta=\beta(R,k)>0$ such that with high
probability, every vertex set $A$ with $|A|<\beta n$ satisfies $|N_{H}(A)|\geq
k|A|$.

Let $\mathrm{SE}_{k}(R)$ (“sparse expanders”) be the set of graphs satisfying
(i) – (ii). Note that if $G\in\mathrm{SE}_{k}$ and $\Delta(F)\leq\ell<k$ then
$G\setminus F\in\mathrm{SE}_{k-\ell}$ and $G\cup F\in\mathrm{SE}_{k}$. Note
also that $\mathrm{SE}_{k}\subseteq\mathrm{SE}_{\ell}$.

For $t>0$ let

$\mathbb{S}(t)=\\{u:T_{D}(u)>t\\}=\\{u:d_{t}(u)<D\\},$ (2.1)

and $\mathbb{L}(t)=V\setminus\mathbb{S}(t)$. For $0\leq t_{0}\leq t_{1}$
define a random graph $G_{n,R}^{*}(t_{0},t_{1})$ by including any edge
$\\{u,v\\}$ with $E(u,v)\leq t_{1}$, and any $\\{u,v\\}$ with one endpoint in
$\mathbb{S}(t_{0})$ and $E(u,v)\leq\tau_{k}$. Then $G_{n,R}(t_{1})\subseteq
G_{n,R}^{*}(t_{0},t_{1})\subseteq G_{n,R}(\tau_{k})$ whenever
$t_{1}\leq\tau_{k}$, and $H\subseteq G_{n,R}^{*}(t_{0},t_{1})$ for any
$0<t_{0}\leq t_{1}$. Suppose $t_{0}<t_{1}<t_{2}$ and define

$G_{0}=G_{n,R}^{*}\left(t_{0},t_{0}\right),\quad
G_{1}=G_{n,R}^{*}\left(t_{0},t_{1}\right),\quad
G_{2}=G_{n,R}^{*}\left(t_{0},t_{2}\right).$

For $i=0,1,2$ let $\mathcal{F}_{i}$ denote the $\sigma$-algebra generated by
$G_{n,R}^{*}(t_{0},t_{0})$ (including $E(u,v)$ for all edges included) and
$G_{n,R}^{*}(t_{0},t_{i})$ (excluding $E(u,v)$). Then $H$ is
$\mathcal{F}_{i}$-measurable for all $i$, and the following lemma lets us jump
between $G_{1}$ and $G_{2}$.

######  Lemma 2.2.

Suppose $R\in\mathrm{RM}(1)$. Let $0<t_{0}<t_{1}<t_{2}$ and
$G_{i}=G_{n,R}^{*}(t_{0},t_{i})$ for $i=0,1,2$. Let
$\mathcal{L}_{2}\in\mathcal{F}_{2}$. Then for any set $F$ of edges

$\displaystyle{\mbox{Pr}\left\\{F\subseteq
G_{2}\mid\mathcal{F}_{1}\right\\}}=\prod_{\begin{subarray}{c}\\{u,v\\}\in
F\setminus G_{1}\\\
u,v\in\mathbb{L}(t_{0})\end{subarray}}\left(1-e^{-R(u,v)(t_{2}-t_{1})}\right),$
(2.2) $\displaystyle{\mbox{Pr}\left\\{F\subseteq G_{1}\mid\\{F\subseteq
G_{2}\\}\cap\mathcal{L}_{2}\right\\}}\geq\left(\frac{t_{1}-t_{0}}{t_{2}-t_{0}}\right)^{|F|}.$
(2.3)

###### Proof.

Any edge in $G_{2}\setminus G_{1}$ is fully contained in $\mathbb{L}(t_{0})$.
Conditional on $G_{0}$ and $\mathbb{S}(t_{0})$, the edges $\\{u,v\\}\notin
G_{0}$ with $u,v\in\mathbb{L}(t_{0})$ are independent exponential random
variables with individual rates $R(u,v)$, conditioned to be at least $t_{0}$.
Then (2.2) follows from the memoryless property of exponential random
variables. Since $\|R\|=o(1)$, we have

${\mbox{Pr}\left\\{F\subseteq G_{1}\mid\\{F\subseteq
G_{2}\\}\cap\mathcal{L}_{2}\right\\}}=\prod_{\\{u,v\\}\in F\setminus
G_{0}}\frac{e^{-R(u,v)t_{0}}-e^{-R(u,v)t_{1}}}{e^{-R(u,v)t_{0}}-e^{-R(u,v)t_{2}}}\\\
=\left(\frac{t_{1}-t_{0}}{t_{2}-t_{0}}\right)^{|F\setminus
G_{0}|}\geq\left(\frac{t_{1}-t_{0}}{t_{2}-t_{0}}\right)^{|F|}.$ (2.4)

∎

###  2.2 The high-level argument

Suppose $R\in\mathrm{RM}(1)$ and let $t_{0}=1/4,t_{1}=1/2,t_{2}=3/4$. Define
$G_{0},G_{1},G_{2}$ as in the previous section. We will show that
$G_{2}\in\mathcal{A}_{k}$ whp. In Section 3.1 we show that $\tau_{k}>3/4$ whp,
and since $G_{2}\subseteq G_{n,R}(\tau_{k})$ when $\tau_{k}>3/4$, it follows
that

${\mbox{Pr}\left\\{G_{n,R}(\tau_{k})\in\mathcal{A}_{k}\right\\}}\geq{\mbox{Pr}\left\\{G_{2}\in\mathcal{A}_{k}\text{
and }\tau_{k}>3/4\right\\}}=1-o(1).$ (2.5)

Say that $F$ is a $k$-graph if it can be written as the disjoint union of
$F_{1},\dots,F_{\left\lfloor k/2\right\rfloor}$ where $F_{i}$ is a path or a
cycle for all $i$, as well as a matching $F_{0}$ when $k$ is odd. Define

$s_{k}(G)=\max\\{|F|:F\subseteq G\text{ a $k$-graph}\\},$

so that $G\in\mathcal{A}_{k}$ if and only if $s_{k}(G)=\left\lfloor
kn/2\right\rfloor$.

For $i=1,2$ let $\mathcal{M}_{i}^{\ell}$ be the event that
$s_{k}(G_{i})=\ell$. Recall the definition of $\mathbb{S}(t)$ from (2.1), and
let

$\mathcal{L}=\\{H\in\mathrm{SE}_{k}\\}\cap\\{|\mathbb{S}(t_{0})|=o(n)\\},$

and note that $\mathcal{L}$ is $\mathcal{F}_{0}$-measurable. Then
$\mathcal{M}_{i}^{\ell}\cap\mathcal{L}\in\mathcal{F}_{i}$ for $i=1,2$, and
Lemma 2.2 gives

${\mbox{Pr}\left\\{\mathcal{M}_{1}^{\ell}\mid\mathcal{M}_{2}^{\ell}\cap\mathcal{L}\right\\}}\geq\min_{\begin{subarray}{c}F\text{
$k$-graph}\end{subarray}}{\mbox{Pr}\left\\{F\subseteq
G_{1}\mid\mathcal{L}\cap\\{F\subseteq
G_{2}\\}\right\\}}\geq\left({\frac{1}{2}}\right)^{kn/2}.$

Then for any $\ell<\left\lfloor kn/2\right\rfloor$,

$\displaystyle{\mbox{Pr}\left\\{\mathcal{M}_{2}^{\ell}\cap\mathcal{L}\right\\}}$
$\displaystyle=\frac{{\mbox{Pr}\left\\{\mathcal{M}_{1}^{\ell}\cap\mathcal{M}_{2}^{\ell}\cap\mathcal{L}\right\\}}}{{\mbox{Pr}\left\\{\mathcal{M}_{1}^{\ell}\mid\mathcal{M}_{2}^{\ell}\cap\mathcal{L}\right\\}}}\leq\frac{{\mbox{Pr}\left\\{\mathcal{M}_{2}^{\ell}\mid\mathcal{M}_{1}^{\ell}\cap\mathcal{L}\right\\}}}{2^{-kn/2}}.$
(2.6)

Suppose we are able to prove that for any $\ell<\left\lfloor
kn/2\right\rfloor$,

${\mbox{Pr}\left\\{\mathcal{M}_{2}^{\ell}\ \middle|\
\mathcal{M}_{1}^{\ell}\cap\mathcal{L}\right\\}}\leq e^{-\Omega(n\sqrt{\ln
n})}.$ (2.7)

Then plugging (2.7) into (2.6) gives

$\displaystyle{\mbox{Pr}\left\\{G_{2}\notin\mathcal{A}_{k}\right\\}}$
$\displaystyle\leq{\mbox{Pr}\left\\{\overline{\mathcal{L}}\right\\}}+\sum_{\ell<\left\lfloor
kn/2\right\rfloor}{\mbox{Pr}\left\\{\mathcal{M}_{2}^{\ell}\cap\mathcal{L}\right\\}}$
(2.8)
$\displaystyle\leq{\mbox{Pr}\left\\{\overline{\mathcal{L}}\right\\}}+kne^{-\Omega(n\sqrt{\ln
n})+O(n)}={\mbox{Pr}\left\\{\overline{\mathcal{L}}\right\\}}+o(1).$ (2.9)

In Lemma 3.1 we will show that $|\mathbb{S}(t_{0})|=o(n)$ whp. Together with
Lemma 2.1, this shows that $\mathcal{L}$ occurs whp. As noted in (2.5), this
together with a proof that $\tau_{k}>3/4$ whp (Lemma 3.2 below) shows that
$G_{n,R}(\tau_{k})\in\mathcal{A}_{k}$ whp.

It remains to prove (2.7). The graph $G_{1}$ contains $H$ by construction. If
$\mathcal{M}_{1}^{\ell}\cap\mathcal{L}$ holds then $G_{1}$ contains some
$k$-graph $F$ of size $\ell$. If $k$ is even, suppose $F=F_{1}\cup\dots
F_{k/2}$ for some disjoint paths and Hamilton cycles $F_{i}$. Suppose without
loss of generality that $|F_{1}|<n$. Then $G_{1}$ contains the graph $G=H\cup
F_{1}\setminus(F_{2}\cup\dots\cup F_{k/2})\in\mathrm{SE}_{2}$. Let $G^{p}$ be
the graph obtained by independently adding any edge $\\{u,v\\}$ to $G$ with
probability $p(u,v)$, where $p$ is some symmetric function. Letting

$p(u,v)=\left\\{\begin{array}[]{ll}0,&u\in\mathbb{S}(t_{0})\text{ or
}v\in\mathbb{S}(t_{0}),\\\ 0,&\\{u,v\\}\in F_{2}\cup\dots\cup F_{k/2},\\\
\frac{1}{3}R(u,v),&\text{ otherwise},\end{array}\right.$

we have $G^{p}\subseteq G_{2}$ by Lemma 2.2. If $s_{2}(G^{p})>s_{2}(G)$ then
$s_{k}(G_{2})\geq s_{k}(G_{1}\cup G^{p})>s_{k}(G_{1})$, since $G^{p}$ is
disjoint from $F_{2}\cup\dots\cup F_{k/2}\subseteq G_{1}$.

If $k$ is odd and $F=F_{1}\cup\dots\cup F_{(k+1)/2}$, assume without loss of
generality that $\Delta(F_{1})\leq i$ and $|F_{1}|<in/2$ for some
$i\in\\{1,2\\}$. Then $G=H\cup F_{1}\setminus(F_{2}\cup\dots\cup
F_{(k+1)/2})\in\mathrm{SE}_{1}$, and $s_{i}(G^{p})>s_{i}(G)$ implies
$s_{k}(G_{2})>s_{k}(G_{1})$.

So, (2.7) follows from the following lemma.

######  Lemma 2.3.

Let $i\in\\{1,2\\}$. Suppose $R\in\mathrm{RM}(1)$ and $G\in\mathrm{SE}_{i}(R)$
with $s_{i}(G)<in/2$, and suppose $p(u,v)\geq R(u,v)/3$ for all
$\\{u,v\\}\notin E$ where $\sum_{\\{u,v\\}\in E}R(u,v)=o(n\ln n)$. Then

$\displaystyle{\mbox{Pr}\left\\{s_{i}(G^{p})=s_{i}(G)\right\\}}\leq
e^{-\sqrt{n\ln n}}.$ (2.10)

The remainder of the paper is mainly devoted to proving Lemma 2.1 (Section 8)
and Lemma 2.3 (Sections 4 through 7).

##  3 Preliminaries

We state some preliminary, for the most part standard, results, and leave the
proofs for Section 9.

###  3.1 Degrees

Recall that $d_{R}(u)=\sum_{v}R(u,v)$. We will often assume that
$\gamma_{1}(R)=1$, and note that this implies that $d=\Theta(\ln n)$ where
$d=\min d_{R}(u)$.

######  Lemma 3.1.

Let $R\in\mathrm{RM}(1)$.

  1. (i)

For any integer $D\geq 1$, $u\in V$ and $S\subseteq V$ with $|V\setminus
S|=O(1)$, and $t=\Omega(1)$,

${\mbox{Pr}\left\\{e_{t}(u,S)<D\right\\}}=\exp\\{-td_{R}(u)+O(\ln
d_{R}(u))\\}.$

  2. (ii)

Let $\mathbb{S}(t)$ denote the set of vertices in $G_{n,R}(t)$ with degree
less than $D$. If $t=\Omega(1)$ then $|\mathbb{S}(t)|=o(n)$ whp.

Recall the definition $\gamma_{k}(P)=\sum_{u}e^{-d_{P}(u)}d_{P}(u)^{k-1}$.

######  Lemma 3.2.

Let $k\geq 1$. Suppose $P\in\mathrm{RM}$ has
$\gamma_{k}(P)\to\gamma_{k}\in[0,\infty]$. Then

$\lim_{n\to\infty}{\mbox{Pr}\left\\{\delta(G_{n,P})\geq
k\right\\}}=e^{-\gamma_{k}}.$

If $R\in\mathrm{RM}(1)$ and $\varepsilon\gg\frac{\ln\ln n}{\ln n}$, then
$G_{n,R}(t)$ has $1-\varepsilon<\tau_{k}<1+\varepsilon$ whp.

We also note the following simple consequence of conditions (a) and (b) of
Definition 1.1.

######  Lemma 3.3.

Suppose $R\in\mathrm{RM}$ has stationary distribution $\sigma$, and
$A\subseteq V$. Then $\sigma(A)=o(1)$ if and only if $|A|=o(n)$.

###  3.2 The expander mixing lemma

For a matrix $A$ indexed by $V$ and sets $S,T\subseteq V$ we write

$A(S,T)=\sum_{u\in S,v\in T}A(u,v),$

noting that pairs $(u,v)$ with $u,v\in S\cap T$ are counted twice. We will use
the following version of the well-known Expander Mixing Lemma [2].

######  Lemma 3.4.

Suppose $R\in RM$ has transition matrix $M$ with stationary distribution
$\sigma$. Then for any $A,B\subseteq V$,

$\displaystyle
M(A,B)=|A|\sigma(B)+O\left(\lambda(R)\sqrt{n|A|\sigma(B)}\right).$ (3.1)

In particular, the following holds.

  1. (i)

$R(A,B)=\Omega(dn)$ for any $A,B\subseteq V$ with $|A|,|B|=\Omega(n)$.

  2. (ii)

There exists a constant $c>0$ such that

$\left|\left\\{u\in
A:M(u,A)\geq\left({\frac{|A|}{n}}\right)^{c}\right\\}\right|=o(|A|)\quad\text{for
all $|A|\leq n/2$}.$

###  3.3 Probabilistic bounds

We consider the following lemma well-known, and state it without proof.

######  Lemma 3.5.

Suppose $X_{1},\dots,X_{m}$ are independent exponential random variables with
finite respective rates $r_{1},\dots,r_{m}>0$. Let $r=r_{1}+\dots+r_{m}$ and
suppose $r_{i}\leq\varepsilon r$ for all $i$, for some $\varepsilon>0$. Let
$X_{(D)}$ be the $D$–th smallest value in the family. Then for $D\leq
1/2\varepsilon$,

${\mbox{Pr}\left\\{X_{i}\leq X_{(D)}\right\\}}\leq 2D\frac{r_{i}}{r}.$

We will also use the following Chernoff bounds.

######  Lemma 3.6.

Suppose $X$ is a finite set and let $\sigma_{x}\in[0,1]$ for all $x\in X$. Let
$\mu=\sum_{x\in X}\sigma_{x}$.

  1. (i)

Suppose $S\subseteq X$ is a random set obtained by including any $x\in X$
independently with probability $\sigma_{x}$. If $\phi\leq\frac{1}{2}\mu$, then

$\displaystyle{\mbox{Pr}\left\\{|S|\leq\phi\right\\}}$
$\displaystyle\leq\exp\left\\{-\frac{\mu}{8}\right\\}.$ (3.2)

  2. (ii)

Suppose $T\subseteq X$ is a random set with ${\mbox{Pr}\left\\{A\subseteq
T\right\\}}\leq\prod_{x\in A}\sigma_{x}$ for all $A\subseteq X$. If $\phi\geq
5\mu$, then

$\displaystyle{\mbox{Pr}\left\\{|T|\geq\phi\right\\}}\leq\left({\frac{\mu}{\phi}}\right)^{\phi/2}.$
(3.3)

###### Proof.

Note that the condition on $T$ implies that
$\mathbb{E}\left[|T|^{\ell}\right]\leq\mathbb{E}\left[|S|^{\ell}\right]$ for
all $\ell\geq 0$. The bounds then follow by standard methods, see e.g. [12,
Section 21.4]. ∎

###  3.4 A matrix lemma

Suppose $I$ is a totally ordered set, $A$ a set and ${\bf
a}=(a_{1},\dots,a_{\ell})\in A^{\ell}$ a sequence in $A$. Say that a function
$f:I\to A$ respects ${\bf a}$ if the sequence $(f(i))_{i\in I}$ is a
subsequence of ${\bf a}$.

######  Lemma 3.7.

Suppose $\tau:I\times J\to A$ and ${\bf a}=(a_{1},\dots,a_{\ell})\in
A^{\ell}$, $\ell\geq 1$. Suppose $I$ can be totally ordered so that
$i\mapsto\tau(i,j)$ respects ${\bf a}$ for each $j\in J$. Let
$\pi_{I},\pi_{J}$ be finite measures on $I,J$, respectively. Then there exist
$S\subseteq I,T\subseteq J$ with $\pi_{I}(S)\geq\pi_{I}(I)/\ell$ and
$\pi_{J}(T)\geq\pi_{J}(J)/\ell$, such that $\tau$ is constant on $S\times T$.

###  3.5 Mixing in simple random walks

Let $M$ be a transition matrix with stationary distribution $\sigma$ with
$\sigma(u)>0$ for all $u\in V$. For a probability measure $\pi$ on $V$, define

$\mu_{\sigma}(\pi)=\sqrt{\left(\sum_{u\in
V}\frac{\pi(v)^{2}}{\sigma(v)}\right)-1}.$

Note that $\mu_{\sigma}(\pi)\geq 0$ with equality if and only if $\pi=\sigma$.
We use $\mu_{\sigma}$ as a measure of distance from stationarity.

######  Lemma 3.8.

Suppose $R\in\mathrm{RM}$ has transition matrix $M$. Let $\pi_{0}$ be a
probability measure on $V$, and define $\pi_{1}(v)=\sum_{u}\pi_{0}(u)M(u,v)$.
Then

$\displaystyle\mu_{\sigma}(\pi_{1})\leq\lambda(R)\mu_{\sigma}(\pi_{0}).$ (3.4)

##  4 On alternating walks

Suppose $F=(V,E)$ is a graph, and $R$ is a rate matrix on $V$. A walk
$W=(w_{0},w_{1},\dots,w_{\ell})$ on $V$ is $F$-alternating if
$\\{w_{i},w_{i+1}\\}\in F$ for all odd $i$, and strictly $F$-alternating if
also $\\{w_{i},w_{i+1}\\}\notin F$ for all even $i$.

We need a way to measure the size of a family of $F$-alternating walks. This
will be slightly cumbersome to define. Firstly, for any walk
$W=(w_{0},\dots,w_{\ell})$ define

$R_{\mathrm{alt}}[W]=\prod_{j=0}^{\left\lfloor\ell/2\right\rfloor-1}R(w_{2j},w_{2j+1}).$

For a family of walks $\mathcal{W}$ let
$R_{\mathrm{alt}}[\mathcal{W}]=\sum_{W\in\mathcal{W}}R_{\mathrm{alt}}[W]$.

For any edge set $E$ with $E\cap G=\emptyset$ we also define

$R_{G}[E]=\prod_{\\{u,v\\}\in E}R(u,v).$

If $E\cap G\neq\emptyset$ let $R_{G}[E]=0$. If $\mathcal{E}$ is a family of
edge sets, let $R_{G}[\mathcal{E}]=\sum_{E\in\mathcal{E}}R_{G}[E]$.

For a walk $W$ let $\mathrm{odd}(W)$ be the set of edges
$\\{\\{w_{2i},w_{2i+1}\\}:i\geq 0\\}$. Note that if $W$ is a walk which
repeats no vertex and is strictly $G$-alternating, then
$R_{G}[\mathrm{odd}(W)]=R_{\mathrm{alt}}[W]$. If $E$ is an edge set of size
$r$, then the number of walks $W$ with $\mathrm{odd}(W)=E$ is $2^{r}r!$. We
conclude that if $\mathcal{W}$ is a family of non-repeating strictly
$G$-alternating walks of length $2r-1$ and
$\mathrm{odd}(\mathcal{W})=\\{\mathrm{odd}(W):W\in\mathcal{W}\\}$, then

$R_{G}[\mathrm{odd}(\mathcal{W})]\geq\frac{1}{2^{r}r!}R_{\mathrm{alt}}[\mathcal{W}].$
(4.1)

For a walk $W=(w_{0},\dots,w_{i})$ let $f(W)=w_{i}$ denote its final vertex.
For a family $\mathcal{W}$ of walks and $v\in V$ let $\mathcal{W}^{\to v}$ be
the set of $W\in\mathcal{W}$ with $f(W)=v$. Let
$(W,v_{1},\dots,v_{j})=(w_{0},\dots,w_{i},v_{1},\dots,v_{j})$, and for two
walks $W_{1}=(w_{0},\dots,w_{i})$ and
$W_{2}=(w_{0}^{\prime},\dots,w_{j}^{\prime})$ write

$W_{1}\circ W_{2}=(w_{0},\dots,w_{i},w_{j}^{\prime},\dots,w_{0}^{\prime}).$

###  4.1 Mixing for alternating walks

We define a random walk on $V$ as a probability measure $\pi$ on the set
$V^{\infty}$ of infinite walks on $V$. For walks $W$ of length $\ell$, write
$\pi(W)=\pi(\mathcal{W}(W))$ where $\mathcal{W}(W)$ is the family of walks
agreeing with $W$ for the first $\ell$ steps. Define

$\pi(w_{j+1}\mid
w_{0},\dots,w_{j})=\frac{\pi(w_{0},\dots,w_{j+1})}{\pi(w_{0},\dots,w_{j})}$

whenever $\pi(w_{0},\dots,w_{j})>0$. Define $\pi(v\mid W)=0$ when $\pi(W)=0$.

Suppose $G$ is a graph and $R$ a rate matrix. Recall the definition of
$\widehat{N}(A)$ from Section 2.1. Starting at some (possibly random) initial
point $w_{0}$, say that a random walk $\pi$ is an $(R,G)$-alternating random
walk if for all $i\geq 0$,

$\displaystyle\pi(w_{2i+1}\mid w_{0},\dots,w_{2i})$
$\displaystyle=M(w_{2i},w_{2i+1}),$ (4.2) $\displaystyle\pi(w_{2i+2}\mid
w_{0},\dots,w_{2i+1})$ $\displaystyle=0,\quad
w_{2i+2}\notin\widehat{N}_{G}(w_{2i+1}).$ (4.3)

We let $\pi_{i}$ denote the measure on $V$ induced by $w_{i}$. A special case
is the simple, lazy $(R,G)$-alternating random walk $\pi_{G}$ defined by

$\pi_{G}(w_{2i}\mid w_{0},\dots,w_{2i-1})=\frac{1}{d_{G}(w_{2i-1})+1},\quad
w_{2i}\in\widehat{N}_{G}(w_{2i-1}),$

for all $i\geq 1$. If the initial vertex $x$ is specified, we denote the
measure by $\pi_{G,x}$.

Note that if $W=(w_{0},\dots,w_{j})$ is a $G$-alternating walk and $\pi$ a
random $(R,G)$-alternating walk, then

$\pi(W\mid w_{0})\leq\prod_{i=0}^{\left\lceil
j/2\right\rceil-1}\frac{R(w_{2i},w_{2i+1})}{d_{R}(w_{2i})}\leq\frac{R_{\mathrm{alt}}[W]}{d^{\left\lceil
j/2\right\rceil}}.$ (4.4)

For rate matrices $R$ define

$\mathrm{mix}(R)=\left\lceil
2-2\frac{\ln(n\|M\|)}{\ln\lambda(R)}\right\rceil,$ (4.5)

and note that $\mathrm{mix}(R)=O(1)$ for $R\in\mathrm{RM}$ since then
$\lambda(R)=(n\|M\|)^{-\Omega(1)}$. The name is in reference to the following
lemma.

######  Lemma 4.1.

Suppose $R\in\mathrm{RM}$, $\Delta(F)\leq 2$, and that $\pi$ is an
$(R,F)$-alternating random walk. Suppose $\theta\leq\lambda(R)^{-1/4}$ tends
to infinity with $n$, and that $j\geq\mathrm{mix}(R)$. Suppose $c>0$ is a
constant. There exists a constant $\rho>0$ such that if $\mathcal{W}$ is a
family of $F$-alternating walks $W$ of length $2j$, such that $d_{R}(v)<\theta
d$ for all $v\in W$, and $\pi(\mathcal{W})\geq c$, then there exists a vertex
set $U_{2j}$ of size at least $\rho n$ such that

$\displaystyle\pi(\mathcal{W}^{\to u})\geq\frac{\rho}{n},\quad\text{for all
$u\in U_{2j}$}.$ (4.6)

Say that a measure $\mu$ on $V$ is near-uniform if there exists a constant
$c>0$ such that $\mu(v)\leq c/n$ for all $v$. Say that a random walk $\pi$ is
near-uniform if $\pi_{0}$ is near-uniform. Note that for a near-uniform $\pi$,
(4.4) shows that for any family of walks $\mathcal{W}$ of length $j$,

$\pi(\mathcal{W})=\sum_{u}\pi_{0}(u)\pi(\mathcal{W}\mid
u)\leq\frac{c}{n}\frac{R_{\mathrm{alt}}[\mathcal{W}]}{d^{\left\lceil
j/2\right\rceil}}$ (4.7)

For $S\subseteq V$ let $\tau(S)$ be the random time at which a walk first
visits $S$, and let $\tau_{\mathrm{odd}}(S)$ be the first odd index for which
it occurs.

######  Lemma 4.2.

Suppose $R\in\mathrm{RM}$ and that $G$ is light-tailed. Suppose $\pi$ is a
near-uniform random $(R,G)$-alternating walk.

  1. (i)

If $j\geq 0$ is constant and $|S|=o(n)$, then $\pi(\tau(S)\leq 2j)=o(1)$.

  2. (ii)

If $|S|=\Omega(n)$ then $\pi(\tau(S)\leq 1)=\Omega(1)$.

Lemma 4.2 (i) is particularly interesting for $S=S_{\theta}$, which has
$|S_{\theta}|=o(n)$ if $R\in\mathrm{RM}$ and $G$ is light-tailed. We let
$\mathcal{D}_{j}^{\theta}$ denote the event that $\tau(S_{\theta})\leq j$, and
let $Z_{j}^{\theta}(c)$ be the corresponding vertex set. Then
$|Z_{j}^{\theta}(c)|=o(n)$.

######  Lemma 4.3.

Suppose $R\in\mathrm{RM}$ and that $G$ is light-tailed. Let $j\geq 0$. Let
$\mathcal{C}_{j}^{\theta}$ be the set of $G$-alternating walks
$W=(w_{0},\dots,w_{j})$ with $d_{G}(w_{i})<\theta$ and $d_{R}(w_{i})<\theta d$
for all $i$, such that either (a) $|\\{w_{0},\dots,w_{j}\\}|<j+1$ or (b) $W$
is not strictly $G$-alternating. If $\theta^{j}\|M\|=o(1)$ then

$R_{\mathrm{alt}}[\mathcal{C}_{j}^{\theta}]=o(nd^{\left\lceil
j/2\right\rceil}).$

###  4.2 Matchings and augmenting walks

Suppose $G$ is a graph on an even number $n$ of vertices. Let
$s_{1}(G)\leq\left\lfloor n/2\right\rfloor$ denote the size of the largest
matching in $G$. Suppose $s_{1}(G)<\left\lfloor n/2\right\rfloor$, and let
$\mathcal{F}_{1}(G)$ be the family of matchings $F$ with $|F|=\mu(G)$. For
$F\in\mathcal{F}_{1}(G)$ let $\mathrm{IP}_{F}$ be the set of vertices isolated
by $F$, i.e. vertices $x$ such that $d_{F}(x)=0$. Let
$\mathrm{IP}_{2}=\mathrm{IP}_{2}(G)$ be the set of vertex pairs $\\{x,y\\}$
such that $\\{x,y\\}\subseteq\mathrm{IP}_{F}$ for some
$F\in\mathcal{F}_{1}(G)$.

######  Lemma 4.4.

Suppose $G\in\mathrm{SE}_{1}$ with $s_{1}(G)<\left\lfloor n/2\right\rfloor$.
Then $|\mathrm{IP}_{2}|\geq(\beta n)^{2}/2.$

###### Proof.

Let $F\in\mathcal{F}_{1}(G)$ with and $x\in\mathrm{IP}_{F}$. Let $Y$ be the
set of vertices $y$ such that there exists an $F$-alternating walk
$(x=w_{0},\dots,w_{2j}=y)$ of even length, with $x\in Y$. Then
$N_{G}(Y)=N_{F}(Y)$. Indeed, suppose $v\in N_{G}(Y)\setminus N_{F}(Y)$, and
let $W=(x,\dots,y)$ be an even-length $F$-alternating walk such that $yv\in
G$. If $v\in\mathrm{IP}_{F}$ then $W+v$ is an augmenting walk, contradicting
the maximality of $F$. If $v\notin\mathrm{IP}_{F}$ then $vw\in F$ for some
$w$, and the walk $(W,v,w)$ shows that $w\in Y$, contradicting $v\notin
N_{F}(Y)$. It follows that $|N_{G}(Y)|\leq|N_{F}(Y)|\leq|Y|-1$. Since $G$
expands, we then have $|Y|\geq\beta n$.

The same argument shows that for every $y\in Y$, there is a set
$|X_{y}|\geq\beta n$ such that $\\{x,y\\}\in\mathrm{IP}_{2}$ for each $x\in
X_{y}$. We conclude that $|\mathrm{IP}_{2}|\geq(\beta n)^{2}/2$. ∎

For a graph $G$, integer $r\geq 1$, and $\theta$ tending to infinity, let
$\mathcal{T}_{r}^{\theta}(G)$ be the family of edge sets $|T|=r$ such that no
$e\in T$ is contained in $G$ or incident to $S_{\theta}$, and $s_{1}(G\cup
T)>s_{1}(G)$.

######  Proposition 4.5.

Suppose $R\in\mathrm{RM}$ and $G\in\mathrm{SE}_{1}$ with
$s_{1}(G)<\left\lfloor n/2\right\rfloor$. Then there exists an $r\leq
2\mathrm{mix}(R)+1$ such that if $\theta$ tends to infinity sufficiently
slowly, then

$R_{G}[\mathcal{T}_{r}^{\theta}]=\Omega(nd^{r}).$

###### Proof.

Let $\mathrm{AW}_{2r-1}^{\theta}(G)$ be the set of walks
$(w_{0},\dots,w_{2r-1})$ which (a) repeat no vertex, (b) avoid $S_{\theta}$,
(c) are $F$-alternating with $w_{0},w_{2r-1}\in\mathrm{IP}_{F}$ for some
$F\in\mathcal{F}_{1}(G)$, and (d) are strictly $G$-alternating. Then
$\mathrm{odd}(\mathrm{AW}_{2r-1}^{\theta}(G))\subseteq\mathcal{T}_{r}^{\theta}$,
and (4.1) shows that it is enough to prove that
$R_{\mathrm{alt}}[\mathrm{AW}_{2r-1}^{\theta}(G)]=\Omega(nd^{r})$ for some
$r\leq 2\mathrm{mix}(R)+1$ and $\theta$.

For $F\in\mathcal{F}_{1}(G)$ let $\mathcal{A}_{i}(F)$ be the set of
$F$-alternating walks $(w_{0},w_{1},\dots,w_{i})$ with
$w_{0}\in\mathrm{IP}_{F}$ and $w_{i}\notin\mathrm{IP}_{F}$. Let
$(w_{0},\dots,w_{i})\in\mathcal{B}_{i}(F)$ if
$(w_{0},\dots,w_{i-1})\in\mathcal{A}_{i-1}(F)$ and $w_{i}\in\mathrm{IP}_{F}$.
Let $\mathcal{A}_{i},\mathcal{B}_{i}$ be the walks which are in
$\mathcal{A}_{i}(F),\mathcal{B}_{i}(F)$ for some $F\in\mathcal{F}_{1}(G)$,
respectively. Note that
$\mathcal{B}_{i}\setminus(\mathcal{C}_{i}\cup\mathcal{D}_{i}^{\theta})\subseteq\mathrm{AW}_{i}^{\theta}(G)$.

Suppose $x\in\mathrm{IP}_{F}$ for some $F\in\mathcal{F}_{1}(G)$. Let
$\pi_{F,x}$ be the simple, lazy $(R,F)$-alternating random walk with starting
vertex $x$, as defined in Section 4.1. Then for all $i\geq 0$, it holds that
$\pi_{F,x}(\mathcal{A}_{2i+1}\cup\mathcal{B}_{2i+1})=\pi_{F,x}(\mathcal{A}_{2i})$
and
$\pi_{F,x}(\mathcal{A}_{2i+2})\geq\frac{1}{2}\pi_{F,x}(\mathcal{A}_{2i+1})$.
For any $j\geq 1$, we conclude that there is a constant $c_{j}$ such that
either $\pi_{F,x}(\mathcal{B}_{2i-1})\geq c_{j}$ for some $1\leq i<j$, or
$\pi_{F,x}(\mathcal{A}_{2j})\geq c_{j}$. We set $j=\mathrm{mix}(R)$, as
defined in (4.5).

For each pair $\\{x,y\\}\in\mathrm{IP}_{2}$ pick some
$F(x,y)\in\mathcal{F}_{1}(G)$ with $\\{x,y\\}\in\mathrm{IP}_{F}$. Define a
random $(R,G)$-alternating walk $\pi$ by

$\pi=\sum_{\\{x,y\\}\in\mathrm{IP}_{2}}\frac{1}{|\mathrm{IP}_{2}|}\left(\frac{\pi_{F(x,y),x}}{2}+\frac{\pi_{F(x,y),y}}{2}\right).$

In other words, we pick a pair $\\{x,y\\}\in\mathrm{IP}_{2}$ uniformly at
random, then pick one of $x,y$ as our starting point with probability $1/2$,
and run the simple, lazy $(R,F(x,y))$-alternating random walk. Note that $\pi$
is near-uniform, as $|\mathrm{IP}_{2}|=\Omega(n^{2})$.

The one-sided case. Suppose $\pi(\mathcal{B}_{2i-1})=\Omega(1)$ for some
$i<j$. Since
$\mathcal{B}_{2i-1}\setminus(\mathcal{C}_{2i-1}\cup\mathcal{D}_{2i-1}^{\theta})\subseteq\mathrm{AW}_{2i-1}^{\theta}$,
Lemmas 4.2 (i) and 4.3 imply

$\displaystyle\pi(\mathrm{AW}_{2i-1}^{\theta}(G))$
$\displaystyle\geq\pi(\mathcal{B}_{2i-1})-\pi(\mathcal{C}_{2i-1})-\pi(\mathcal{D}_{2i-1}^{\theta})=\Omega(1).$
(4.8)

Then (4.7) gives
$R_{\mathrm{alt}}[\mathrm{AW}_{2i-1}^{\theta}(G)]=\Omega(nd^{i})$.

The two-sided case. Suppose $\pi(\mathcal{B}_{2i-1})<c_{j}$ for all $i<j$. Let
$\mathcal{A}_{2j}^{\theta}$ be the set of walks in $\mathcal{A}_{2j}$ which
avoid $\mathcal{D}_{2j}^{\theta}$, and let

$\mathrm{XY}=\left\\{\\{x,y\\}\in\mathrm{IP}_{2}:\pi_{F(x,y),x}(\mathcal{A}_{2j}^{\theta})\geq\frac{c_{j}}{2}\text{
and }\pi_{F(x,y),y}(\mathcal{A}_{2j}^{\theta})\geq\frac{c_{j}}{2}\right\\}.$

Then $|\mathrm{XY}|=\Omega(n^{2})$. Indeed,
$\pi(\mathcal{D}_{2j}^{\theta})=o(1)$ by Lemma 4.2 (i), so

$\displaystyle
c_{j}-o(1)\leq\pi(\mathcal{A}_{2j}^{\theta})\leq\frac{|\overline{\mathrm{XY}}|}{|\mathrm{IP}_{2}|}\frac{c_{j}}{2}+\frac{|\mathrm{XY}|}{|\mathrm{IP}_{2}|}\leq\frac{c_{j}}{2}+\frac{|\mathrm{XY}|}{|\mathrm{IP}_{2}|}.$
(4.9)

Fix some $\\{x,y\\}\in\mathrm{XY}$ and let $F=F(x,y)$. Let
$\mathcal{A}_{x,y}\subseteq\mathcal{A}_{2j}^{\theta}$ be the set of
$F$-alternating walks in $\mathcal{A}_{2j}^{\theta}$ originating at $x$. Note
that
$\mathcal{A}_{x,y}\circ\mathcal{A}_{y,x}\subseteq\mathcal{B}_{4j+1}\setminus\mathcal{D}_{4j+1}^{\theta}$.
We have

$\displaystyle R_{\mathrm{alt}}[\mathcal{A}_{x,y}\circ\mathcal{A}_{y,x}]$
$\displaystyle=\sum_{u,v}R_{\mathrm{alt}}[\mathcal{A}_{x,y}^{\to
u}]R(u,v)R_{\mathrm{alt}}[\mathcal{A}_{y,x}^{\to v}].$ (4.10)

By Lemma 4.1 there exists a constant $\rho>0$ and a set $|U_{x}|\geq\rho n$
such that $\pi_{F,x}(\mathcal{A}_{x,y}^{\to u})\geq\rho/n$ for all $u\in
U_{x}$, and by (4.4) we have

$R_{\mathrm{alt}}[\mathcal{A}_{x,y}^{\to u}]\geq
d^{j}\pi_{F,x}(\mathcal{A}_{x,y}^{\to
u})=\Omega\left({\frac{d^{j}}{n}}\right).$

Likewise, $R_{\mathrm{alt}}[\mathcal{A}_{y,x}^{\to v}]=\Omega(d^{j}/n)$ for
all $v\in U_{y}$ where $|U_{y}|\geq\rho n$. Then (4.10) and Lemma 3.4 imply

$\displaystyle R_{\mathrm{alt}}[\mathcal{A}_{x,y}\circ\mathcal{A}_{y,x}]\geq
R(U_{x},U_{y})\Omega\left({\frac{d^{j}}{n}}\right)^{2}=\Omega\left({\frac{d^{2j+1}}{n}}\right).$
(4.11)

Since
$\mathcal{A}_{x,y}\circ\mathcal{A}_{y,x}\setminus\mathcal{C}_{4j+1}\subseteq\mathrm{AW}_{4j+1}^{\theta}(G)$,
Lemma 4.3 gives

$\displaystyle R_{G}[\mathrm{AW}_{4j+1}^{\theta}(G)]$
$\displaystyle\geq\left(\sum_{(x,y)\in\mathrm{XY}}R_{\mathrm{alt}}[\mathcal{A}_{x,y}\circ\mathcal{A}_{y,x}]\right)-R_{\mathrm{alt}}[\mathcal{C}_{4j+1}]=\Omega(nd^{2j+1}).$
(4.12)

∎

###  4.3 Paths and boosters

We view paths $P=(x=v_{0},\dots,v_{\ell}=y)$ as being directed from $x$ to
$y$, and for any $P$ define a total ordering $\leq_{P}$ of $V$ by
$v_{i}\leq_{P}v_{j}$ whenever $i\leq j$, and $u\leq_{P}v$ whenever $u\in
P,v\notin P$ (arbitrarily ordering the vertices not on $P$).

Suppose ${\bf z}=(z_{1},z_{2},\dots,z_{\ell})$ is a sequence of distinct
vertices on $P$. Define $\tau({\bf z})$ as the permutation of $[\ell]$ for
which $z_{\tau(1)}\leq_{P}z_{\tau(2)}\leq_{P}\dots\leq_{P}z_{\tau(\ell)}$. If
${\bf z}$ repeats a vertex or contains a vertex not on $P$, define $\tau({\bf
z})=\perp$. For a pair of $P$-alternating walks $(X,Y)$ with
$X=(x,x_{1},\dots,x_{i})$ and $Y=(y,y_{1},\dots,y_{2j})$, let
$\tau(X,Y)=\perp$ if $X$ has odd length and $f(X)\in N_{P}(Y)$, and
$\tau(X,Y)=\tau(y_{1},\dots,y_{2j},x_{1},\dots,x_{i})$ otherwise (note that
$\tau=\perp$ is possible in this case as well). See Figure 1.

$x$$y$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x_{1}$$x_{2}$$[1]$$[2]$$[3]$$[4]$$[5]$$[6]$
Figure 1: Two walks $X,Y$ with $\tau(X,Y)=(126543)$. If
$X^{\prime}=(X,x_{3})$, then $\tau(X^{\prime},Y)$ will take the following
values in order as $x_{3}$ increases from $x$ to $y$ and out of $P$: $\perp$,
$(7126543)$, $\perp$, $(1276543)$, $\perp$, $(1265743)$, $\perp$, $(1265437)$,
$\perp$. This sequence is the same for any compatible $X,Y$ with the same
$\tau(X,Y)$, though some values may be skipped.

####  4.3.1 Path rotations

Suppose $P=(v_{0},\dots,v_{\ell})$ is a path of length $\ell$, and let
$e=\\{v_{\ell},v_{i}\\}$ be an edge with $0<i<\ell-1$. Then
$P\triangle(v_{\ell},v_{i},v_{i+1})=(v_{0},\dots,v_{i},v_{\ell},v_{\ell-1},\dots,v_{i+1})$
is also a path of length $\ell$. We say that $(v_{\ell},v_{i},v_{i+1})$ is a
rotation walk of length 2.

In general, suppose $P$ is a path with endpoints $x$ and $y$, and suppose $W$
is a non-repeating even-length strictly $P$-alternating walk starting at $y$
and avoiding $x$. If $P\triangle W$ is a path, we say that $W$ is a rotation
walk for $P$. Let $\mathcal{R}_{2i}(P,y)$ be the set of rotations walks for
$P$ of length $2i$ with starting point $y$. Let $\mathcal{R}_{2i+1}(P,y)$ be
the set of walks $(w_{0},\dots,w_{2i+1})$ with
$(w_{0},\dots,w_{2i})\in\mathcal{R}_{2i}(P,y)$ and $w_{2i+1}\in P$ with
$\mathrm{dist}_{P}(w_{2i+1},\\{w_{0},\dots,w_{2i},x\\})>1$.

Suppose $W=(w_{0},\dots,w_{2i+1})\in\mathcal{R}_{2i+1}(P,y)$ for some $i\geq
0$. Then there is a unique vertex $v\in N_{P}(f(W))$ for which
$(W,v)\in\mathcal{R}_{2i+2}(P,y)$, and we define $r_{P}(W)$ as the path
$(W,v)$. Note that $\tau(r_{P}(W))$ is fully determined by $\tau(W)$, as $v$
is the immediate successor of $u$ along the path $P\triangle W$, viewed as
going from $x$ to $f(W)$.

We will need to consider pairs of rotation walks starting at $x$ and $y$. Let
$\mathcal{A}_{i}(P,x)$ be the set of $P$-alternating walks of length $i$
starting at $x$. For $X\in\mathcal{A}_{i}(P,x)$ and
$Y\in\mathcal{R}_{2j}(P,y)$, say that $(X,Y)$ is a compatible pair if
$X\in\mathcal{R}_{i}(P\triangle Y,x)$, no vertex appears twice in $X\cup Y$,
and $\mathrm{dist}_{P}(f(X),Y)>1$ if $X$ has odd length. For a compatible pair
$(X,Y)$ let $r_{P,Y}(X)=r_{P\triangle Y}(X)$ be the unique walk $(X,v)$ for
which $(r_{P}(X),Y)$ is compatible. Note that $\tau(r_{P,Y}(X),Y)$ is fully
determined by $\tau(X,Y)$.

We summarize this with a lemma. For families of walks $\mathcal{X}$ and
$\mathcal{Y}$, say that $(\mathcal{X},\mathcal{Y})$ is compatible if every
$(X,Y)\in\mathcal{X}\times\mathcal{Y}$ is compatible, and there exists a
permutation $\tau_{0}$ such that $\tau(X,Y)=\tau_{0}$ for all
$(X,Y)\in\mathcal{X}\times\mathcal{Y}$.

######  Lemma 4.6.

Let $i,j\geq 0$. Suppose $\mathcal{X}\subseteq\mathcal{A}_{2i+1}(P,x)$ and
$\mathcal{Y}\subseteq\mathcal{R}_{2j}(P,y)$ are such that
$(\mathcal{X},\mathcal{Y})$ is compatible. Let
$r_{P,\mathcal{Y}}(\mathcal{X})=\\{r_{P,Y}(X):X\in\mathcal{X},Y\in\mathcal{Y}\\}\subseteq\mathcal{A}_{2i+2}(P,x)$.
Then $(r_{P,\mathcal{Y}}(\mathcal{X}),\mathcal{Y})$ is compatible.

###### Proof.

This follows from the fact that $\tau(r_{P,Y}(X),Y)$ is fully determined by
$\tau(X,Y)$, which is constant on $\mathcal{X}\times\mathcal{Y}$. ∎

The relevance of compatible walks is this: if $(\mathcal{X},\mathcal{Y})$ is a
compatible pair of families of even-length walks, then $P\triangle(X\circ Y)$
is a cycle of length $\ell+1$ for every
$(X,Y)\in\mathcal{X}\times\mathcal{Y}$.

####  4.3.2 Boosters

Suppose $G\in\mathrm{SE}_{2}$ has $s_{2}(G)<n$, and let $\mathcal{F}_{2}(G)$
be the set of paths and cycles $F\subseteq G$ with $|F|=s_{2}(G)$. We first
take care of a special case.

######  Lemma 4.7.

Suppose $G\in\mathrm{SE}_{2}$ and that $\mathcal{F}_{2}(G)$ contains a cycle.
Let $\mathrm{BW}_{1}(G)$ denote the set of edges $e$ such that
$s_{2}(G+e)>s_{2}(G)$. Then $R_{G}[\mathrm{BW}_{1}(G)]=\Omega(dn)$.

###### Proof.

The family $\mathcal{F}_{2}(G)$ contains a cycle $C$ only if the vertex set
$U$ of $C$ forms a connected component in $G$. Since $G$ expands, any
connected component has size between $\beta n$ and $(1-\beta)n$. Since
$U\times\overline{U}\subseteq\mathrm{BW}_{1}(G)$, by Lemma 3.4 we have
$R_{G}[\mathrm{BW}_{1}(G)]\geq R(U,\overline{U})=\Omega(dn)$. ∎

Now suppose $\mathcal{F}_{2}(G)$ contains only paths. For $U\subseteq V$, let
$\mathrm{EP}_{2}(U)$ be the set of ordered pairs $(x,y)$ such that some
$P\in\mathcal{F}_{2}(G)$ has endpoints $x$ and $y$, and $V(P)=U$.

######  Lemma 4.8.

Suppose $G\in\mathrm{SE}_{2}$ with $s_{2}(G)<n$. Then there exists some
$U\subseteq V$ with $|\mathrm{EP}_{2}(U)|\geq(\beta n)^{2}$.

###### Proof.

Pósa’s lemma (see e.g. [12]) shows that if $\\{x,y\\}\in\mathrm{EP}_{2}(U)$
for some $x,y$, then the set $Y=\\{y:\\{x,y\\}\in\mathrm{EP}_{2}(U)\\}$ has
$|N_{G}(Y)|<2|Y|$. Since $G\in\mathrm{SE}_{2}$ we then have $|Y|\geq\beta n$,
and the lemma follows just like in Lemma 4.4, this time considering ordered
pairs. ∎

We prove the analogue of Proposition 4.5 for paths. For a graph $G$, integer
$r\geq 1$, and $\theta$ tending to infinity, let $\mathcal{T}_{r}^{\theta}(G)$
be the family of edge sets $|T|=r$ such that no $e\in T$ is contained in $G$
or incident to $S_{\theta}$, and $s_{2}(G\cup T)>s_{2}(G)$.

######  Proposition 4.9.

Suppose $R\in\mathrm{RM}$ and $G\in\mathrm{SE}_{2}$ with $s_{2}(G)<n$. Then
there exists an $r\leq 2\mathrm{mix}(R)+1$ such that if $\theta$ tends to
infinity sufficiently slowly, then

$R_{G}[\mathcal{T}_{r}^{\theta}]=\Omega(nd^{r}).$

###### Proof.

Lemma 4.7 takes care of the case when $\mathcal{F}_{2}(G)$ contains a cycle;
it only remains to note that the set $E_{\theta}$ of edges incident to
$S_{\theta}$ has $R[E_{\theta}]=o(nd)$ by the degree condition (1.2). Assume
$\mathcal{F}_{2}(G)$ contains no cycles.

For a graph $G$ and integer $r\geq 0$, let $\mathrm{BW}_{2r-1}^{\theta}(G)$ be
the family of walks $W$ of length $2r-1$ such that (a) $W$ is $P$-alternating
for some $P\in\mathcal{F}_{2}(G)$, (b) $W$ is strictly $G$-alternating, (c) no
vertex appears more than once in $W$, (d) $W$ avoids $S_{\theta}$, and (e)
$s_{2}(P\triangle W)>s_{2}(P)$. By (4.1), it is enough to show that
$R_{\mathrm{alt}}[\mathrm{BW}_{2r-1}^{\theta}(G)]=\Omega(nd^{r})$ for some
$r\leq 2\mathrm{mix}(R)+1$.

Suppose $P$ is a path from $x$ to $y$ on vertex set $U$. Define
$\mathcal{R}_{i}(P,y)$ as in Section 4.3.1. For $i\geq 0$, let
$\mathcal{B}_{2i+1}(P,y)$ be the set of walks $(w_{0},\dots,w_{2i+1})$ with
$(w_{0},\dots,w_{2i})\in\mathcal{R}_{2i}$ and
$w_{2i+1}\in\\{x\\}\cup\overline{U}$, and note that $s_{2}(P\triangle
W)>s_{2}(P)$ for $W\in\mathcal{B}_{2i+1}$.

We define $\mathrm{rot}_{P,y}$ as a random $(R,P)$-alternating walk initated
at $y$ with

$\displaystyle\mathrm{rot}_{P,y}(r_{P}(Y)\mid Y)$ $\displaystyle=1,\quad
Y\in\mathcal{R}_{2i+1}(P,y).$ (4.13)

This satisfies

$\displaystyle\mathrm{rot}_{P,y}(\mathcal{R}_{2i+2})$
$\displaystyle=\mathrm{rot}_{P,y}(\mathcal{R}_{2i+1}),$ (4.14)
$\displaystyle\mathrm{rot}_{P,y}(\mathcal{R}_{2i+1}\cup\mathcal{B}_{2i+1})$
$\displaystyle\geq(1-o(1))\mathrm{rot}_{P,y}(\mathcal{R}_{2i}).$ (4.15)

Indeed, if
$W=(w_{0},\dots,w_{2i+1})\notin\mathcal{R}_{2i+1}\cup\mathcal{B}_{2i+1}$ while
$(w_{0},\dots,w_{2i})\in\mathcal{R}_{2i}$, then
$\mathrm{dist}_{P}(w_{2i+1},\\{w_{0},\dots,w_{2i},x\\})<2$, which happens with
probability $o(1)$. We conclude that for any constant $j\geq 1$,

$\mathrm{rot}_{P,y}(\mathcal{R}_{2j})+\sum_{i=0}^{j-1}\mathrm{rot}_{P,y}(\mathcal{B}_{2i+1})=1-o(1).$
(4.16)

For each $(x,y)\in\mathrm{EP}_{2}(U)$ pick some $P(x,y)\in\mathcal{F}_{2}(G)$
on $U$, with $P(x,y)$ and $P(y,x)$ each other’s reverses. Define a random
$(R,G)$-alternating walk

$\mathrm{rot}=\sum_{(x,y)\in\mathrm{EP}_{2}(U)}\frac{1}{|\mathrm{EP}_{2}(U)|}\mathrm{rot}_{P(x,y),y}.$

Since $|\mathrm{EP}_{2}(U)|=\Omega(n^{2})$, this is near-uniform. Let
$j=\mathrm{mix}(R)$, and pick $\theta\leq\lambda(R)^{-1/4}$ so that
$\theta^{4j+1}\|M\|=o(1)$.

The one-sided case. Suppose $s_{2}(G)=n-\Omega(n)$. Then
$|\overline{U}|=\Omega(n)$, and $\\{\tau(\overline{U})\leq
1\\}\subseteq\mathcal{B}_{1}$. By Lemma 4.2, we have

$\mathrm{rot}(\mathcal{B}_{1}\setminus\mathcal{D}_{1}^{\theta})=\Omega(1).$

Since $\mathrm{rot}$ is near-uniform, (4.7) shows that
$R_{\mathrm{alt}}[\mathcal{B}_{1}\setminus\mathcal{D}_{1}^{\theta}]=\Omega(nd)$.
Since
$\mathcal{B}_{1}\setminus\mathcal{D}_{1}^{\theta}\subseteq\mathrm{BW}_{1}^{\theta}(G)$,
that finishes this case.

The two-sided case. Suppose $s_{2}(G)=n-o(n)$. Then $\overline{U}=o(n)$, and
Lemma 4.2 gives $\mathrm{rot}(\tau(\overline{U}\cup S_{\theta})\leq 2j)=o(1)$,
so $\mathrm{rot}(\mathcal{R}_{2j})=1-o(1)$. Then there exists a set
$\mathrm{XY}\subseteq\mathrm{EP}_{2}$ such that all $(x,y)\in\mathrm{XY}$ have
$\mathrm{rot}_{P(x,y),x}(\mathcal{R}_{2j}^{\theta})=1-o(1)$ and
$\mathrm{rot}_{P(x,y),y}(\mathcal{R}_{2j}^{\theta})=1-o(1)$.

Fix $(x,y)\in\mathrm{XY}$ and let $P=P(x,y)$, directed from $x$ to $y$. We
will construct a compatible pair $(\mathcal{X}_{2j},\mathcal{Y}_{2j})$ of
families of walks of length $2j$. Then
$\mathcal{X}_{2j}\circ\mathcal{Y}_{2j}\subseteq\mathcal{B}_{4j+1}(P,y)$, and
we can apply the same techniques that we used for matchings.

Construction of $\mathcal{X}_{i},\mathcal{Y}_{i}$. Initially let
$\mathcal{X}_{0}=\\{(x)\\}$. Let $\tau_{0}$ be a permutation such that
$\mathrm{rot}_{P,y}(\tau((x),Y)=\tau_{0})\geq\mathrm{rot}_{P,y}(\mathcal{R}_{2j}(P,y))/2^{j}$,
and let $\mathcal{Y}_{0}$ be the set of $Y\in\mathcal{R}_{2j}(P,y)$ with
$\tau((x),Y)=\tau_{0}$. For $i=1,\dots,2j$ we inductively construct compatible
families $\mathcal{X}_{i},\mathcal{Y}_{i}$ with
$\mathrm{rot}_{P,x}(\mathcal{X}_{i})\geq c_{i,j}$ and
$\mathrm{rot}_{P,y}(\mathcal{Y}_{i})\geq c_{i,j}$, where $c_{i,j}=(3j)^{-2i}$
for $i=1,\dots,2j$.

Construction, odd $i$. Suppose $(\mathcal{X}_{i-1},\mathcal{Y}_{i-1})$ is a
compatible pair of families. Define $\mathcal{X}_{i}^{\prime}$ as the set of
one-step extensions of $\mathcal{X}_{i-1}$:

$\mathcal{X}_{i}^{\prime}=\\{(x_{0},\dots,x_{i-1},v):(x_{0},\dots,x_{i-1})\in\mathcal{X}_{i-1},v\in
V\\}.$

We aim to apply Lemma 3.7 to $\tau(X,Y)$ for
$(X,Y)\in\mathcal{X}_{i}^{\prime}\times\mathcal{Y}_{i-1}$. In order to do
this, we need to define a total ordering on $\mathcal{X}_{i}^{\prime}$ such
that $X\mapsto\tau(X,Y)$ respects some common sequence for all
$Y\in\mathcal{Y}_{i-1}$.

Let $\leq_{\tau}$ be some arbitrary ordering of the set
$\tau(\mathcal{X}_{i}^{\prime})=\\{\tau(X):X\in\mathcal{X}_{i}^{\prime}\\}$.
Note that $|\tau(\mathcal{X}_{i}^{\prime})|\leq i+1$. Define a total ordering
$\leq$ on $\mathcal{X}_{i}^{\prime}$ such that $X_{1}\leq X_{2}$ whenever
$\tau(X_{1})\leq_{\tau}\tau(X_{2})$, or $\tau(X_{1})=\tau(X_{2})$ and
$f(X_{1})\leq_{P}f(X_{2})$.

Let $\tau^{\prime}\in\tau(\mathcal{X}_{i}^{\prime})$ and consider the set
$\mathcal{X}_{i}^{\prime}(\tau^{\prime})$ of $X\in\mathcal{X}_{i}^{\prime}$
with $\tau(X)=\tau^{\prime}$. Restricted to this set, our ordering orders
walks by their final vertex. Suppose
$X_{1},X_{2}\in\mathcal{X}_{i}^{\prime}(\tau^{\prime})$ and
$Y\in\mathcal{Y}_{i-1}$ are such that $f(X_{1})\leq_{P}f(X_{2})$ with no
vertex of $Y$ in the interval $[f(X_{1}),f(X_{2})]$ (note that no vertex of
$X_{1}\cup X_{2}$ is in this interval as then $\tau(X_{1})\neq\tau(X_{2})$).
Then $\tau(X_{1},Y)=\tau(X_{2},Y)$.

As $X$ runs through $\mathcal{X}_{i}^{\prime}(\tau^{\prime})$ according to the
ordering $\leq$, the value of $\tau(X,Y)$ changes only when $f(X)$ enters or
exits $\widehat{N}_{P}(Y)$, which happens at most $2j+1$ times. This shows
that the map $X\mapsto(X,Y)$, restricted to
$\mathcal{X}_{i}^{\prime}(\tau^{\prime})$, respects some sequence of length at
most $2j+2$, common to all $Y\in\mathcal{Y}_{i}$ (see Figure 1). Since
$|\tau(\mathcal{X}_{i}^{\prime})|\leq i+1$, the sequence $X\mapsto\tau(X,Y)$
on all of $\mathcal{X}_{i}^{\prime}$ respects some common sequence of length
at most $\ell=2i(j+1)\leq(3j)^{2}$.

We apply Lemma 3.7 with measures $\mathrm{rot}_{P,x}$ and $\mathrm{rot}_{P,y}$
on $\mathcal{X}_{i}^{\prime}$ and $\mathcal{Y}_{i-1}$, respectively. The lemma
asserts that there exist sets
$\mathcal{X}_{i}\subseteq\mathcal{X}_{i}^{\prime}$ and
$\mathcal{Y}_{i}\subseteq\mathcal{Y}_{i-1}$ such that $\tau$ is constant on
$\mathcal{X}_{i}\times\mathcal{Y}_{i}$, and

$\mathrm{rot}_{P,x}(\mathcal{X}_{i})\geq\frac{\mathrm{rot}_{P,x}(\mathcal{X}_{i-1})}{\ell}\quad\text{
and
}\quad\mathrm{rot}_{P,y}(\mathcal{Y}_{i})\geq\frac{\mathrm{rot}_{P,y}(\mathcal{Y}_{i-1})}{\ell}.$

By induction, both quantities are at least $c_{i-1,j}/\ell\geq c_{i,j}$. Note
that if $\tau(X,Y)=\perp$ then either $X\in\mathcal{B}_{i}(P\triangle Y,x)$,
or $\mathrm{dist}_{P}(f(X),Y)<2$. The latter has probability
$O(\|M\||Y|)=o(1)$. Since $(x,y)\in\mathrm{XY}$, for any
$Y\in\mathcal{Y}_{i-1}$ we then have

$\mathrm{rot}_{P,x}(\tau(\ \cdot\
,Y)=\perp)\leq\mathrm{rot}_{P,x}(\tau(\overline{U})\leq i)+o(1)=o(1).$

We conclude that the common value of $\tau$ on
$\mathcal{X}_{i}\times\mathcal{Y}_{i}$ is not $\perp$, so
$(\mathcal{X}_{i},\mathcal{Y}_{i})$ is compatible.

Construction, even $i$. Suppose $\mathcal{X}_{i-1},\mathcal{Y}_{i-1}$ have
been constructed. Lemma 4.6 shows that
$\mathcal{X}_{i}=r_{P,\mathcal{Y}_{i-1}}(\mathcal{X}_{i-1})$ and
$\mathcal{Y}_{i}=\mathcal{Y}_{i-1}$ are compatible. We have
$\mathrm{rot}_{P,x}(\mathcal{X}_{i})=\mathrm{rot}_{P,x}(\mathcal{X}_{i-1})$.

Gluing. We proceed exactly as in (4.11) to obtain

$\displaystyle R_{\mathrm{alt}}[\mathcal{X}_{2j}\circ\mathcal{Y}_{2j}]$
$\displaystyle=\sum_{u,v}R_{\mathrm{alt}}[\mathcal{X}_{2j}^{\to
u}]R(u,v)R_{\mathrm{alt}}[\mathcal{Y}_{2j}^{\to
v}]=\Omega\left({\frac{d^{2j+1}}{n}}\right).$ (4.17)

Since
$\mathcal{X}_{2j}\circ\mathcal{Y}_{2j}\setminus(\mathcal{C}_{4j+1}\cup\mathcal{D}_{4j+1}^{\theta})\subseteq\mathrm{BW}_{4j+1}^{\theta}(G)$
for any $(x,y)\in\mathrm{XY}$, summing over $(x,y)\in\mathrm{XY}$ and applying
Lemmas 4.2 (i) and 4.3 gives

$R_{\mathrm{alt}}[\mathrm{BW}_{4j+1}^{\theta}(G)]=\Omega(nd^{2j+1})-o(nd^{2j+1}).$

∎

##  5 Sprinkling

Suppose $X$ is a finite set, $p:X\to[0,1]$ a function, and
$\mathcal{G}=(X,\mathcal{E})$ a graph. Let $X_{p}\subseteq X$ be the random
set obtained by independently including any $x\in X$ with probability $p(x)$.
Suppose for some $r\geq 1$ that $\mathcal{T}$ is a set of paths on $r$
vertices in $\mathcal{G}$. We are interested in the probability that some
$T\in\mathcal{T}$ is contained in $X_{p}$.

For a set $A\subseteq X$ write $p(A)=\sum_{x\in A}p(x)$ and $p[A]=\prod_{x\in
A}p(x)$, and for a family $\mathcal{A}$ of sets write
$p[\mathcal{A}]=\sum_{A\in\mathcal{A}}p[A]$. Let $\Delta$ be the maximum value
of $p(N_{\mathcal{G}}(x))$ for $x\in X$.

######  Lemma 5.1.

Suppose $r\geq 1$ is an integer, and $\mathcal{T}$ is a set of paths on $r$
vertices in $\mathcal{G}=(X,\mathcal{E})$, such that $p[\mathcal{T}]\geq
6(3\Delta)^{r-2}p(X)$. Then

$\displaystyle{\mbox{Pr}\left\\{T\nsubseteq X_{p},\text{ all
$T\in\mathcal{T}$}\right\\}}\leq\exp\left\\{-\frac{p[\mathcal{T}]}{(3\Delta)^{r-1}r^{r}}\right\\}.$
(5.1)

We begin our proof with the following lemma.

######  Lemma 5.2.

Suppose $r>1$. Let $\mathcal{T}_{1}$ be the random set of paths
$(x_{2},\dots,x_{r})$ such that $(x_{1},\dots,x_{r})\in\mathcal{T}$ for some
$x_{1}\in X_{p}$. If $p[\mathcal{T}]\geq 6\Delta^{r-2}p(X)$, then

$\displaystyle{\mbox{Pr}\left\\{p[\mathcal{T}_{1}]<\frac{p[\mathcal{T}]}{3\Delta}\right\\}}\leq\exp\left\\{-\frac{p[\mathcal{T}]}{3\Delta^{r-1}}\right\\}.$
(5.2)

###### Proof.

For $x\in X$ let $\mathcal{Q}(x)$ be the set of $(x_{2},\dots,x_{r})$ such
that $(x,x_{2},\dots,x_{r})\in\mathcal{T}$. For $S\subseteq X$ let
$\mathcal{Q}(S)=\cup_{x\in S}\mathcal{Q}(x)$. For $S\subseteq X$ and $x\notin
S$, say that $x$ is $S$-useful if

$p[\mathcal{Q}(x)\setminus\mathcal{Q}(S)]\geq\frac{p[\mathcal{T}]}{3p(X)}.$

######  Claim 5.1.

Suppose $S\subseteq X$ has $p(\mathcal{Q}(S))<p[\mathcal{T}]/3\Delta$. Then
the set $U\subseteq X\setminus S$ of $S$-useful elements has $p(U)\geq
p[\mathcal{T}]/3\Delta^{r-1}$.

###### Proof of Claim 5.1.

For $T=(x_{2},\dots,x_{r})$ let $\mathcal{Q}^{-1}(T)$ be the set of $x$ such
that $(x,x_{2},\dots,x_{r})\in\mathcal{T}$. Then $\mathcal{Q}^{-1}(T)\subseteq
N_{\mathcal{G}}(x_{2})$, and $p(\mathcal{Q}^{-1}(T))\leq\Delta$. Let
$\mathcal{M}(S)$ be the set of $(x_{1},\dots,x_{r})\in\mathcal{T}$ with
$(x_{2},\dots,x_{r})\notin\mathcal{Q}(S)$. Then

$p[\mathcal{M}(S)]\geq p[\mathcal{T}]-\Delta
p(\mathcal{Q}(S))\geq\frac{2}{3}p[\mathcal{T}].$ (5.3)

For any $x\in X$ we have $p[\mathcal{Q}(x)]\leq\Delta^{r-1}$, so

$\displaystyle p[\mathcal{M}(S)]$ $\displaystyle\leq\sum_{x\notin
S}p(x)p[\mathcal{Q}(x)\setminus\mathcal{Q}(S)]$ (5.4) $\displaystyle\leq
p(U)\Delta^{r-1}+p(X\setminus S)\frac{1}{3}\frac{p[\mathcal{T}]}{p(X)}\leq
p(U)\Delta^{r-1}+\frac{1}{3}p[\mathcal{T}].$ (5.5)

Combining (5.3) and (5.5) gives $p(U)\geq p[\mathcal{T}]/3\Delta^{r-1}$. ∎

Consider sampling $S\subseteq X_{p}$ by the following procedure.

  1. 1.

Initially let $S_{0}=\emptyset$ and $Z_{0}=\emptyset$. Set $i=1$.

  2. 2.

Let $x_{i}\notin Z_{i-1}$ be an $S_{i-1}$-useful element. Let
$Z_{i}=Z_{i-1}\cup\\{x_{i}\\}$, and with probability $p(x_{i})$ let
$S_{i}=S_{i-1}\cup\\{x_{i}\\}$, otherwise let $S_{i}=S_{i-1}$.

  3. 3.

If $p[\mathcal{Q}(S_{i})]\geq p[\mathcal{T}]/3\Delta$, declare success and end
the procedure. If $p(Z_{i})\geq p[\mathcal{T}]/3\Delta^{r-1}$, declare failure
and end the procedure. Otherwise, increase $i$ by 1 and go to step 2.

By Claim 5.1, Step 2 can be carried out as long as neither success nor failure
has been declared, since then $p(U\setminus Z_{i-1})>0$ where $U$ is the set
of $S_{i-1}$-useful elements.

Since each $x_{i}$ is $S_{i-1}$-useful at time of sampling, we have

$p[\mathcal{Q}(S_{\ell})]\geq\frac{p[\mathcal{T}]}{3p(X)}\sum_{i=1}^{\ell}\xi_{i},$

where the $\xi_{i}$ are independent indicator random variables. Letting
$\xi(\ell)=\sum_{i\leq\ell}\xi_{i}$, we have
$\mathbb{E}\left[\xi(\ell)\right]=p(Z_{\ell})$. If failure is declared, there
exists some $\ell$ for which $p(Z_{\ell})\geq p[\mathcal{T}]/3\Delta^{r-1}$
while $\xi(\ell)<p(X)/\Delta=o(p(Z_{\ell}))$. By the Chernoff bound (3.2) we
have

$\displaystyle{\mbox{Pr}\left\\{\xi(\ell)<\frac{p(X)}{\Delta}\text{ and
}p(Z_{\ell})\geq\frac{p[\mathcal{T}]}{3\Delta^{r-1}}\right\\}}\leq\exp\left\\{-\frac{p[\mathcal{T}]}{24\Delta^{r-1}}\right\\}.$
(5.6)

Since $p[\mathcal{T}_{1}]\geq p[\mathcal{Q}(S_{\ell})]$, the lemma follows. ∎

We can now prove Lemma 5.1.

###### Proof of Lemma 5.1.

If $r=1$ then $\mathcal{T}$ is a collection of elements of $X$, and

${\mbox{Pr}\left\\{\mathcal{T}\cap
X_{p}=\emptyset\right\\}}=\prod_{x\in\mathcal{T}}(1-p(x))\leq
e^{-p[\mathcal{T}]}.$ (5.7)

Suppose $r>1$. Let $X_{1},\dots,X_{r}$ be independent random subsets of $X$,
each sampling any $x\in X$ with probability $p^{\prime}(x)=p(x)/r$. Then any
$x$ is independently in $X_{1}\cup\dots\cup X_{r}$ with probability
$1-(1-p(x)/r)^{r}\leq p(x)$.

Let $\mathcal{T}_{0}=\mathcal{T}$, and for $0<i<r$ let $\mathcal{T}_{i}$ be
the random set of $(x_{i+1},\dots,x_{r})$ such that
$(x_{1},\dots,x_{i},x_{i+1},\dots,x_{r})\in\mathcal{T}$ for some $x_{j}\in
X_{j}$, $1\leq j\leq i$.

Let $\mathcal{E}_{i}$ denote the event that $p^{\prime}[\mathcal{T}_{i}]\geq
p^{\prime}[\mathcal{T}]/(3\Delta)^{i}$. Lemma 5.2 shows that for $0<i<r$,

$\displaystyle{\mbox{Pr}\left\\{\overline{\mathcal{E}_{i}}\mid\mathcal{E}_{i-1}\right\\}}\leq\exp\left\\{-\frac{1}{3^{i}\Delta^{r-1}}p^{\prime}[\mathcal{T}]\right\\}.$
(5.8)

We then have

${\mbox{Pr}\left\\{\overline{\mathcal{E}_{r-1}}\right\\}}\leq\sum_{i=1}^{r-1}{\mbox{Pr}\left\\{\overline{\mathcal{E}_{i}}\mid\mathcal{E}_{i-1}\right\\}}\leq(r-1)\exp\left\\{-\left({\frac{1}{3\Delta}}\right)^{r-1}p[\mathcal{T}]\right\\}.$

Finally, note that $\mathcal{T}_{r-1}$ is a set of elements in $X$. Repeating
the argument behind (5.7) gives

${\mbox{Pr}\left\\{T\nsubseteq X_{p},\text{ all
$T\in\mathcal{T}$}\mid\mathcal{E}_{r-1}\right\\}}\leq\exp\left\\{-\left({\frac{1}{3\Delta}}\right)^{r-1}p^{\prime}[\mathcal{T}]\right\\}.$

With $p^{\prime}[\mathcal{T}]=p[\mathcal{T}]/r^{r}$, this finishes the proof.
∎

##  6 Finishing the high-level proof

We can now prove Lemma 2.3. Suppose $R\in\mathrm{RM}$ and
$G\in\mathrm{SE}_{i}$ with $s_{i}(G)<\left\lfloor in/2\right\rfloor$ for some
$i\in\\{1,2\\}$. Note that $d=\Theta(\ln n)$ since $\gamma_{1}(R)=1$. Let
$\theta$ tend to infinity arbitrarily slowly, and let $E_{\theta}$ be the set
of edges incident to $S_{\theta}=S_{\theta}(R,G)$. Propositions 4.5 and 4.9
show, for $i=1,2$ respectively, that there exists an $r\leq
2\mathrm{mix}(R)+1$ and a set $\mathcal{T}_{r}$ of edge sets $T$ with $|T|=r$
and $T\cap(G\cup E_{\theta})=\emptyset$ such that

$R_{G}[\mathcal{T}_{r}]=\sum_{T\in\mathcal{T}_{r}}\prod_{uv\in
T}R(u,v)=\Omega(nd^{r}).$

Suppose $E$ is an edge set with $R(E)=o(n\ln n)$, and that $p$ satisfies
$p(u,v)\geq R(u,v)/3$ for all $\\{u,v\\}\notin E$. Let
$X=\binom{V}{2}\setminus(G\cup E_{\theta})$. We then have

$\displaystyle{\mbox{Pr}\left\\{s_{i}(G^{p})=s_{i}(G)\right\\}}={\mbox{Pr}\left\\{T\nsubseteq
X_{p},\text{ all $T\in\mathcal{T}_{r}$}\right\\}}.$ (6.1)

Let $\mathcal{G}=(X,\mathcal{E})$ be the graph on $X$ where
$u_{1}v_{1},u_{2}v_{2}\in X$ are adjacent if $G$ contains an edge between
$\\{u_{1},v_{1}\\}$ and $\\{u_{2},v_{2}\\}$. Then

$\Delta=\max_{uv\in X}p(N_{\mathcal{G}}(uv))\leq 2\theta d.$

Let $\mathcal{T}_{r}(E)$ be the set of $T\in\mathcal{T}_{r}$ which intersect
$E$. Picking $\theta$ so that $R(E)\theta^{r-1}=o(nd)$, we have

$R_{G}[\mathcal{T}_{r}(E)]\leq R(E)\Delta^{r-1}=o(nd^{r}).$

It follows that

$p[\mathcal{T}_{r}]\geq\frac{1}{3}R_{G}[\mathcal{T}_{r}\setminus\mathcal{T}_{r}(E)]=\Omega(nd^{r}).$

Note that $p(X)=O(nd)$. Lemma 5.1 then gives

${\mbox{Pr}\left\\{T\nsubseteq X_{p},\text{ all
$T\in\mathcal{T}_{r}$}\right\\}}=\exp\left\\{-\Omega\left({\frac{nd^{r}}{\Delta^{r-1}}}\right)\right\\}=\exp\left\\{-\Omega\left({\frac{nd}{\theta^{r-1}}}\right)\right\\}.$

Letting $\theta^{r-1}=o(\sqrt{d})$ and recalling that $d=\Theta(\ln n)$
finishes the proof.

##  7 Proofs for Section 4.1: alternating walks mix

Suppose $G$ is a graph and $R$ a rate matrix on $V$, with associated
transition matrix $M$. In Section 4.1 we defined the simple, lazy
$(R,G)$-alternating random walk, which is a special case of the following
definition. Recall that $\widehat{N}(A)=A\cup N(A)$.

######  Definition 7.1.

Given a graph $G$, a random walk $\pi$ on $V$ is a random $(R,G)$-alternating
walk if the following hold for all $j\geq 0$:

$\displaystyle\pi(w_{2j+1}\mid w_{0},\dots,w_{2j})$
$\displaystyle=M(w_{2j},w_{2j+1}),$ (7.1) $\displaystyle\pi(w_{2j+2}\mid
w_{0},\dots,w_{2j+1})$ $\displaystyle=0,\quad
w_{2j+2}\notin\widehat{N}_{G}(w_{2j+1}).$ (7.2)

In short, a random $(R,G)$-alternating walk alternates between memoryless
transitions weighted by $M$, and (lazy) steps restricted to the edges of $G$.
We use $\pi_{j}$ to denote the measure induced by the $j$–th vertex $w_{j}$,
and note that the initial distribution $\pi_{0}$ may be any distribution on
$V$.

Before going into mixing of the random $(R,G)$-alternating walk, we restate
and prove Lemma 4.3. Define $S_{\theta}$ as the set of vertices $u$ with
$d_{G}(u)\geq\theta$ or $d_{R}(u)\geq\theta d$, and say that a walk avoids
$S_{\theta}$ if it contains no vertex of $S_{\theta}$.

######  Lemma 7.2.

Suppose $R\in\mathrm{RM}$ and that $G$ is light-tailed, and let $j=O(1)$. Let
$\mathcal{C}_{j}^{\theta}$ be the set of $G$-alternating walks of length $j$
which avoid $S_{\theta}$ and either (a) repeat some vertex, or (b) are not
strictly $G$-alternating. If $\theta^{j+1}\|M\|=o(1)$ then
$R_{\mathrm{alt}}[\mathcal{C}_{j}^{\theta}]=o(nd^{\left\lceil
j/2\right\rceil})$.

###### Proof.

If a $G$-alternating walk $W=(w_{0},\dots,w_{j})$ repeats a vertex or has
$\\{w_{2i},w_{2i+1}\\}\in G$ for some $i$, there must exist some $i$ such that
$w_{2i+1}\in\widehat{N}_{G}(w_{0},\dots,w_{2i})$. If $d_{G}(w_{i})<\theta$ for
all $i$, then

$M(w_{2i},\widehat{N}_{G}(w_{0},\dots,w_{2i}))\leq\|M\|(2i+1)\theta,$

so $\pi(\mathcal{C}_{j}^{\theta})=O(\theta\|M\|)$ for any random
$(R,G)$-alternating walk $\pi$. Note that for any walk $W=(w_{0},\dots,w_{j})$
which avoids $S_{\theta}$,

$R_{\mathrm{alt}}[W]\leq\prod_{i=0}^{\left\lceil
j/2\right\rceil-1}\frac{\theta
d}{d_{R}(w_{2i})}R(w_{2i},w_{2i+1})\prod_{i=0}^{\left\lfloor
j/2\right\rfloor-1}\frac{\theta}{d_{G}(w_{2i-1})+1}\\\
\leq\theta^{j}d^{\left\lceil j/2\right\rceil}\times n\pi_{G}(W),$ (7.3)

where $\pi_{G}$ is the simple, lazy $(R,G)$-alternating walk initiated at a
vertex chosen uniformly at random. Since $\theta^{j+1}\|M\|=o(1)$, it follows
that $R_{\mathrm{alt}}[\mathcal{C}_{j}^{\theta}]=o(nd^{\left\lceil
j/2\right\rceil})$.

∎

###  7.1 Mixing for the random alternating walk

The $R$-steps of the $(R,G)$-alternating walk gets $\pi_{j}$ closer to
stationarity by Lemma 3.8, while the $G$-steps may pull it back. The following
lemma bounds the harm done.

######  Lemma 7.3.

Suppose $R\in\mathrm{RM}$ with $\lambda(R)=\lambda$ and stationary
distribution $\sigma$. Suppose $\pi$ is a random $(R,G)$-alternating walk for
some graph $G$ with maximum degree $\theta-1$ and $d_{G}(u)=0$ whenever
$d_{R}(u)\geq\theta d$. Then for $i\geq 0$,

$\displaystyle\mu_{\sigma}(\pi_{2i+1})$
$\displaystyle\leq\lambda\mu_{\sigma}(\pi_{2i}),$ (7.4)
$\displaystyle\mu_{\sigma}(\pi_{2i+2})^{2}$
$\displaystyle\leq\theta^{4}\left(\mu_{\sigma}(\pi_{2i+1})^{2}+1\right).$
(7.5)

In particular, if $\lambda\theta^{2}=o(1)$ then for all $i\geq 0$,

$\mu_{\sigma}(\pi_{2i+1})^{2}\leq\lambda^{2i}\theta^{4i}\mu_{\sigma}(\pi_{1})^{2}+O(\lambda^{2}\theta^{4}).$
(7.6)

###### Proof.

Lemma 3.8 immediately gives (7.4), and we prove (7.5). Note that for any
$i\geq 1$ and $u\in V$,

$\displaystyle\pi_{2i}(u)$
$\displaystyle=\sum_{v\in\widehat{N}(u)}\pi_{2i-1}(v)\pi(w_{2i}=u\mid
w_{2i-1}=v)\leq\theta\max_{v\in\widehat{N}(u)}\pi_{2i-1}(v).$ (7.7)

Suppose $v\in\widehat{N}(u)$. Then $u=v$ or $d_{R}(u)\leq\theta d$, since
$d_{G}(u)=0$ whenever $d_{R}(u)\geq\theta d$. Since $d_{R}(v)\geq d$, in
either case we conclude that
$\sigma(u)/\sigma(v)=d_{R}(u)/d_{R}(v)\leq\theta$, and

$\displaystyle\mu_{\sigma}(\pi_{2i})^{2}$
$\displaystyle\leq\sum_{v}\frac{\pi_{2i}(v)^{2}}{\sigma(v)}\leq\sum_{v}\frac{\theta^{2}}{\sigma(v)}\max_{u\in\widehat{N}(v)}\pi_{2i-1}(u)^{2}.$
(7.8)

Any vertex $u$ is counted at most $\theta$ times in this sum, so

$\displaystyle\mu_{\sigma}(\pi_{2i})^{2}\leq\theta^{3}\sum_{u}\frac{\pi_{2i-1}(u)^{2}}{\sigma(u)}\max_{v\in\widehat{N}(u)}\frac{\sigma(u)}{\sigma(v)}\leq\theta^{4}\left(\mu_{\sigma}(\pi_{2i-1})^{2}+1\right).$
(7.9)

This shows (7.5). Repeatedly applying (7.4) and (7.5) with
$\lambda\theta^{2}=o(1)$ gives (7.6). ∎

Recall that for a family $\mathcal{W}$ of walks and a vertex $v$,
$\mathcal{W}^{\to v}$ is the set of walks in $\mathcal{W}$ ending at $v$. Say
that a walk $W=(w_{0},\dots,w_{j})$ is non-lazy if $w_{i}\neq w_{i+1}$ for all
$0\leq i<j$.

For any random $(R,G)$-alternating walk $\pi$ we define a variant
$\pi^{\theta}$ by the following holding for any $W=(w_{0},\dots,w_{2j-1})$: if
$w_{2j-1}\in S_{\theta}$ then $w_{2j}=w_{2j-1}$, and if $w_{2j-1}\notin
S_{\theta}$ then

$\pi^{\theta}(w_{2j}\mid W)=\left\\{\begin{array}[]{ll}0,&w_{2j}\in
S_{\theta},\\\ \pi(w_{2j}\mid W)+\sum_{v\in S_{\theta}}\pi(v\mid
W),&w_{2j}=w_{2j-1},\\\ \pi(w_{2j}\mid W),&w_{2j}\notin\\{w_{2j-1}\\}\cup
S_{\theta}.\end{array}\right.$ (7.10)

Then $\pi^{\theta}$ is a random $(R,G^{\theta})$-alternating walk, where
$G^{\theta}\subseteq G$ is obtained from $G$ by removing any edge incident to
$S_{\theta}$. The walk $\pi^{\theta}$ is designed to satisfy the conditions of
Lemma 7.3 as well as satisfying $\pi^{\theta}(\mathcal{W})=\pi(\mathcal{W})$
for any family $\mathcal{W}$ of walks which either (a) are non-lazy and avoid
$S_{\theta}$, or (b) have $w_{i}\notin\widehat{N}(S_{\theta})$ for odd $i$.

######  Lemma 7.4.

Suppose $R\in\mathrm{RM}$ with $\lambda(R)=\lambda$, suppose $F$ is a graph
with maximum degree $\Delta(F)\leq 2$, and suppose $\pi$ is a random
$(R,F)$-alternating walk. Suppose $\theta\leq\lambda^{-1/4}$ tends to infinity
with $n$, and let $j\geq 2-2\frac{\ln(n\|M\|)}{\ln\lambda}$ be an integer. Let
$c>0$ be constant. Suppose $\mathcal{W}$ is a set of non-lazy
$S_{\theta}(R,F)$-avoiding walks of length $2j$, such that
$\pi(\mathcal{W})\geq c$. Then there exists a constant $\rho>0$ such that
there exists a set $|U_{2j}|\geq\rho n$, such that any $u\in U_{2j}$ has
$\pi(\mathcal{W}^{\to u})\geq\rho/n$.

###### Proof.

Let $S_{\theta}=S_{\theta}(R,F)$ and consider the walk $\pi^{\theta}$ defined
above. Since $\theta\leq\lambda^{-1/4}$ and $\lambda=o(1)$, Lemma 7.3 implies
that

$\mu_{\sigma}(\pi_{2j-1}^{\theta})^{2}\leq\lambda^{j-1}\mu_{\sigma}(\pi_{1}^{\theta})^{2}+O(\lambda).$
(7.11)

We have $\pi_{1}^{\theta}(u)=\sum_{v}\pi_{0}^{\theta}(v)M(v,u)\leq\|M\|$ for
all $u$, and since $\sigma(u)\geq 1/bn$ for all $u$,

$\mu_{\sigma}(\pi_{1})^{2}\leq\sum_{u}\frac{\pi_{1}(u)^{2}}{\sigma(u)}\leq
bn^{2}\|M\|^{2}.$

So for $j\geq 2-2\ln(n\|M\|)/\ln(\lambda)$, (7.11) becomes
$\mu_{\sigma}(\pi_{2j-1}^{\theta})^{2}=O(\lambda)$. Define $T$ as the set of
vertices $u$ with $|\pi_{2j-1}^{\theta}(u)-\sigma(u)|<\lambda^{1/3}\sigma(u)$.
Then by definition of $\mu_{\sigma}$,

$\displaystyle
O(\lambda)=\mu_{\sigma}(\pi_{2j-1}^{\theta})^{2}\geq\sum_{v\notin
T}\left(\frac{\pi_{2j-1}^{\theta}(v)}{\sigma(v)}-1\right)^{2}\sigma(v)\geq\lambda^{2/3}\sigma(\overline{T}).$
(7.12)

Then $\sigma(T)=1-O(\lambda^{1/3})$. By definition of $T$,

$\displaystyle\pi_{2j-1}^{\theta}(T)$
$\displaystyle\geq(1-\lambda^{1/3})\sigma(T)=1-O(\lambda^{1/3}),$ (7.13)

and for any vertex set $A$,

$\pi_{2j-1}^{\theta}(A)\leq(1+\lambda^{1/3})\sigma(A\cap
T)+\pi_{2j-1}^{\theta}(\overline{T})\leq\sigma(A)+O(\lambda^{1/3}).$ (7.14)

Let $\mathcal{W}_{2j-1}\subseteq\mathcal{W}$ be the set of walks obtained by
removing the final vertex from walks in $\mathcal{W}$. Note that
$c\leq\pi(\mathcal{W}_{2j-1})=\pi^{\theta}(\mathcal{W}_{2j-1})$. For any $v\in
V$ let $\mathcal{W}_{2j-1}^{\to v}$ be the set of walks in
$\mathcal{W}_{2j-1}$ which end at $v$, and let $U_{2j-1}$ be the set of $v$
such that $\pi^{\theta}(\mathcal{W}_{2j-1}^{\to v})\geq c/2n$. Then

$c\leq\pi^{\theta}(\mathcal{W}_{2j-1})=\sum_{v}\pi^{\theta}(\mathcal{W}_{2j-1}^{\to
v})\\\
\leq\frac{c}{2n}|\overline{U_{2j-1}}|+\pi_{2j-1}^{\theta}(U_{2j-1})\leq\frac{c}{2}+\sigma(U_{2j-1})+O(\lambda^{1/3}).$
(7.15)

Since $\lambda=o(1)$, we conclude that $\sigma(U_{2j-1})\geq c/3$. By Lemma
3.3 we then have $|U_{2j-1}|\geq c^{\prime}n$ for some constant
$c^{\prime}>0$. Let

$U_{2j}=\left\\{v:\pi^{\theta}(\mathcal{W}^{\to
v})\geq\frac{1}{3}\frac{c}{2n}\right\\}.$

Since $\Delta_{F}\leq 2$, every $u\in U_{2j-1}$ has at least one neighbour in
$U_{2j}$, counting self-loops, and $|U_{2j}|\geq|U_{2j-1}|/3\geq
c^{\prime}n/3$. Since $\pi(\mathcal{W}^{\to v})=\pi^{\theta}(\mathcal{W}^{\to
v})$ for all $v$, this finishes the proof with
$\rho=\min\\{c^{\prime}/3,c/6\\}$. ∎

###  7.2 Hitting times for sets

For a random walk $(w_{0},w_{1},\dots)$ and $S\subseteq V$, recall that
$\tau(S)$ is the smallest $i$ for which $w_{i}\in S$.

######  Lemma 7.5.

Suppose $R\in\mathrm{RM}$ and that $G$ is light-tailed. Suppose $\pi$ is a
random $(R,G)$-alternating walk with $\pi_{0}(u)=1/|A|$ for $u\in A$, where
$A\subseteq V$ has size $|A|=\Omega(n)$.

  1. (i)

If $j\geq 0$ is constant and $|S|=o(n)$, then

$\pi(\tau(S)\leq 2j)=o(1).$

  2. (ii)

If $|S|=\Omega(n)$ then

$\pi(\tau(S)\leq 1)=\Omega(1).$

###### Proof.

We prove (i). Let $\theta=o(n/|S|)$ tend to infinity with $n$. We may assume
that $S_{\theta}\subseteq S$, since replacing $S$ by $S\cup S_{\theta}$ only
increases the probability in question. Note that since $G$ is light-tailed,

$|\widehat{N}(S)|\leq|\widehat{N}(S\setminus
S_{\theta})|+|\widehat{N}(S_{\theta})|\leq\theta|S|+o(n)=o(n).$

Note that either $\tau(S)=0$ or
$\tau(S)\geq\tau_{\mathrm{odd}}(\widehat{N}(S))$. We then have

$\pi(\tau(S)\leq
2j)\leq\pi_{0}(S)+\pi(\tau_{\mathrm{odd}}(\widehat{N}(S))<2j\mid\overline{S}).$
(7.16)

The first term equals $|S|/|A|=o(1)$.

Let $\pi^{\theta}$ be the modification of $\pi$ defined in (7.10). Note that
since $S_{\theta}\subseteq S$, any walk
$W\in\\{\tau_{\mathrm{odd}}(\widehat{N}(S))<2j\\}$ has
$\pi^{\theta}(W)=\pi(W)$. Since $\sigma(u)\geq 1/bn$ for all $u$ for some
constant $b\geq 1$,

$\displaystyle\mu_{\sigma}(\pi_{0}^{\theta})^{2}$
$\displaystyle=\left(\sum_{u\in
Z}\frac{(1/|Z|)^{2}}{\sigma(u)}\right)-1\leq\frac{bn}{|Z|}-1=O(1).$ (7.17)

By Lemma 7.3 and since $\theta\leq\lambda^{-1/4}$, for any odd $i\geq 1$ we
have
$\mu_{\sigma}(\pi_{i}^{\theta})^{2}\leq\mu_{\sigma}(\pi_{1}^{\theta})^{2}+O(\lambda)=O(\lambda)$.
As in (7.14), we have
$\pi_{i}^{\theta}(\widehat{N}(S))\leq\sigma(\widehat{N}(S))+o(1)$. Then

$\pi(\tau(S)\leq 2j)\leq
o(1)+\pi^{\theta}(\tau_{\mathrm{odd}}(\widehat{N}(S))<2j)\leq\sum_{\begin{subarray}{c}i<2j\\\
i\text{ odd}\end{subarray}}\pi_{i}^{\theta}(\widehat{N}(S))=o(1).$

Part (ii) follows from $\mu_{\sigma}(\pi_{1})^{2}=O(\lambda)$. Applying (7.14)
to the complement of $S$, we have

$\pi(\tau(S)\leq 1)\geq\pi_{1}(S)\geq\sigma(S)-o(1).$

∎

##  8 A low-degree expander

Recall that $G_{n,R}(t)$ is constructed by letting $E(u,v)$ be independent
exponential random variables with rate $R(u,v)$ for all $\\{u,v\\}$, including
any edge $\\{u,v\\}$ with $E(u,v)\leq t$ (note that $E(u,v)=E(v,u)$). Let
$D\geq k$ be an integer and define

$T_{D}(u)=\inf\\{t>0:|\\{v:E(u,v)\leq t\\}|\geq D\\}$

be the random time at which $u$ attains degree $D$. We define a graph
$H(t)\subseteq G_{n,R}(t)$ by including an edge $\\{u,v\\}$ whenever
$E(u,v)\leq t$ and $E(u,v)\leq\max\\{T_{D}(u),T_{D}(v)\\}$, and let
$H=H(\tau_{k})$.

######  Lemma 8.1.

Suppose $R\in\mathrm{RM}$ and $k\geq 1$. There exists some $D=O(1)$ such that
the following hold.

  1. (i)

Let $\theta$ tend to infinity with $n$. Letting $S_{\theta}$ denote the set of
$u$ with $d_{H}(u)\geq\theta$ or $d_{R}(u)\geq\theta d$, with high probability
$|\widehat{N}_{H}(S_{\theta})|=o(n)$.

  2. (ii)

There exists a constant $\beta=\beta(R,k)>0$ such that with high probability,
every $|A|<\beta n$ has $|N_{H}(A)|\geq k|A|$.

We prove Lemma 8.1 over the next few sections.

###  8.1 $H$ and the $D$-out graph

For all ordered pairs $(u,v)$, let $X(u,v)$ be independent exponential random
variables with rate $R(u,v)/2$. Define

$\displaystyle T_{D}^{+}(u)$ $\displaystyle=\inf\\{t>0:|\\{v:X(u,v)\leq
t\\}|\geq D\\},$ (8.1) $\displaystyle T_{D}^{-}(v)$
$\displaystyle=\inf\\{t>0:|\\{u:X(u,v)\leq t\\}|\geq D\\}.$ (8.2)

Define two undirected graphs on $V$ by

$\displaystyle H_{D}^{+}$ $\displaystyle=\\{\\{u,v\\}:X(u,v)\leq
T_{D}^{+}(u)\\},$ (8.3) $\displaystyle H_{D}^{-}$
$\displaystyle=\\{\\{u,v\\}:X(u,v)\leq T_{D}^{-}(v)\\}.$ (8.4)

Then $H_{D}^{+}$ and $H_{D}^{-}$ are equal in distribution, the common
distribution being the $R$-weighted $D$-out random graph $\mathcal{G}_{R,D}$,
defined as follows. Each $u$ independently samples $D$ vertices $N(u)$ chosen
without replacement with probability proportional to $R(u,\cdot)$. Let
$\vec{\mathcal{G}}_{R,D}$ be the graph with edges $(u,v)$ for $v\in N(u)$.
Then $\mathcal{G}_{R,D}$ is obtained by ignoring orientations and merging
parallel edges in $\vec{\mathcal{G}}_{R,D}$.

We couple $H_{D}^{+}$ and $H_{D}^{-}$ to $H$ by letting
$E(u,v)=\min\\{X(u,v),X(v,u)\\}$. Then $H\subseteq H_{D}^{+}\cup H_{D}^{-}$.
Indeed, suppose $\\{u,v\\}\in H$. If $X(u,v)\leq X(v,u)$ then

$\displaystyle X(u,v)$
$\displaystyle=E(u,v)\leq\max\\{T_{D}(u),T_{D}(v)\\}\leq\max\\{X_{D}^{+}(u),X_{D}^{-}(v)\\},$
(8.5)

so $\\{u,v\\}\in H_{D}^{+}\cup H_{D}^{-}$. The same argument with the signs
reversed holds if $X(v,u)\leq X(u,v)$.

###  8.2 Lemma 8.1 (i): degrees in $H$

We have $S_{\theta}=A_{\theta}\cup B_{\theta}$ where
$A_{\theta}=\\{v:d_{H}(v)\geq\theta\\}$ and
$B_{\theta}=\\{u:d_{R}(u)\geq\theta d\\}$, and

$\displaystyle|\widehat{N}(S_{\theta})|$
$\displaystyle\leq|\widehat{N}(B_{\theta}\setminus
A_{\theta})|+|\widehat{N}(A_{\theta})|\leq\theta|B_{\theta}|+|\widehat{N}(A_{\theta})|.$
(8.6)

Letting $c=1/20D$, we bound

$|\widehat{N}_{H}(A_{\theta})|\leq\sum_{\ell\geq\theta}(\ell+1)|\\{v:d_{H}(v)=\ell\\}|=\theta|A_{\theta}|+\sum_{\ell\geq\theta}|A_{\ell}|\\\
\leq\theta|A_{\theta}\setminus
B_{c\theta}|+\theta|B_{c\theta}|+\sum_{\ell\geq\theta}(|A_{\ell}\setminus
B_{c\ell}|+|B_{c\ell}|).$ (8.7)

We bound $|A_{\ell}\setminus B_{c\ell}|$. The discussion in Section 8.1 shows
that $H\subseteq H_{D}^{+}\cup H_{D}^{-}$ where
$H_{D}^{+}\stackrel{{\scriptstyle d}}{{=}}H_{D}^{-}\stackrel{{\scriptstyle
d}}{{=}}\mathcal{G}_{R,D}$. Letting $d(u)$ denote degrees in
$\mathcal{G}_{R,D}$,

$\displaystyle{\mbox{Pr}\left\\{d_{H}(u)\geq\ell\right\\}}\leq
2{\mbox{Pr}\left\\{d(u)\geq\ell/2\right\\}}.$ (8.8)

Let $X_{u}$ be the number of vertices $v$ with $u\in N(v)$. If
$d(u)\geq\ell/2$ then $X_{u}\geq\ell/2-D\geq\ell/4$. Vertices $v\neq u$
independently have $u\in N(v)$ with probability at most $DM(v,u)$ by Lemma
3.5. Since $M(v,u)=d_{R}(u)M(u,v)/d_{R}(v)$, and
$d_{R}(u)/d_{R}(v)\leq\ell/20D$ for $u\notin B_{c\ell}$, we have

$\mathbb{E}\left[X_{u}\right]=\sum_{v}{\mbox{Pr}\left\\{u\in
N(v)\right\\}}\leq D\sum_{v}M(v,u)\leq\frac{\ell}{20}.$

By the Chernoff bound (3.3), we have

${\mbox{Pr}\left\\{d_{H}(u)\geq\ell\right\\}}\leq
2{\mbox{Pr}\left\\{X_{u}\geq\frac{\ell}{4}\right\\}}\leq
2\left({\frac{1}{5}}\right)^{\ell/2},\quad u\notin B_{c\ell}.$ (8.9)

It follows that $\mathbb{E}|A_{\ell}\setminus B_{c\ell}|=ne^{-\Omega(\ell)}$.
Since $R\in\mathrm{RM}$, there are constants $b,b_{1}>0$ and
$\alpha\in[0,1/2)$ such that

$\frac{t|B_{t}|}{b_{1}n}\leq\sigma(B_{t})\leq
b\left({\frac{|B_{t}|}{n}}\right)^{1-2\alpha}.$ (8.10)

If $\alpha>0$ then $|B_{t}|\leq b_{2}t^{-\frac{1}{1-\alpha}}n$ for some
$b_{2}>0$. Then

$\displaystyle\mathbb{E}|\widehat{N}(S_{\theta})|$
$\displaystyle\leq\theta|B_{\theta}|+\theta|B_{c\theta}|+\theta\mathbb{E}|A_{\theta}|+\sum_{\ell\geq\theta}|B_{c\ell}|+\mathbb{E}|A_{\ell}\setminus
B_{c\ell}|$ (8.11)
$\displaystyle\leq\left(\frac{b_{2}}{\theta^{\frac{\alpha}{1-\alpha}}}+\frac{b_{2}}{(c\theta)^{\frac{\alpha}{1-\alpha}}}+\theta
e^{-\Omega(\theta)}+\sum_{\ell\geq\theta}\frac{b_{2}}{(c\ell)^{\frac{1}{1-\alpha}}}+e^{-\Omega(\ell)}\right)n.$
(8.12)

For $\theta$ tending to infinity, Markov’s inequalty shows that
$|\widehat{N}(S_{\theta})|=o(n)$ whp. If $\alpha=0$ then (8.10) gives
$|B_{t}|=0$ for any $t$ tending to infinity, and we again conclude that
$|\widehat{N}(S_{\theta})|=o(n)$ whp.

###  8.3 Lemma 8.1 (ii): expansion in $H$

Note that the distribution of $H$ is unaffected by scaling $R$, and we may
assume that $R$ is scaled so that $\gamma_{1}(R)=1$, and in particular
$1-\varepsilon\leq\tau_{k}\leq 1+\varepsilon$ whp for any
$\varepsilon\gg\frac{\ln\ln n}{\ln n}$, by Lemma 3.2. Let $\mathbb{S}$ be the
set of vertices $u$ with degree less than $D$ in $G_{n,R}(1-\varepsilon)$. For
$A\subseteq V$, let $A_{1}=A\cap\mathbb{S}$ and $A_{2}=A\setminus\mathbb{S}$,
and note that

$\displaystyle|N_{H}(A)|$ $\displaystyle=|N_{H}(A_{1})\setminus
A_{2}|+|N_{H}(A_{2})\setminus\widehat{N}_{H}(A_{1})|$ (8.13)
$\displaystyle\geq|N_{H}(A_{1})|+|N_{H}(A_{2})|-|A_{2}|-e_{H}(A_{2},\widehat{N}(\mathbb{S})),$
(8.14)

We proceed in three parts. Firstly, we show that whp no vertex in $H$ has two
neighbours in $\mathbb{S}$, and that $\mathbb{S}$ contains no edges, which
implies that $|N_{H}(A_{1})|\geq k|A_{1}|$ since $H$ has minimum degree at
least $k$. Secondly, we note that $N_{H}(A_{2})=N_{H(\infty)}(A_{2})$ since
$A_{2}\cap\mathbb{S}=\emptyset$, and show that whp
$|N_{H(\infty)}(A)|\geq\frac{D}{16}|A|$ for all $|A|\leq\beta n$, if $D$ is
large enough. Lastly, we show that whp
$e_{H}(u,\widehat{N}(\mathbb{S}))\leq\frac{D}{17}$ for all $u$, if $D$ is
large enough. We conclude that if $D$ is large enough then whp, for all
$|A|\leq\beta n$,

$|N_{H}(A)|\geq k|A_{1}|+\frac{D}{16}|A_{2}|-|A_{2}|-\frac{D}{17}|A_{2}|\geq
k|A|.$

####  8.3.1 Part 1

Let $t=1-\varepsilon$. For an edge set $F$, let
$\mathbb{S}_{F}(t)\subseteq\mathbb{S}(t)$ be the set of vertices $u$ with
degree less than $D$, not counting the edges in $F$. Letting $\mathcal{T}$
denote the event that $t\leq\tau_{k}\leq 2$, we have

$\displaystyle\\{u,v\in\mathbb{S}(t)\\}\cap\\{F\subseteq
H\\}\cap\mathcal{T}\subseteq\\{u,v\in\mathbb{S}_{F}(t)\\}\cap\\{F\subseteq
G_{n,R}(2)\\}.$ (8.15)

The two events in the right-hand side are independent, and we first use Lemma
3.1 to bound

$\displaystyle{\mbox{Pr}\left\\{e_{H}(\mathbb{S}(t))>0\right\\}}$
$\displaystyle\leq{\mbox{Pr}\left\\{\overline{\mathcal{T}}\right\\}}+\sum_{u,v}{\mbox{Pr}\left\\{u,v\in\mathbb{S}_{\\{uv\\}}(t)\right\\}}{\mbox{Pr}\left\\{E(u,v)\leq
2\right\\}}$ (8.16) $\displaystyle\leq
o(1)+2\|R\|\sum_{u,v}p_{\varepsilon}(u)p_{\varepsilon}(v),$ (8.17)

for some $p_{\varepsilon}(u)=e^{-(1-\varepsilon)d_{R}(u)+O(\ln d_{R}(u))}$.
Likewise, the probability that some $w$ has two neighbours in $\mathbb{S}$ is
bounded by

$\displaystyle 4\sum_{u,v,w}p_{\varepsilon}(u)p_{\varepsilon}(v)R(u,w)R(v,w)$
$\displaystyle\leq
4\|R\|\sum_{u,v}p_{\varepsilon}(u)p_{\varepsilon}(v)d_{R}(v)$ (8.18)
$\displaystyle\leq\|R\|\sum_{u,v}p_{\varepsilon}(u)p_{\varepsilon}(v),$ (8.19)

where $4d_{R}(v)$ is absorbed into the error term of $p_{\varepsilon}(v)$. We
bound $\sum_{u}p_{\varepsilon}(u)$. Recall that
$\gamma_{1}(R)=\sum_{u}e^{-d_{R}(u)}=1$ by choice of scaling. Let $U$ be the
set of $u$ with $d_{R}(u)\leq 2\ln n$. Then, as $p_{\varepsilon}(u)\leq
e^{-(1-2\varepsilon)d_{R}(u)}$,

$\displaystyle\sum_{u}p_{\varepsilon}(u)$ $\displaystyle\leq
e^{4\varepsilon\ln n}\sum_{u\in
U}e^{-d_{R}(u)}+|\overline{U}|e^{-(1-2\varepsilon)2\ln n}\leq
2n^{4\varepsilon}.$ (8.20)

We have $\|R\|n^{8\varepsilon}=o(1)$, and conclude that both (8.17) and (8.19)
are $o(1)$.

####  8.3.2 Part 2

Let $m\geq 1$ be some integer to be chosen. Consider the $2m$-out graph
$\mathcal{G}_{R,2m}$. Let $N(u)$ be the $2m$ vertices chosen by $u$,
independent for all $u$. Fix some set $A\subseteq V$ with $|A|=a\leq\beta n$,
let $\kappa=((m+1)a/n)^{c}$ with $c>0$ as in Lemma 3.4 (ii). Note that
$\kappa$ can be made smaller than any positive constant by letting $\beta$ be
small enough, and we choose $\beta$ sufficiently small to allow the Chernoff
bounds below.

Consider the following procedure. Initially set $B_{0}=A$. For $1\leq i\leq
3a/4$ do as follows. Let $u_{i}\in A\setminus\\{u_{1},\dots,u_{i-1}\\}$ be
such that $M(u,B_{i-1})<\kappa$. Note that this is possible for $i\leq 3a/4$
by Lemma 3.4 (ii) since $A\subseteq B_{i-1}$ and $|B_{i-1}|\leq(m+1)a$. Reveal
vertices of $N(u_{i})$ until (a) at least $m$ vertices not in $B_{i-1}$ have
been found, in which case we add those $m$ vertices to $B_{i-1}$ to form
$B_{i}$, or (b) all of $N(u_{i})$ has been revealed. Let $X_{i}=1$ if (a)
occurs and 0 otherwise.

When a vertex of $N(u_{i})$ is revealed it has probability at most $2\kappa$
of being in $B_{i}$ (with the factor 2 accounting for the choices already
made). So, conditional on the procedure so far, the probability that $X_{i}=0$
is at most

$\displaystyle{\mbox{Pr}\left\\{\text{Bin}\left(2m,2\kappa\right)\geq
m\right\\}}\leq\left({\frac{4\kappa m}{m}}\right)^{m/2},$ (8.21)

by the Chernoff bound (3.3). With $p=(4\kappa)^{m/2}$ we then have

$\displaystyle{\mbox{Pr}\left\\{|N(A)|<\frac{m}{2}|A|\right\\}}\leq{\mbox{Pr}\left\\{\sum_{i=1}^{3a/4}X_{i}<\frac{a}{2}\right\\}}\leq{\mbox{Pr}\left\\{\text{Bin}\left(\frac{3a}{4},p\right)\geq\frac{a}{4}\right\\}}.$
(8.22)

Again applying (3.3), we obtain

$\displaystyle{\mbox{Pr}\left\\{\exists|A|\leq\beta
n:|N(A)|<\frac{m}{2}|A|\right\\}}$ $\displaystyle\leq\sum_{a\leq\beta
n}\binom{n}{a}\left({\frac{3ap/4}{a/4}}\right)^{a/8}$ (8.23)
$\displaystyle\leq\sum_{a\leq\beta n}\left(\frac{ne}{a}(3p)^{1/8}\right)^{a}.$
(8.24)

We have $p^{1/8}=f(m)(a/n)^{cm/16}$ for some function $f(m)$. Choosing
$m>16/c$, and $\beta$ small enough, we conclude that this sum is $o(1)$. So
$\mathcal{G}_{R,2m}\in\mathcal{E}_{m/2}$ whp, where

$\mathcal{E}_{m/2}=\left\\{|N(A)|\geq\frac{m}{2}|A|\text{ for all
$|A|\leq\beta n$}\right\\}.$

Let $D=4m$. Condition on the whp events $H_{D/2}^{+}\in\mathcal{M}_{m/2}$ and
$H_{D/2}^{-}\in\mathcal{M}_{m/2}$, and let $|A|\leq\beta n$. Note that for
each $u$, $N_{H(\infty)}(u)$ contains at least one of $N^{+}(u)$ and
$N^{-}(u)$. Let $A^{+}$ be the set of $u$ with $N^{+}(u)\subseteq
N_{H(\infty)}(u)$, and suppose without loss of generality that
$|A^{+}|\geq|A|/2$. Then

$\displaystyle|N_{H(\infty)}(A)|$
$\displaystyle\geq|N^{+}(A^{+})|\geq\frac{m}{2}|A^{+}|\geq\frac{D}{16}|A|.$
(8.25)

For $D$ large enough, we conclude that $H(\infty)\in\mathcal{E}_{D/16}$ whp.

####  8.3.3 Part 3

Let $t=1+\varepsilon$. Fix $u\in V$ and let
$\mathbb{S}_{u}\supseteq\mathbb{S}$ be the set of vertices $v$ with degree
less than $D$ in $G_{n,R}(t)$, not counting edges incident to $u$. Let
$X(u)=|N_{t}(u)\cap\widehat{N}_{t}(\mathbb{S}_{u})|$. If $\tau_{k}\leq t$ we
then have $e_{H}(u,\widehat{N}_{H}(\mathbb{S}))\leq X(u)$ since $H\subseteq
G_{n,R}(t)$. Note that $N_{t}(u)$ and $\widehat{N}_{t}(\mathbb{S}_{u})$ are
independent. Conditional on $E(v,w)$ for all $v,w\neq u$, the expected value
of $X(u)$ is

$tR(u,\widehat{N}_{t}(\mathbb{S}_{u}))\leq 2\|R\||N_{t}(\mathbb{S}_{u})|\leq
2D\|R\||\mathbb{S}_{u}|.$

Let $\phi$ be such that $\|R\|^{\phi/2}\leq n^{-2}$. The Chernoff bound (3.3)
then gives

$\displaystyle{\mbox{Pr}\left\\{X(u)\geq\phi\ \middle|\
|\mathbb{S}_{u}|=n^{o(1)}\right\\}}$
$\displaystyle\leq\left({\frac{\mathbb{E}\left[X\right]}{\phi}}\right)^{\phi/2}$
(8.26)
$\displaystyle=O\left((\|R\||N_{t}(\mathbb{S}_{u})|)^{\phi/2}\right)=o(n^{-1}).$
(8.27)

Since $\tau_{k}\leq 1+\varepsilon$ whp by Lemma 3.2, we conclude that
$e_{H}(u,\widehat{N}_{H}(\mathbb{S}))<\phi$ for all $u$ whp.

##  9 Proofs for Section 3

###  9.1 Degrees

###### Proof of Lemma 3.1.

Suppose $X=X_{1}+\dots+X_{n}$ where the $X_{i}$ are independent indicator
random variables with $\mathbb{E}\left[X_{i}\right]=1-e^{-\mu_{i}}$ and
$\mu=\mu_{1}+\dots+\mu_{n}$, where $\mu_{i}/\mu\leq\varepsilon=o(1)$ for all
$i$, and $\mu$ tends to infinity with $n$. It is not hard to show that

$\displaystyle{\mbox{Pr}\left\\{X\leq\ell\right\\}}$
$\displaystyle=\frac{e^{-\mu}\mu^{\ell}}{\ell!}\left(1+O\left({\frac{\varepsilon}{\mu}}\right)\right),$
(9.1)

Define $\mathrm{Po}(\mu,\ell)=e^{-\mu}\mu^{\ell}/\ell!$.

Let $R\in\mathrm{RM}(1)$ and let $t=\Omega(1)$. For any vertex $u$ and any set
$S\subseteq V$ with $|V\setminus S|=O(1)$, $e_{t}(u,S)$ satisfies the above
with

$\mathbb{E}\left[e_{t}(u,S)\right]=tR(u,S)=td_{R}(u)-o(1).$

With $d_{R}(u)\geq d$ tending to infinity we then have

$\displaystyle{\mbox{Pr}\left\\{e_{t}(u,S)\leq\ell\right\\}}=(1+o(1))\mathrm{Po}(td_{R}(u),\ell)=e^{-td_{R}(u)+O(\ln
d_{R}(u))}.$ (9.2)

∎

###### Proof of Lemma 3.2.

Let $P\in\mathrm{RM}$ be a matrix with
$\gamma_{k}(P)\to\gamma_{k}\in(0,\infty)$. Note that $d=\min
d_{P}(u)=\Theta(\ln n)$ tends to infinity with $n$. Let $U$ be a set of $\ell$
distinct vertices, let $k>0$, and let $0<k_{u}\leq k$ for each $u\in U$, with
$\sum_{u\in U}(k-k_{u})=2m$ for some $m\geq 0$. Consider the graph $G_{n,P}$.
By (9.1),

$\displaystyle{\mbox{Pr}\left\\{e(u,\overline{U})<k_{u},\text{ all $u\in
U$}\right\\}}$ $\displaystyle=\prod_{u\in
U}{\mbox{Pr}\left\\{e(u,\overline{U})<k_{u}\right\\}}$ (9.3)
$\displaystyle=(1+o(1))\prod_{u\in U}\mathrm{Po}(d_{P}(u),k_{u}-1)$ (9.4)
$\displaystyle\leq\frac{1+o(1)}{d^{2m}}\prod_{u\in
U}\mathrm{Po}(d_{P}(u),k-1).$ (9.5)

Let $\mathcal{E}_{m}$ be the event that $U$ contains exactly $m$ edges. Then
$\mathcal{E}_{m}$ is independent of $\\{e(u,\overline{U}):u\in U\\}$, and
${\mbox{Pr}\left\\{\mathcal{E}_{m}\right\\}}=O(\|P\|^{m})$ and
${\mbox{Pr}\left\\{\mathcal{E}_{0}\right\\}}=1-o(1)$. For $k>0$ we then have,
using both (9.4) and (9.5),

$\displaystyle{\mbox{Pr}\left\\{d(u)<k\ \forall u\in U\right\\}}$
$\displaystyle=\sum_{m}{\mbox{Pr}\left\\{\mathcal{E}_{m}\right\\}}\sum_{\sum
k_{u}=k\ell-2m}{\mbox{Pr}\left\\{e(u,\overline{U})<k_{u}\forall u\in
U\right\\}}$ (9.6) $\displaystyle\leq\left(\prod_{u\in
U}\mathrm{Po}(d_{P}(u),k-1)\right)\left({\mbox{Pr}\left\\{\mathcal{E}_{0}\right\\}}+\sum_{m>0}O\left({\frac{\|P\|^{m}}{d^{2m}}}\right)\right)$
(9.7) $\displaystyle=(1+o(1))\prod_{u\in U}\mathrm{Po}(d_{P}(u),k-1).$ (9.8)

Letting $X_{k}$ denote the number of vertices in $G_{n,P}$ with $d(u)<k$,

$\displaystyle\mathbb{E}\left[\binom{X_{k}}{\ell}\right]$
$\displaystyle=\sum_{|U|=\ell}{\mbox{Pr}\left\\{d(u)<k,\text{ all $u\in
U$}\right\\}}$ (9.9) $\displaystyle=\sum_{|U|=\ell}(1+o(1))\prod_{u\in
U}\mathrm{Po}(d_{P}(u),k-1)=(1+o(1))\frac{\gamma_{k}(P)^{\ell}}{\ell!}.$
(9.10)

If $\gamma_{k}(P)$ converges to some $\gamma_{k}<\infty$, the method of
moments (see e.g. [7]) implies that $X_{k}$ converges to a Poisson random
variable with expected value $\gamma_{k}$, and

$\lim_{n\to\infty}{\mbox{Pr}\left\\{\delta(G_{n,P})\geq
k\right\\}}=\lim_{n\to\infty}{\mbox{Pr}\left\\{X_{k}=0\right\\}}=e^{-\gamma_{k}}.$

If $\gamma_{k}(P)$ diverges to infinity, we note that
$\text{Var}\left(X_{k}\right)=o(\mathbb{E}\left[X_{k}\right])$, and
Chebyshev’s inequality implies that ${\mbox{Pr}\left\\{X_{k}>0\right\\}}\to
1$.

To obtain a bound for $\tau_{k}$, let $\varepsilon\gg\frac{\ln\ln n}{\ln n}$
and suppose $\gamma_{1}(R)=1$. Note that
$G_{n,R}(1+\varepsilon)\stackrel{{\scriptstyle d}}{{=}}G_{n,P}$ with
$P(u,v)=1-e^{-(1+\varepsilon)R(u,v)}$. This matrix has $d_{P}(u)+O(\ln
d_{P}(u))\geq(1+\varepsilon/2)d_{R}(u)$ for all $u$, where we use the fact
that $\|R\|=o(\varepsilon)$. We have

$\displaystyle\gamma_{k}(P)=\sum_{u}e^{-d_{P}(u)}d_{P}(u)^{k-1}$
$\displaystyle\leq\sum_{u}e^{-(1+\varepsilon/2)d_{R}(u)}$ (9.11)
$\displaystyle\leq e^{-\varepsilon d/2}\gamma_{1}(R)=o(1).$ (9.12)

We conclude that $\delta(G_{n,R}(1+\varepsilon))\geq k$ whp. By the same
token, $\delta(G_{n,R}(1-\varepsilon))<k$ whp.

∎

###  9.2 A matrix lemma

###### Proof of Lemma 3.7.

If $\ell=1$, take $S=I$ and $T=J$. We prove the case $\ell>1$ by induction. By
rescaling, we may assume that $\pi_{I}(I)=1$ and $\pi_{J}(J)=1$.

For each $j\in J$ let $I_{\ell}(j)$ be the set of $i\in I$ with
$\tau(i,j)=a_{\ell}$. Let

$J^{\prime}=\left\\{j\in J:\pi_{I}(I_{\ell}(j))<\frac{1}{\ell}\right\\}.$

If $\pi_{J}(J^{\prime})<1-\ell^{-1}$, let $S=\cap_{j\notin
J^{\prime}}I_{\ell}(j)$ and $T=J\setminus J^{\prime}$. Then $\tau=a_{\ell}$ on
$S\times T$ and $\pi_{I}(S)\geq\ell^{-1}$, $\pi_{J}(T)\geq\ell^{-1}$.

If $\pi_{J}(J^{\prime})\geq 1-\ell^{-1}$, let $I^{\prime}=\cap_{j\in
J^{\prime}}(I\setminus I_{\ell}(j))$ and consider the matrix

$\tau^{\prime}(i,j)=\tau(i,j),\quad i\in I^{\prime},j\in J^{\prime}.$

This takes values $\\{a_{1},\dots,a_{\ell-1}\\}$, and by induction there exist
$S\subseteq I^{\prime},T\subseteq J^{\prime}$ with
$\pi_{I}(S)\geq(\ell-1)^{-1}\pi_{I}(I^{\prime})$ and
$\pi_{J}(T)\geq(\ell-1)^{-1}\pi_{J}(J^{\prime})$ such that $\tau^{\prime}$,
and therefore $\tau$, is constant on $S\times T$. We have

$\pi_{I}(I^{\prime})\geq\min_{j\in J^{\prime}}\pi_{I}(I\setminus
I_{\ell}(j))\geq 1-\ell^{-1},\quad\pi_{J}(J^{\prime})\geq 1-\ell^{-1},$

so

$\displaystyle\pi_{I}(S)$
$\displaystyle\geq(\ell-1)^{-1}\pi_{I}^{j}(I^{\prime})\geq\ell^{-1},$ (9.13)
$\displaystyle\pi_{J}(T)$
$\displaystyle\geq(\ell-1)^{-1}\pi_{J}(J^{\prime})\geq\ell^{-1}.$ (9.14)

∎

###  9.3 Mixing in simple random walks

###### Proof of Lemma 3.8.

This proof is more or less taken from [16], with slight modifications. We
first note that for $R\in\mathrm{RM}$, the transition matrix $M$ is
reversible:

$\sigma(u)M(u,v)=\frac{d_{R}(u)}{d_{R}(V)}\frac{R(u,v)}{d_{R}(u)}=\frac{d_{R}(v)}{d_{R}(V)}\frac{R(v,u)}{d_{R}(v)}=\sigma(v)M(v,u).$

For vectors $f,g:V\to\mathbb{R}$ we define an inner product

$\langle f,g\rangle_{\sigma}=\sum_{v}f(v)g(v)\sigma(v),$ (9.15)

and the associated norm $\|f\|_{\sigma}=\langle f,f\rangle_{\sigma}^{1/2}$.
Then for probability measures $\pi$,

$\left\|\frac{\pi(\cdot)}{\sigma(\cdot)}-\mathbf{1}\right\|_{\sigma}=\sqrt{\left(\sum_{v}\frac{\pi(v)^{2}}{\sigma(v)}\right)-1}=\mu_{\sigma}(\pi),$
(9.16)

where $\mathbf{1}=(1,1,\dots,1)$.

Let $1=\lambda_{1}\geq\lambda_{2}\geq\dots\geq\lambda_{n}\geq-1$ be the
eigenvalues of $M$ , with a corresponding eigenbasis
$\mathbf{1}=f_{1},\dots,f_{n}$, orthonormal with respect to the
$\langle\cdot,\cdot\rangle_{\sigma}$ inner product. Then (see e.g. [16])

$\displaystyle\frac{\pi M(v)}{\sigma(v)}-1$
$\displaystyle=\sum_{j=2}^{n}\sum_{u}\pi(u)f_{j}(u)f_{j}(v)\lambda_{j}$ (9.17)
$\displaystyle=\sum_{j=2}^{n}\lambda_{j}f_{j}(v)\sum_{u}\left[\left(\frac{\pi(u)}{\sigma(u)}-1\right)f_{j}(u)\sigma(u)+f_{j}(u)\sigma(u)\right]$
(9.18)
$\displaystyle=\sum_{j=2}^{n}\lambda_{j}f_{j}(v)\left[\left\langle\frac{\pi}{\sigma}-\mathbf{1},f_{j}\right\rangle_{\sigma}+\langle
f_{j},\mathbf{1}\rangle_{\sigma}\right].$ (9.19)

For any $j>1$, orthonormality implies $\langle
f_{j},\mathbf{1}\rangle_{\sigma}=0$. Let
$F(j)=\langle\pi/\sigma-\mathbf{1},f_{j}\rangle_{\sigma}$, and note that
$\mu_{\sigma}(\pi)^{2}=\sum_{j=1}^{n}F(j)^{2}$. Then

$\displaystyle\mu_{\sigma}(\pi M)^{2}$
$\displaystyle=\sum_{v}\sigma(v)\left(\sum_{j=2}^{n}\lambda_{j}f_{j}(v)F(j)\right)^{2}$
(9.20) $\displaystyle=\sum_{j\geq
2}\lambda_{j}^{2}F(j)^{2}\|f_{j}\|_{\sigma}^{2}+2\sum_{k>j\geq
2}\lambda_{j}\lambda_{k}F(j)F(k)\langle f_{j},f_{k}\rangle_{\sigma}$ (9.21)

Since the $f_{j}$ are orthonormal in the $\langle\cdot,\cdot\rangle_{\sigma}$
inner product, we are left with

$\displaystyle\mu_{\sigma}(\pi M)^{2}$ $\displaystyle=\sum_{j\geq
2}\lambda_{j}^{2}F(j)^{2}\leq\lambda^{2}\sum_{j=1}^{n}F(j)^{2}=\lambda^{2}\mu_{\sigma}(\pi)^{2}.$
(9.22)

∎

###  9.4 The expander mixing lemma

###### Proof of Lemma 3.4.

For $A\subseteq V$ let $\mathbf{1}_{A}:V\to\\{0,1\\}$ be the indicator for
$A$. Let $\pi(u)=\mathbf{1}_{A}/|A|$. One easily checks that

$\displaystyle\frac{1}{|A|}M(A,B)-\sigma(B)=\left\langle\frac{\pi
M(\cdot)}{\sigma(\cdot)}-\mathbf{1}_{V},\mathbf{1}_{B}\right\rangle_{\sigma}.$
(9.23)

Cauchy-Schwarz’ inequality and Lemma 3.8 then give

$\displaystyle\left|\frac{1}{|A|}M(A,B)-\sigma(B)\right|^{2}\leq\left\|\frac{\pi
M}{\sigma}-\mathbf{1}_{V}\right\|_{\sigma}^{2}\|\mathbf{1}_{B}\|_{\sigma}^{2}\leq\lambda\mu_{\sigma}(\pi)^{2}\sigma(B).$
(9.24)

Since $\mu_{\sigma}(\pi)^{2}\leq\sum_{u\in A}\pi(u)^{2}/\sigma(u)\leq bn/|A|$,
(3.1) follows.

To see how (i) follows, note that $R(u,v)\geq dM(u,v)$ for all $u,v$. Lemma
3.3 gives $\sigma(B)=\Omega(1)$ whenever $|B|=\Omega(n)$. Since
$\lambda(R)=o(1)$, for $|A|,|B|=\Omega(n)$ we then have

$R(A,B)\geq dM(A,B)\geq
d(|A|\sigma(B)-O(\lambda\sqrt{n|A|\sigma(B)})=\Omega(dn).$

For (ii), let $c>0$ be some constant to be chosen, and for each $|A|\leq n/2$
define $A^{\prime}$ as the set of $u\in A$ with $M(u,A)\geq(|A|/n)^{c}$. If
$|A|<(n^{c}\|M\|)^{-1/(1-c)}$ then any $u\in A$ has

$M(u,A)\leq\|M\||A|<\left({\frac{|A|}{n}}\right)^{c},$

so $A^{\prime}=\emptyset$. Suppose $(n^{c}\|M\|)^{-1/(1-c)}\leq|A|\leq n/2$.
Then (3.1) and the power law condition (1.2) give, for some constant
$0\leq\alpha<1/2$,

$\left({\frac{|A|}{n}}\right)^{c}\leq\frac{1}{|A^{\prime}|}M(A^{\prime},A)\leq\sigma(A)+\lambda\sqrt{\frac{bn\sigma(A)}{|A^{\prime}|}}\\\
\leq\left[\left({\frac{|A|}{n}}\right)^{1-2\alpha-2c}+\lambda\sqrt{\frac{b|A|}{|A^{\prime}|}}\left({\frac{n}{|A|}}\right)^{\alpha+2c}\right]\left({\frac{|A|}{n}}\right)^{2c}.$
(9.25)

For $2c<1-2\alpha$, the first term in square brackets is at most 1. Since
$\lambda\leq(n\|M\|)^{-\alpha-\gamma}$ for some constant $\gamma>0$, we have
for $|A|\geq(n^{c}\|M\|)^{-1/(1-c)}$ that

$\displaystyle\left({\frac{n}{|A|}}\right)^{\alpha+2c}$
$\displaystyle\leq\left({\frac{n}{n^{-\frac{c}{1-c}}\|M\|^{-\frac{1}{1-c}}}}\right)^{\alpha+2c}=(n\|M\|)^{\frac{\alpha+2c}{1-c}}.$
(9.26)

We have $n\|M\|\geq 1$ since $M$ is a transition matrix. Since $\lambda=o(1)$
and $\lambda\leq(n\|M\|)^{-\alpha-\gamma}$ for some constant $\gamma>0$, we
conclude that for $c>0$ small enough, $\lambda(n/|A|)^{\alpha+2c}=o(1)$. From
(9.25) we then have, for $|A|\leq n/2$,

$\displaystyle 1<2^{c}\leq\left({\frac{n}{|A|}}\right)^{c}\leq
1+o\left(\sqrt{\frac{b|A|}{|A^{\prime}|}}\right).$ (9.27)

We conclude that $|A^{\prime}|=o(|A|)$. ∎

## References

  * [1] M. Ajtai, J. Komlós, and E. Szemerédi.  First occurrence of Hamilton cycles in random graphs.  Annals of Discrete Mathematics, 115:173–178, 1985.
  * [2] N. Alon and F.R.K. Chung.  Explicit construction of linear sized tolerant networks.  Discrete Mathematics, 72(1):15 – 19, 1988.
  * [3] Yahav Alon and Michael Krivelevich.  Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs.  ArXiv e-prints, 2020.
  * [4] Michael Anastos, Alan Frieze, and Pu Gao.  Hamiltonicity of random graphs in the stochastic block model.  ArXiv e-prints, 2019.
  * [5] B. Bollobás.  The evolution of random graphs.  Transactions of the American Mathematical Society, 286(1):257–274, 1984.
  * [6] B. Bollobás and A. M. Frieze.  On matchings and Hamiltonian cycles in random graphs.  Annals of Discrete Mathematics, 28:23–46, 1985.
  * [7] Rick Durrett.  Probability: Theory and Examples.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 4 edition, 2010.
  * [8] P. Erdős and A Rényi.  On the evolution of random graphs.  Publ. Math. Inst. Hungar. Acad. Sci., 5:17–61, 1960.
  * [9] A. M. Frieze.  Limit distribution for the existence of Hamiltonian cycles in random bipartite graphs.  Europ. J. Combinatorics, 6:327–334, 1985.
  * [10] A. M. Frieze.  Hamilton cycles in random graphs: a bibliography.  ArXiv e-prints, 1901.07139 [v13], July 2019.
  * [11] A. M. Frieze and T. Johansson.  On random $k$-out subgraphs of large graphs.  Random Structures & Algorithms, 50(2):143–157, 2017.
  * [12] A. M. Frieze and M. Karoński.  Introduction to Random Graphs.  Cambridge University Press, Cambridge, UK, 2015.
  * [13] Alan Frieze and Michael Krivelevich.  Hamilton cycles in random subgraphs of pseudo-random graphs.  Discrete Mathematics, 256:137–150, September 2002.
  * [14] T. Johansson.  On Hamilton cycles in Erdős-Rényi subgraphs of large graphs.  Random Structures & Algorithms, 57:132–149, 2020.
  * [15] J. Komlós and E. Szemerédi.  Limit distribution for the existence of Hamiltonian cycles in a random graph.  Discrete Mathematics, 43(1):55–63, 1983.
  * [16] David A Levin and Yuval Peres.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * [17] Richard Montgomery.  Hamiltonicity in random graphs is born resilient.  Journal of Combinatorial Theory, Series B, 139:316 – 341, 2019\.
  * [18] A. Nilli.  On the second eigenvalue of a graph.  Discrete Mathematics, 91(2):207 – 210, 1991.