3.1.1. The construction of approximating weight sequences

Let $(\textbf{w}(n))_{n \ge 1}$ be regular and consider the limiting distribution function F. For $\gamma \in (0,1)$ , recall that $F(C_{\gamma}) \geq 1 - \gamma$ . Recall also that from Definition 1 there is a positive real number $x_0$ such that $F(x) = 0$ for $x < x_0$ .

We define a set of intervals $\mathcal{P}_\ell$ whose union is a superset of $[x_0,C_\gamma)$ as follows. Let $\varepsilon_\ell = 1/\ell$ . First, for $i\geq 0$ , we set

$$x_{i+1} = \sup \{x \in (x_i,C_\gamma) \,:\, F(x) - F(x_i) < \varepsilon_\ell \}.$$

Set $t_\ell = \min \{ i \,:\, x_i = C_\gamma \}$ and $x_{-1}=0$ . For each $i=0,\ldots, {t_\ell}$ , let $y_{2i}, y_{2i+1}$ be such that

1. (1) $\max \big\{ \frac{1}{2} (x_{i-1}+x_i), x_i -\varepsilon_\ell \big\} < y_{2i} < x_i$ ;

2. (2) $x_i < y_{2i+1} < \min \big\{ \frac{1}{2}(x_i +x_{i+1}), x_i+ \varepsilon_\ell \big\}$ or $y_{2i+1}= C_\gamma$ , if $i=t_\ell$ ;

3. (3) $y_{2i}, y_{2i+1}$ are points of continuity of F.

Now, we set $\mathcal{P}_\ell \,:\!=\, \{ [y_0 ,y_1), \ldots, [y_{2 t_\ell}, C_\gamma) \}$ . With $p_\ell = 2 t_\ell+1$ , for $i=1,\ldots, p_\ell$ , we set $I_i = [y_{i-1}, y_{i} )$ .

Given this partition and the weight sequence $\textbf{w} (n)$ , for each $n \geq 1$ we define two finitary weight sequences $\textbf{W}^{(\ell, \gamma)+} ({n^{\prime}})$ and $\textbf{W}^{(\ell,\gamma)-} ({n^{\prime\prime}})$ on the sets [n ^′] and [n ^′′], respectively, as follows. The partition $\mathcal{P}_\ell$ gives rise to a partition of $[n] \setminus \mathsf{C}_{\gamma}$ , where for each $i =1,\ldots, p_\ell$ we have $\mathsf{C}_i = \{j \,:\, w_j(n) \in I_i \}$ . We denote this partition by $\mathcal{P}_{n,\ell,\gamma}$ , and we let this be the associated partition of $\textbf{W}^{(\ell,\gamma)+} (n)$ and $\textbf{W}^{(\ell, \gamma)-} (n)$ .

In particular, consider the random subset of $\mathsf{C}_\gamma$ in which every element of $\mathsf{C}_\gamma$ is included independently with probability p. An application of the Chernoff bounds implies that w.h.p. this has size at least $\lfloor p|\mathsf{C}_\gamma| - n^{2/3} \rfloor\,=\!:\,k_-$ . Consider a set of vertices $\mathsf{C}_\gamma^-=\{ v_1,\ldots, v_{k_-} \}$ which is disjoint from [n]. We identify with [n ^′′] the set $\left( \cup_{i=1}^{p_\ell} \mathsf{C}_i \right) \bigcup \mathsf{C}_\gamma^-$ , through a bijective mapping $\varphi^- \,:\, \left( \cup_{i=1}^{p_\ell} \mathsf{C}_i \right) \bigcup \mathsf{C}_\gamma^- \to [n^{\prime\prime}]$ . It follows that $n^{\prime\prime} = (1-{h_F(\gamma)} + p{h_F(\gamma)})n (1+o(1))$ .

For any vertex $j \in \mathsf{C}_\gamma$ such that $w_j(n) \geq 2 C_\gamma$ , we consider $c_j\,:\!=\,2 \big\lfloor \frac{w_j(n)}{C_\gamma}\big\rfloor$ copies of this vertex each having weight $2C_\gamma$ , which we label as $v_{j1},\ldots, v_{jc_j}$ . For each such j we let

$$\varepsilon_j(n)= \frac{w_j(n)}{C_\gamma} - \Big\lfloor \frac{w_j (n)}{C_\gamma} \Big\rfloor,$$

and we set

$$R = \Big\lceil 2 \sum_{j \,:\, w_j(n) \geq 2 C_\gamma} \varepsilon_j (n) \Big\rceil.$$

If $j \in \mathsf{C}_\gamma$ is such that $C_\gamma \leq w_j(n) < 2 C_\gamma$ , then we introduce a single copy $v_{j1}$ having weight equal to $w_j$ (in other words $c_j=1$ ).

We let $\mathsf{C}_\gamma^+$ be the set that is the union of these copies together with a set of R vertices which we denote by $\mathcal{R}$ (disjoint from the aforementioned sets) each having weight $2 C_\gamma$ :

$$ \mathsf{C}_\gamma^+ \,:\!=\, \mathcal{R} \cup \bigcup_{j \in \mathsf{C}_\gamma} \big\{v_{j1},\ldots, v_{jc_j} \big\}. $$

Let $n^{\prime} = \left| \left( \cup_{i=1}^{p_\ell} \mathsf{C}_i \right) \bigcup \mathsf{C}_\gamma^+ \right|$ , and identify the set [n ^′] with the vertices in $\left( \cup_{i=1}^{p_\ell} \mathsf{C}_i \right) \bigcup \mathsf{C}_\gamma^+$ , through a bijection $\varphi^+ \,:\, \left( \cup_{i=1}^{p_\ell} \mathsf{C}_i \right) \bigcup \mathsf{C}_\gamma^+ \to[n^{\prime}]$ . We will use the symbol $\mathsf{C}_\gamma^+$ to denote the set $[n^{\prime}] \setminus\varphi^+\left( \left( \cup_{i=1}^{p_\ell} \mathsf{C}_i \right) \right)$ . In other words, the set $\mathsf{C}_\gamma^+$ consists of the replicas of the vertices in $\mathsf{C}_\gamma$ , as these were defined above, together with the set of vertices corresponding to $\mathcal{R}$ . This completes the definition of $\textbf{W}^{(\ell, \gamma)+} (n)$ .

For each $i = 1,\ldots, p_\ell$ , we set $W_i^- = y_{2(i-1)}$ and $W_i^+ = y_{2i-1}$ ; for each $j \in \mathsf{C}_i$ , we set

$$W_{{\varphi^-(j)}}^{(\ell, \gamma)-} (n) \,:\!=\, W_i^- \quad \mbox{and} \quad W_{{\varphi^+(j)}}^{(\ell, \gamma)+} (n) \,:\!=\, W_i^+.$$

For any $j \in [n^{\prime\prime}] \setminus \varphi^- \left(\cup_{i=1}^{p_\ell} \mathsf{C}_i\right)$ we set $W_j^{(\ell, \gamma)-} (n) \,:\!=\, C_\gamma$ . Note that

$$\lim_{n \rightarrow \infty} \frac{|\mathsf{C}_\gamma^-|}{n} = p h_F(\gamma),$$

and if $W_{\mathsf{C}_\gamma^-} \big(\textbf{W}^{(\ell,\gamma)-}\big)$ denotes the total weight of these vertices, then this satisfies

$$\lim_{n \rightarrow \infty} \frac{W_{\mathsf{C}_\gamma^-} \big(\textbf{W}^{(\ell,\gamma)-}\big)}{n} = ph_F(\gamma) C_\gamma \,=\!:\,W_\gamma^-< W_\gamma < 4W_\gamma.$$

Furthermore,

\begin{equation*}\begin{split}|\mathsf{C}_\gamma^+| &=\sum_{j \,:\, C_\gamma \leq w_j < 2C_\gamma} 1 + \sum_{j \,:\, w_j \geq 2C_\gamma }2 \lfloor \frac{w_j}{C_\gamma} \rfloor + R \\&= \sum_{j \,:\, C_\gamma \leq w_j < 2C_\gamma} 1 + 2 \sum_{j \,:\, w_j \geq 2C_\gamma } \frac{w_j}{C_\gamma} + e(n),\end{split}\end{equation*}

with $0\leq e(n) < 1$ . By the weak convergence of $F_n$ to F and since $\mathbb{E} \left[W_n\right] \to \mathbb{E} \left[W_F\right] < \infty$ , it follows that

(6) \begin{equation} \lim_{n \to \infty} \frac{|\mathsf{C}_\gamma^+|}{n} = \mathbb{P}\left[C_\gamma \leq W_F \leq 2C_\gamma\right] + 2 \frac{\mathbb{E} \left[\textbf{1}_{\{ W_F \geq 2C_\gamma \}}W_F\right]}{C_\gamma}\,=\!:\,\gamma^+,\end{equation}

where $\gamma^+ \downarrow 0$ as $\gamma \downarrow 0$ . So $n^{\prime}/n \to 1- h_{F}(\gamma) + \gamma^+$ as $n\to \infty$ . Moreover,

(7) \begin{equation} \lim_{\gamma \downarrow 0} \gamma^+ C_\gamma = \lim_{\gamma \downarrow 0}\big(C_\gamma \mathbb{P}\left[C_\gamma \leq W_F \leq 2C_\gamma\right] + 2 \mathbb{E} \left[\textbf{1}_{\{ W_F \geq 2C_\gamma \}}W_F\right]\big)\stackrel{5}{=} 0.\end{equation}

Also, the total weight of the vertices in $\mathsf{C}_\gamma^+$ can be bounded as follows:

\begin{equation*} \begin{split} W_{\mathsf{C}_\gamma^+} \big(\textbf{W}^{(\ell,\gamma)+}\big) &= \sum_{j \,:\, C_\gamma \leq w_j < 2C_\gamma} w_j + \sum_{j \,:\, w_j \geq 2C_\gamma } 2 \big\lfloor \frac{w_j}{C_\gamma} \big\rfloor (2 C_\gamma) \\ &\leq {\sum_{j \,:\, C_\gamma \leq w_j < 2C_\gamma} w_j}+ 4 \sum_{j \,:\, w_j \geq 2C_\gamma } w_j. \end{split} \end{equation*}

Hence, as $n \rightarrow \infty$ ,

(8) \begin{equation} \begin{split}\frac{W_{\mathsf{C}_\gamma^+} \big(\textbf{W}^{(\ell,\gamma)+}\big)}{n} \rightarrow& \mathbb{E} \left[\textbf{1}_{\big\{ C_\gamma \leq W_F < 2C_\gamma \big\}}W_F\right] + 4 \mathbb{E} \left[\textbf{1}_{ \{ W_F \geq 2C_\gamma \} }W_F\right]\,=\!:\,W_\gamma^+ {\leq} 4 W_\gamma.\end{split}\end{equation}

We denote by $U_{n}^{(\ell,\gamma)+}$ and $U_{n}^{(\ell, \gamma)-}$ the weight in $\textbf{W}^{(\ell,\gamma)+} (n^{\prime})$ and $\textbf{W}^{(\ell, \gamma)-} (n^{\prime\prime})$ of a uniformly chosen vertex from [n ^′] and [n ^′′], respectively. Also, we let $F_n^{(\ell, \gamma)-}, F_{n}^{(\ell, \gamma)+}$ denote their distribution functions. Note that both $F_n^{(\ell, \gamma)-}$ and $F_{n}^{(\ell, \gamma)+}$ converge pointwise, as $n\rightarrow \infty$ , to the functions $F^{(\ell, \gamma)-}$ and $F^{(\ell, \gamma)+}$ , respectively, where

• for each $i = 0,\ldots, p_\ell$ and for each $x \in I_i$ we set

  $$F^{(\ell, \gamma)-} (x) \,:\!=\, \frac{{F(W_i^+)}}{1-{h_F(\gamma)} + p {h_F(\gamma)}} \quad \mbox{and} \quad F^{(\ell, \gamma)+} (x) = \frac{{F(W_i^-)}}{1- {h_F(\gamma)} + \gamma^+}; $$

• for any $x\geq C_\gamma$ we have $F^{(\ell,\gamma)-}(x) = 1$ , and for any $x< y_0$ we have $F^{(\ell,\gamma)-}(x)=0$ , $F^{(\ell,\gamma)+}(x) =0$ ;

• for any $C_\gamma \leq x < 2C_\gamma$ we have

  (9) \begin{equation} F^{(\ell,\gamma)+}(x) = \frac{F( x )}{1-{h_F(\gamma)} + \gamma^+},\end{equation}
  whereas for $x\geq 2 C_\gamma$ we have $F^{(\ell,\gamma)+}(x) = 1$ .

We will now prove that both families

$$\big\{\textbf{W}^{(\ell,\gamma)+} ({n^{\prime}})\big\}_{\gamma\in (0,1), \ell \in \mathbb{N}} \quad\text{and} \quad\big\{ \textbf{W}^{(\ell, \gamma)-} ({n^{\prime\prime}}) \big\}_{\gamma\in (0,1), \ell \in \mathbb{N}}$$

are F-convergent. Thus, we will verify that they satisfy both parts of Definition 4.

Part 1 of Definition 4. It will be convenient to define a probability distribution function which will be the pointwise limit of $F^{(\ell,\gamma)+}$ and $F^{(\ell,\gamma)-}$ as $\ell \to \infty$ . For any $x\in [0,C_\gamma)$ we set

$$F^{(\gamma)+} (x) =\frac{F( x )}{1-{h_F(\gamma)} + \gamma^+} $$

and

$$F^{(\gamma)-}(x) =\frac{F(x)}{1-{h_F(\gamma)} + p h_F(\gamma)},$$

whereas $F^{(\gamma)+} (x) = F^{(\gamma)-} (x) = 0$ for $x<0$ , and $F^{(\gamma)+} (x) = F^{(\gamma)-} (x) = 1$ for $x \geq C_\gamma$ . Note first that for any point $x < C_\gamma$ that is a point of continuity of F (and therefore of $F^{(\gamma)+}$ and $F^{(\gamma)-}$ as well), we have

$$ \lim_{\ell \to \infty} F^{(\ell,\gamma)+} (x) = F^{(\gamma)+} (x)$$

and

$$ \lim_{\ell \to \infty} F^{(\ell,\gamma)-} (x) = F^{(\gamma)-} (x).$$

Moreover, note that for any $x >0$ we have

$$\lim_{\gamma \downarrow 0} F^{(\gamma)+} (x), F^{(\gamma)-} (x) = F(x).$$

We will now turn to the size-biased versions of these distributions. Let $U^{(\gamma)+}$ and $U^{(\gamma)-}$ denote two random variables with probability distribution functions $F^{(\gamma)+}$ and $F^{(\gamma)-}$ , respectively. Thus, as $\ell \to \infty$ ,

(10) \begin{equation} U^{(\ell, \gamma)+} \stackrel{d}{\rightarrow} U^{(\gamma)+} \quad \mbox{and} \quad U^{(\ell, \gamma)-} \stackrel{d}{\rightarrow} U^{(\gamma)-},\end{equation}

whereas as $\gamma \downarrow 0$ we have

(11) \begin{equation} U^{(\gamma)+}, U^{(\gamma)-} \stackrel{d}{\rightarrow} W_F.\end{equation}

Claim 4. Let $(X_n)_{n\in \mathbb{N}}$ be a sequence of non-negative random variables. Suppose that W is a random variable such that $X_n \stackrel{d}{\rightarrow} W$ as $n\to \infty$ . For every $x>0$ which is a point of continuity of the cumulative distribution function of W, we have

$$\lim_{n\to \infty} \mathbb{E} (X_n \textbf{1}_{X_n \leq x}) = \mathbb{E} (W \textbf{1}_{W\leq x}). $$

This claim implies that for any $\gamma \in (0,1)$ , as $\ell \to \infty$ ,

(12) \begin{equation}F^{*(\ell,\gamma)+}(x)= \frac{ \mathbb{E} \big(U^{(\ell,\gamma)+} \textbf{1}_{U^{(\ell,\gamma)+} \leq x}\big)}{\mathbb{E} \Big(U^{(\ell,\gamma)+}\big)} \to \frac{\mathbb{E} \big(U^{(\gamma)+} \textbf{1}_{U^{(\gamma)+} \leq x}\big)}{\mathbb{E} \big(U^{(\gamma)+} \big)}\end{equation}

and

(13) \begin{equation} F^{*(\ell,\gamma)-}(x)= \frac{ \mathbb{E} \left(U^{(\ell,\gamma)-} \textbf{1}_{U^{(\ell,\gamma)-} \leq x}\right)}{\mathbb{E} \left(U^{(\ell,\gamma)-}\right)} \to \frac{\mathbb{E} \left(U^{(\gamma)-} \textbf{1}_{U^{(\gamma)-} \leq x}\right)}{\mathbb{E} \left(U^{(\gamma)-} \right)}.\end{equation}

Furthermore, we will show the following.

Proof. The proof is identical for both $U^{(\gamma)+}$ and $U^{(\gamma)-}$ , so we will denote these by $U^{(\gamma)\pm}$ . For $\delta>0$ , let ${\bar{C}_\delta}$ be a continuity point of F such that

(14) \begin{equation} \mathbb{E}\left(W_F \textbf{1}_{W_F > {\bar{C}_\delta}}\right) <\delta/3.\end{equation}

By Claim 4 we deduce that for any $\gamma$ sufficiently small,

(15) \begin{equation} | \mathbb{E} \left(U^{(\gamma)\pm} \textbf{1}_{U^{(\gamma)\pm} \leq {\bar{C}_\delta}}\right) - \mathbb{E} \left(W_{F} \textbf{1}_{W_{F} \leq {\bar{C}_\delta}}\right) | < \delta /3.\end{equation}

Let us bound $\mathbb{E} (U^{(\gamma)\pm} \textbf{1}_{U^{(\gamma)\pm} > {\bar{C}_\delta}})$ . Note that if $\gamma$ is small enough, then

$$\mathbb{E} \big(U^{(\gamma)\pm} \textbf{1}_{U^{(\gamma)\pm} > {\bar{C}_\delta}}\big)= \mathbb{E} \big(U^{(\gamma)\pm} \textbf{1}_{C_\gamma \geq U^{(\gamma)\pm} > {\bar{C}_\delta}}\big).$$

So it suffices to bound the latter term.

Claim 5. For any $\delta >0$ , if $\gamma$ is sufficiently small, then

$$\left|\mathbb{E} \left(U^{(\gamma)\pm} \textbf{1}_{C_\gamma \geq U^{(\gamma)\pm} > {\bar{C}_\delta}}\right) - \mathbb{E} \left(W_F \textbf{1}_{C_\gamma \geq W_F > {\bar{C}_\delta}}\right) \right| <\delta /3. $$

Proof. For ${\bar{C}_\delta} < x < C_\gamma$ , we have $F^{(\gamma)\pm} (x) = \lambda^{\pm} (\gamma) \cdot F(x)$ , where $\lambda^{\pm} (\gamma) \to 1$ as $\gamma\downarrow 0$ . Furthermore, $F^{(\gamma)^\pm} (C_\gamma) - F(C_\gamma) = 1 - (1- h_F(\gamma)) = h_F(\gamma)$ . For some integer $T> 0$ , consider a partition of $[0, C_\gamma]$ given by $p_0 =0 < p_1 < \cdots < p_T = C_\gamma$ , which are points of continuity of F. Taking $f(x) = x \textbf{1}_{{\bar{C}_\delta} < x \leq C\gamma}$ , we write

The second term on the right-hand side is

$$ \sum_{1\leq i<T} f(p_i) \Big(F^{(\gamma)^\pm} (p_i) - F^{(\gamma)^\pm} (p_{i-1})\Big) = \lambda^{\pm} (\gamma) \cdot \sum_{1\leq i<T} f(p_i) (F (p_i) - F (p_{i-1})).$$

The first term can be written as

\begin{align*}&f(p_T) \Big(F^{(\gamma)^\pm} (p_T) - F^{(\gamma)^\pm} (p_{T-1}) \Big) \\ &=f(p_T) \Big( F^{(\gamma)^\pm} (p_T) + F(p_T) - F(p_T)- F(p_{T-1}) + F(p_{T-1}) - F^{(\gamma)^\pm} (p_{T-1})\Big)\\ &= f(p_T) (F (p_T) - F (p_{T-1}) ) \\ & \hspace{2cm} + f(p_T) \Big(\Big(F^{(\gamma)^\pm} (p_T) - F(p_T) \Big)- \Big(F^{(\gamma)^\pm} (p_{T-1}) - F(p_{T-1}) \Big)\Big)\\ &\stackrel{p_T=C_\gamma}{=} f(p_T) (F (p_T) - F (p_{T-1}) ) \\ & \hspace{2cm} + f(p_T) \left((F^{(\gamma)^\pm} (C_\gamma) - F(C_\gamma) )- F(p_{T-1})(\lambda^{\pm} (\gamma) - 1) \right)\\ &\stackrel{F^{(\gamma)^\pm} (C_\gamma)=1, h_F(\gamma)=1-F(C_\gamma)}{=} f(p_T) (F (p_T) - F (p_{T-1}) ) \\ & \hspace{2cm} + f(p_T)\Big( h_F(\gamma) - F(p_{T-1})\Big(\lambda^{\pm} (\gamma) - 1 \Big)\Big)\\ &= \lambda^{\pm} (\gamma) f(p_T) (F (p_T) - F (p_{T-1}) ) + (1-\lambda^{\pm} (\gamma)) f(C_\gamma) (F (p_T) - F (p_{T-1}) ) \\ & \hspace{2cm}+ f(C_\gamma) h_F(\gamma) - f(C_\gamma)F(p_{T-1})\left(\lambda^{\pm} (\gamma) - 1 \right).\end{align*}

These two calculations imply that

Taking the limit of a sequence of partitions whose mesh tends to 0, we have $p_{T-1} \uparrow p_T = C_\gamma$ . Since $C_\gamma$ is a point of continuity for F, we obtain

By (5) we have that $C_\gamma h_F(\gamma) \downarrow 0$ as $\gamma \downarrow 0$ . Since $ |\lambda^{\pm} (\gamma) - 1| = O(\gamma^+ + h_F(C_\gamma))$ , by (7) we also have $C_\gamma |\lambda^{\pm} (\gamma) - 1| \downarrow 0$ as $\gamma \downarrow 0$ .

Combining Claim 5 with (14) and (15), we finally deduce that given $\delta >0$ , for any $\gamma$ that is sufficiently small, we have the following bound:

\begin{align*}\big|\mathbb{E} \big(U^{(\gamma)\pm}\big) - \mathbb{E} (W_F)\big| \leq & \big| \mathbb{E} \big(U^{(\gamma)\pm} \textbf{1}_{U^{(\gamma)\pm} \leq {\bar{C}_\delta}}\big) - \mathbb{E} \big(W_{F} \textbf{1}_{W_{F} \leq {\bar{C}_\delta}}\big) \big| \\&+ \Big| \mathbb{E} \Big(U^{(\gamma)\pm} \textbf{1}_{{\bar{C}_\delta} < U^{(\gamma)\pm} \leq C_\gamma}\Big) - \mathbb{E} \Big(W_{F} \textbf{1}_{{\bar{C}_\delta} < W_{F} \leq C_\gamma}\Big) \Big| \\&+ \mathbb{E}\big(W_F \textbf{1}_{W_F > C_\gamma}\big) < \delta.\end{align*}

Claim 4 also implies that for every $x >0$ which is a point of continuity of F, we have as $\gamma \downarrow 0$

(16) \begin{equation} |\mathbb{E} \big(U^{(\gamma)\pm} \textbf{1}_{U^{(\gamma)\pm} \leq x}\big) - \mathbb{E} \big(W_F \textbf{1}_{W_F \leq x}\big)| \downarrow 0 .\end{equation}

So from Lemma 2, (16), and (12)–(13) we deduce that for any continuity point $x \in \mathbb{R}$ and any $\delta >0$ there exists $\gamma_0 = \gamma_0 (\delta, x)$ with the property that for any $0< \gamma < \gamma_0$ there exists $\ell_0$ such that for any $\ell > \ell_0$ we have

(17) \begin{equation} \big| F^{*(\ell,\gamma)}(x) - F^{*}(x) \big| < \delta.\end{equation}

The above can now be translated into the next lemma.

Lemma 3. For any bounded and continuous function $f\,:\, \mathbb{R} \to \mathbb{R}$ the following holds: there exists a function $\gamma_f\,:\, \mathbb{R}_+ \to \mathbb{R}_+$ such that $\gamma_f(x) \downarrow 0$ as $x\downarrow 0$ , and moreover, for any $\delta >0$ and any $0< \gamma < \gamma_f (\delta )$ there exists $\ell_0$ with the property that for any $\ell > \ell_0$

$$ |\mathbb{E} \big(f\big(U^{*\pm (\ell,\gamma)}\big)\big) - \mathbb{E} \big(f\big(W_F^*\big)\big)| < \delta.$$

Although this is a straightforward restatement of weak convergence, we give it more explicitly as $U^{*\pm (\ell,\gamma)}$ depends on two parameters $\ell$ and $\gamma$ . It is for the sake of clarity that we state explicitly how these depend upon each other when taking the double limit.

This completes the first part of Definition 4. We now turn to the second part.

Part 2 of Definition 4. Since $F^{(\ell,\gamma)+}$ and $F^{(\ell,\gamma)-}$ are both constant (and equal to 1), for $x \geq 2 C_\gamma$ we have

\begin{equation*}\begin{split} \mathbb{E} \big( U^{(\ell,\gamma)\pm}\big) = \mathbb{E} \left( U^{(\ell,\gamma)\pm} \textbf{1}_{U^{(\ell,\gamma)\pm} \leq 2 C_\gamma}\right). \end{split}\end{equation*}

Furthermore,

\begin{equation*}\begin{split} \mathbb{E} \left[W_F\right] &= \mathbb{E} \left( W_F \textbf{1}_{W_F \leq 2C_\gamma}\right) +\mathbb{E} \left( W_F \textbf{1}_{W_F > 2 C_\gamma}\right).\end{split}\end{equation*}

Therefore,

(18)

The last term converges to 0 as $\gamma \downarrow 0$ since $\mathbb{E} \left( W_F\right) < \infty$ .

We will now bound the first term on the right-hand side in (18). We write $F^{(\ell,\gamma)\pm}$ for either of $F^{(\ell,\gamma)+}$ and $F^{(\ell,\gamma)-}$ . Using the integration-by-parts formula for the Lebesgue–Stieltjes integral, we can write

(19) \begin{equation} \begin{split}\mathbb{E} \left( U^{(\ell,\gamma)\pm} \textbf{1}_{U^{(\ell,\gamma)\pm} \leq 2 C_\gamma}\right) &= 2C_\gamma F^{(\ell,\gamma)\pm}(2C_\gamma+) -\int_{0}^{2C_\gamma} F^{(\ell,\gamma)\pm}(x)dx \\& = 2C_{\gamma} - \int_{0}^{2C_\gamma} F^{(\ell,\gamma )\pm}(x)dx.\end{split}\end{equation}

Using integration by parts, we also get

(20) \begin{equation} \begin{split} \mathbb{E} \left( W_F \textbf{1}_{W_F\leq 2C_\gamma}\right) &= 2C_\gamma \cdot F(2C_\gamma+) - 0\cdot F(0-) - \int_{0}^{2C_\gamma} F(x) dx \\&=2 C_\gamma \cdot (1- \mathbb{P}\left[W_F > 2C_\gamma\right]) - \int_{0}^{2C_\gamma} F (x) dx.\end{split}\end{equation}

Therefore,

(21) \begin{eqnarray}&& \left| \mathbb{E} \left( U^{(\ell,\gamma)\pm} \textbf{1}_{U^{(\ell,\gamma)\pm} \leq 2 C_\gamma}\right)- \mathbb{E} \left( W_F \textbf{1}_{W_F\leq 2C_\gamma}\right) \right| \leq \nonumber \\&&2 C_\gamma \mathbb{P}\left[W_F > 2C_\gamma\right]+ \int_0^{C_\gamma} |F^{(\ell,\gamma)\pm} (x) - F(x)| dx + \int_{C_\gamma}^{2C_\gamma} |F^{(\ell,\gamma)\pm} (x) - F(x)| dx.\nonumber \\ \end{eqnarray}

We will bound $\int_0^{C_\gamma} |F^{(\ell,\gamma)+} (x) - F(x)| dx$ . First, we write

\begin{eqnarray*}&&\int_{0}^{C_\gamma} |F^{(\ell,\gamma)+} (x) -F(x)| dx = {\sum_{i=0}^{p_\ell-1}}\int_{y_{i}}^{y_{i+1}} |F^{(\ell,\gamma)+} (x) -F(x)| dx \\&&= \sum_{i=0}^{t_\ell}\int_{y_{2i}}^{y_{2i+1}} |F^{(\ell,\gamma)+} (x) -F(x)| d x +\sum_{i=0}^{t_\ell-1}\int_{y_{2i+1}}^{y_{2(i+1)}} |F^{(\ell,\gamma)+} (x) -F(x)| dx.\end{eqnarray*}

For the first sum of integrals, note that for any $x\in [y_{2i},y_{2i+1})$ we have $|F(W_{2i}^-) - F(x)| \leq F(W_{2i}^+) - F(W_{2i}^-)$ . Therefore, each integrand is bounded as follows:

(22) \begin{align}|F^{(\ell,\gamma)+} (x) -F(x)| =& \left| \frac{F(W_{2i}^-)}{1-h_F(\gamma) +\gamma^+} - F(x)\right| =\left|\frac{F(W_{2i}^-) - F(x) (1-h_F(\gamma) + \gamma^+)}{1-h_F(\gamma) +\gamma^+} \right| \nonumber \\\leq& \frac{|F (W_{2i}^-) - F(x)|}{1-h_F(\gamma) +\gamma^+}+ F(x) \frac{|h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+} \nonumber \\\leq& \frac{ F(W_{2i}^+) - F(W_{2i}^-)}{1-h_F(\gamma) +\gamma^+} + \frac{|h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+}. \end{align}

Using this bound, we get

But $ \int_{y_{2i}}^{y_{2i+1}} dx = y_{2i+1} - y_{2i} \leq 2\varepsilon_\ell $ . So

$$ \sum_{i=0}^{t_\ell} \left( (F(W_i^+) - F(W_i^-)) \cdot \int_{y_{2i}}^{y_{2i+1}} dx \right) \leq2\varepsilon_\ell \cdot \sum_{i=0}^{t_\ell} \left( (F(W_i^+) - F(W_i^-)) \right)\leq 2 \varepsilon_\ell.$$

Furthermore,

$$ |h_F(\gamma) - \gamma^+\Big|\sum_{i=0}^{t_\ell} \int_{y_{2i}}^{y_{2i+1}} dx \leq C_\gamma \cdot |h_F(\gamma) - \gamma^+\Big| \leq C_\gamma \cdot |h_F(\gamma) - \gamma^+| .$$

We thus deduce that

$$ \sum_{i=0}^{t_\ell} \int_{y_{2i}}^{y_{2i+1}} |F^{(\ell,\gamma)+} (x) -F(x)| dx \leq \frac{2\varepsilon_\ell + C_\gamma |h_F(\gamma) - \gamma^+|}{1- h_F(\gamma) +\gamma^+}.$$

For the second integral, note that for $x\in [y_{2i+1},y_{2(i+1)})$ we have

$$\big|F \big(W_{2i+1}^-\big) - F(x)\big| \leq \varepsilon_\ell.$$

Arguing as in (22), we deduce that

$$ \big|F^{(\ell,\gamma)+} (x) -F(x)\big| \leq \frac{\varepsilon_\ell + |h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+}.$$

Therefore,

$$\sum_{i=0}^{t_\ell-1}\int_{y_{2i+1}}^{y_{2(i+1)}} |F^{(\ell,\gamma)+} (x) -F(x)| d x \leq\frac{C_\gamma (\varepsilon_\ell + |h_F(\gamma) - \gamma^+|)}{1-h_F(\gamma) + \gamma^+}.$$

We thus conclude that

(23) \begin{eqnarray}&&\int_{0}^{C_\gamma} |F^{(\ell,\gamma)+} (x) -F(x)| d x \leq \frac{\varepsilon_\ell (C_\gamma+2)+{2}C_\gamma |h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+} \,=\!:\, \hat{\rho}^+(\ell,\gamma). \end{eqnarray}

One can similarly show that

(24) \begin{eqnarray}\int_{0}^{C_\gamma} |F^{(\ell,\gamma)-} (x) -F(x)| d x &\leq&\frac{\varepsilon_\ell (C_\gamma+2)+{2} C_\gamma h_F(\gamma)}{1-h_F(\gamma) + p h_F(\gamma )} \,=\!:\, \hat{\rho}^- (\ell,\gamma). \end{eqnarray}

Note that $\lim_{\gamma \downarrow 0} \lim_{\ell \to \infty} \hat{\rho}^{\pm} (\ell,\gamma) =0$ .

Finally, we will consider $\int_{C_\gamma}^{2C_\gamma} |F^{(\ell,\gamma)+} (x) - F(x)| d x$ . For any $x \in [C_\gamma, 2C_\gamma]$ that is a point of continuity we have

\begin{eqnarray*}|F^{(\ell,\gamma)+} (x) -F(x)| &=& \left| \frac{F(x)}{1-h_F(\gamma) +\gamma^+} - F(x)\right| =\left|\frac{F(x) - F(x) (1-h_F(\gamma) + \gamma^+)}{1-h_F(\gamma) +\gamma^+} \right| \nonumber \\&\leq& F(x) \frac{|h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+}\leq\frac{|h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+}.\end{eqnarray*}

Therefore,

(25) \begin{equation} \begin{split}&\left|\int_{C_\gamma}^{2C_\gamma} (F^{(\ell,\gamma)+}(x) - F(x))dx \right| \leq \int_{C_\gamma}^{2C_\gamma}| F^{(\ell,\gamma)+}(x) - F(x)|dx \leq\\&\leq \frac{|h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+} \cdot (2C_\gamma -C_\gamma) = C_\gamma \cdot \frac{|h_F(\gamma) - \gamma^+|}{1-h_F(\gamma) + \gamma^+} \leq \hat{\rho}^+ (\ell,\gamma).\end{split}\end{equation}

Also,

(26) \begin{eqnarray}&&\int_{C_\gamma}^{2C_\gamma} \left| F^{(\ell,\gamma)-}(x)- F(x) \right| dx = \int_{C_\gamma}^{2C_\gamma} \left| 1- F(x) \right| dx = \int_{C_\gamma}^{2C_\gamma} \mathbb{P}\left[W_F > x\right]dx \nonumber \\&\leq& \int_{C_\gamma}^{\infty} \mathbb{P}\left[W_F \geq x\right] dx = \mathbb{E} \left( W_F \textbf{1}_{W_F \geq C_\gamma}\right).\end{eqnarray}

The latter $\downarrow 0$ as $\gamma \downarrow 0$ .

Now, substituting the bounds of (23), (24), (25), and (26) into (21), we get

(27) \begin{eqnarray}&& \left| \mathbb{E} \left( U^{(\ell,\gamma)\pm} \textbf{1}_{U^{(\ell,\gamma)\pm} \leq 2 C_\gamma}\right)- \mathbb{E} \left( W_F \textbf{1}_{W_F\leq 2C_\gamma}\right) \right| \leq \nonumber \\&& \hspace{4.5cm} 2 C_\gamma \mathbb{P}\left[W_F > 2C_\gamma\right] + {2}\hat{\rho}^{\pm} (\ell,\gamma) + \mathbb{E} \left( W_F \textbf{1}_{W_F \geq C_\gamma}\right). \nonumber\\ \end{eqnarray}

Using the upper bound of (27) in (18), and using the fact that $\mathbb{E} \left( W_F \textbf{1}_{W_F > 2C_\gamma}\right) \leq \mathbb{E} \left( W_F \textbf{1}_{W_F \geq C_\gamma}\right)$ , we finally get

(28) \begin{eqnarray}\left| \mathbb{E} \left( U^{(\ell,\gamma)\pm}\right) - \mathbb{E} \left( W_F\right) \right| &\leq& 2 C_\gamma \mathbb{P}\left[W_F > 2C_\gamma\right] +{2} \hat{\rho}^{\pm} (\ell,\gamma) + 2\mathbb{E} \left( W_F \textbf{1}_{W_F \geq C_\gamma}\right) \nonumber \\&\leq& {2 \hat{\rho}^{\pm} (\ell,\gamma) + 3\mathbb{E} \left( W_F \textbf{1}_{W_F \geq C_\gamma}\right)}.\end{eqnarray}

Another useful bound which can be deduced from (19) and (20), replacing $2C_\gamma$ with $C_\gamma$ , is

But note that $\mathbb{P}\left[U^{(\ell,\gamma)-}\leq C_\gamma\right] =1$ , whereas

$$\mathbb{P}\left[U^{(\ell,\gamma)+}\leq C_\gamma\right] = \frac{F(C_\gamma)}{1-h_F(\gamma)+\gamma^+}.$$

So

$$\left| \mathbb{P}\left[U^{(\ell,\gamma)+}\leq C_\gamma\right]- \mathbb{P}\left[W_F\leq C_\gamma\right] \right| =\frac{F(C_\gamma) |h_F(\gamma) - \gamma^+|}{1-h_F(\gamma)+\gamma^+}$$

and

$$\left| \mathbb{P}\left[U^{(\ell,\gamma)-}\leq C_\gamma\right]- \mathbb{P}\left[W_F\leq C_\gamma\right] \right| = \mathbb{P}\left[W_F> C_\gamma\right].$$

Thus,

(29)

whereas

(30) \begin{eqnarray}\left| \mathbb{E} \left( U^{(\ell,\gamma)+} \textbf{1}_{U^{(\ell,\gamma)\pm}\leq C_\gamma}\right)- \mathbb{E} \left( W_F\right) \right|&\leq& C_\gamma \mathbb{P}\left[W_F >C_\gamma\right]+ \hat{\rho}^{\pm} (\ell,\gamma) \nonumber \\&&+ \mathbb{E} \left( W_F \textbf{1}_{W_F > C_\gamma}\right). \end{eqnarray}

We conclude that (28), together with (5), (29), and (30), completes Part 2 of Definition 4.

3.1.2. Bounds on $|\mathcal{A}_f|$

For a subset $S \subseteq [n]$ , let $\mathcal{A}_f (S)$ denote the final set of infected vertices in $CL (\textbf{w})$ assuming that $\mathcal{A}_0 = S$ . With this notation, we have of course that $\mathcal{A}_f = \mathcal{A}_f (\mathcal{A}_0)$ . We also set $\mathcal{A}_f^-(S)$ to be the set of infected vertices in $CL^{\prime} \big(\textbf{W}^{(\ell,\gamma)-}\big)$ , assuming that the initial set is $\varphi^-(S \cap \cup_{i=1}^{p_\ell}\mathsf{C}_i) $ . Finally, for a subset $S \subseteq [n^{\prime}]$ , let $\mathcal{A}_f^+(S)$ be the final set of infected vertices on $CL^{\prime} \big(\textbf{W}^{(\ell,\gamma)+}\big)$ . We will show the following.

Claim 6. Let $p\in(0,1)$ . Assume that $\mathcal{A}_0$ is a random subset of [n] where each vertex is included with probability p independently of any other vertex. Then there is a coupling space on which, w.h.p.,

(31) \begin{equation}\big|\mathcal{A}_f^- \big(\mathcal{A}_0 \cup \mathsf{C}_\gamma^- \big)\big|\leq |\mathcal{A}_f| \leq \big|\mathcal{A}_f^+ \big(\mathcal{A}_0 \cup \mathsf{C}_\gamma^+\big)\big|.\end{equation}

In the proof of Claim 6 and elsewhere, we write that the probability that two vertices k and j, with $w_j(n) \leq C_\gamma$ , are adjacent is equal to $w_k(n) w_j(n)/W_{[n]}$ ; in other words, when we apply (1) we tacitly assume that n is sufficiently large so that this ratio is less than 1.

Proof of Claim 6. As $\mathcal{A}_0$ is formed by including every vertex in [n] independently with probability p, it follows that w.h.p. at least $k_-$ elements of $\mathsf{C}_\gamma$ become initially infected. We identify exactly $k_-$ of them with the set $\mathsf{C}_\gamma^-$ . Recall that for each $k \in \cup_{i=1}^{p_\ell}{ \mathsf{C}_i}$ we have $W_{\varphi^-(k)}^{(\ell,\gamma)-}(n) \leq w_k (n)$ . This implies that for each pair $k,k^{\prime} \in [n] \setminus \mathsf{C}_\gamma$ of distinct vertices, the probability that $\varphi^-(k)$ and $\varphi^- (k^{\prime})$ are adjacent in $CL^{\prime}\big(\textbf{W}^{(\ell,\gamma)-}\big)$ is smaller than the corresponding probability for k and k ^′ in $CL (\textbf{w})$ . Hence, there is a coupling space on which

$$ CL^{\prime}\big(\textbf{W}^{(\ell,\gamma)-}\big) \subseteq CL(\textbf{w}), $$

and the first inequality in (31) follows. The second inequality follows from a slightly more involved argument. Let $j \in \mathsf{C}_\gamma$ be such that $w_j (n) \geq 2C_\gamma$ , and let $k \in \cup_{i=1}^{p_\ell} \mathsf{C}_i $ . The probability that k is adjacent to j in $CL(\textbf{w})$ is equal to $w_k w_j / W_{[n]}$ . Also, the probability that k is adjacent to at least one of the copies of j in [n ^′] in the random graph $CL^{\prime}\big(\textbf{W}^{(\ell,\gamma)+}\big)$ is

$$ 1 - \left( 1- \frac{2W^{(\ell,\gamma)+}_{\varphi^+(k)} C_\gamma}{W_{[n]}} \right)^{2 \lfloor {w_j / C_\gamma}\rfloor}. $$

Assume we have shown that for n sufficiently large we have that for any $k \in \cup_{i=1}^{p_\ell} \mathsf{C}_i $ and any $j \in \mathsf{C}_\gamma$ ,

(32) \begin{equation} \frac{w_k w_j}{W_{[n]}} \leq 1 - \left( 1- \frac{2W^{(\ell,\gamma)+}_{\varphi^+(k)} C_\gamma}{W_{[n]}} \right)^{2 \lfloor {w_j / C_\gamma}\rfloor}.\end{equation}

Moreover, assume that every vertex in $\mathsf{C}^{\prime}_\gamma$ is among those vertices that are initially infected. Now, observe that there is a coupling space in which we have

(33) \begin{equation} CL(\textbf{w})\big[\cup_{i=1}^{p_\ell}\mathsf{C}_i\big] \subseteq CL^{\prime}\big(\textbf{W}^{(\ell,\gamma)+}\big)\big[\cup_{i=1}^{p_\ell}\mathsf{C}_i\big].\end{equation}

This is the case because for any $k \in \cup_{i=1}^{p_\ell}\mathsf{C}_i$ we have $w_k \leq W_{\varphi^+(k)}^{(\ell,\gamma)+}$ . Consider a vertex $k \in \cup_{i=1}^{p_\ell}\mathsf{C}_i$ and now let $j \in \mathsf{C}_\gamma$ . Then the inequality (32) implies that the probability that k is adjacent to j in $CL(\textbf{w})$ is at most the probability that $\varphi^+(k)$ is adjacent to at least one of the copies of j in [n ^′] within $CL^{\prime}\big(\textbf{W}^{(\ell,\gamma)+}\big)$ . Therefore, it follows that the number of neighbors of k in $\mathsf{C}_\gamma$ in the random graph $CL(\textbf{w})$ is stochastically dominated by the size of the neighborhood of k in $\mathsf{C}^{\prime}_\gamma$ in the random graph $CL^{\prime}\big(\textbf{W}^{(\ell,\gamma)+}\big)$ . This observation, together with (33), implies that

$$ \big|\mathcal{A}_f \big(\mathcal{A}_0 \cup \mathsf{C}_\gamma\big)\big| \leq_{st} \big|\mathcal{A}_f^+\big(\mathcal{A}_0 \cup \mathsf{C}_\gamma^+\big)\big|.$$

But also,

\begin{equation*} |\mathcal{A}_f| \leq_{st} |\mathcal{A}_f (\mathcal{A}_0 \cup \mathsf{C}_\gamma)|.\end{equation*}

The second stochastic inequality of the claim follows from the above two inequalities. It remains to show (32). Let us abbreviate $W_{\varphi^+(k)}^{(\ell,\gamma)+}\,=\!:\,W_k$ . Using the Bonferroni inequalities we have

(34) \begin{equation} \begin{split} &1 - \left( 1- \frac{2 W_k C_\gamma}{W_{[n]}} \right)^{2 \lfloor {w_j / C_\gamma}\rfloor} \geq 2 \Big\lfloor \frac{w_j}{C_\gamma}\Big\rfloor \frac{2 W_k C_\gamma}{W_{[n]}} - 2 \left( {w_j / C_\gamma} \right)^2 \,\frac{4 W_k^2 C_\gamma^2}{W_{[n]}^2}.\end{split}\end{equation}

But

$$ 2 \Big\lfloor \frac{w_j}{C_\gamma}\Big\rfloor \frac{2 W_k C_\gamma}{W_{[n]}} \geq2 \left(\frac{w_j}{C_\gamma} -1 \right) \frac{2 W_k C_\gamma}{W_{[n]}}= 2 \frac{w_j}{C_\gamma} \left( 1- \frac{C_\gamma}{w_j} \right) \frac{2 W_k C_\gamma}{W_{[n]}}\stackrel{w_j /C_\gamma \geq 2}{\geq}\frac{2 W_k w_j}{W_{[n]}}.$$

Substituting this lower bound into (34), we obtain

\begin{eqnarray*}1 - \left( 1- \frac{2 W_k C_\gamma}{W_{[n]}} \right)^{2 \lfloor \frac{w_j}{C_\gamma}\rfloor} &\geq&\frac{2 W_k w_j}{W_{[n]}} - \frac{8 W_k^2 w_j^2}{W_{[n]}^2} = \frac{2 W_k w_j}{W_{[n]}} \left(1 - \frac{4 W_k w_j}{W_{[n]}} \right) \\ &>& \frac{W_k w_j}{W_{[n]}}\geq \frac{w_k w_j}{W_{[n]}},\end{eqnarray*}

for n sufficiently large, as $w_k < C_\gamma$ and $w_j = w_j(n) = o(n)$ (uniformly for all j) but $W_{[n]} = \Theta (n)$ .

We will now apply Theorem 3 to the random variables that bound $|\mathcal{A}_f|$ in Claim 6. Theorem 3 implies that there exists $\gamma_2 >0$ satisfying the following: for any $\gamma < \gamma_2$ and any $\delta \in (0,1)$ there exists an infinite set of natural numbers $\mathcal{S}^1$ such that for every $\ell \in \mathcal{S}^1$ , with probability $1-o(1)$ ,

(35) \begin{equation} \begin{split}n^{-1}{\big|\mathcal{A}_f^{+} \big(\mathcal{A}_0 \cup \mathsf{C}_\gamma^+\big) \big|} \leq (1+ \delta) ((1-p) \mathbb{E} \left[ \psi_r( W_F \hat{y})\right] + p),\end{split}\end{equation}

and there exists an infinite set of natural numbers $\mathcal{S}^2$ such that for every $\ell \in \mathcal{S}^2$ , with probability $1-o(1)$ ,

(36) \begin{equation} \begin{split}n^{-1}{\big|\mathcal{A}_f^- \big(\mathcal{A}_0 \cup \mathsf{C}_\gamma^- \big) \big|} \geq (1-\delta) ((1-p) \mathbb{E} \left[ \psi_r(W_F \hat{y})\right] + p).\end{split}\end{equation}

Hence, Claim 6 together with (35) and (36) imply the following w.h.p. bounds on the size of $\mathcal{A}_f$ :

\begin{equation*}\begin{split}n^{-1} {|\mathcal{A}_f| } = (1\pm \delta) ((1-p) \mathbb{E} \left[ \psi_r (W_F \hat{y})\right] + p),\end{split}\end{equation*}

from which Theorem 1 follows.

4.4.1. The end of the process

We will show that w.h.p. only a small fraction of vertices are added after $T_{D_\epsilon}$ . From now on, we start exposing the edges incident to all vertices of $\mathsf{U}$ simultaneously. Hence, we change the time scaling. Informally, each round will be approximated by a generation of a multi-type branching process which is subcritical. The subcriticality is encompassed by the following: there exists $\kappa_0 < 1$ such that with probability $1-o(1)$ ,

(58) \begin{equation} \sum_{i=1}^{p_\ell} \frac{W_i^2}{W_{[n]}}c_{i, r-1}\left( \frac{T_{D_{\epsilon}}-1}{n} \right) < \kappa_0 < 1.\end{equation}

We start this section by proving this. First, let us observe that using the expression for $\mu_{\mathsf{U}}$ from Proposition 2 and the chain rule, for any $\tau < T_{D_\epsilon}$ we can write

$$\mu^{\prime}_{\mathsf{U}} (\tau) = G(\tau ) f_r^{(\ell,\gamma)\prime} (I(\tau)/d),$$

where

$$f_r^{(\ell,\gamma)} (x)=\frac{W^{\prime}_{\gamma}}{d} +p\, \frac{1}{d}\sum_{i=1}^{p_\ell} W_i \gamma_i -x +(1-p)\,\frac{1}{d} \sum_{i=1}^{p_\ell} W_i \gamma_i \mathbb{P}\left[\mathsf{Po} \left( W_i x \right) \geq r\right].$$

But also by (45) we can write

$$ \mu^{\prime}_{\mathsf{U}}(\tau) = G(\tau) \left( -1 +\sum_{i=1}^{p_\ell} \frac{W_i^2}{d}\gamma_{i, r-1}\left( \tau \right) \right).$$

So in particular, for $\tau = (T_{D_\epsilon} -1)/n$ , we have $G((T_{D_\epsilon} -1)/n) >0$ and therefore (with $x(\tau) = I(\tau)/d$ )

$$ f_r^{(\ell,\gamma)\prime} \left(x\left(\frac{T_{D_\epsilon} -1}{n} \right)\right) = -1 +\sum_{i=1}^{p_\ell} \frac{W_i^2}{d} \gamma_{i, r-1}\left( \frac{T_{D_\epsilon} -1}{n} \right). $$

But by Lemma 5 and Proposition 4 below, for any $\delta \in (0,1)$ there exists $c_1>0$ with the property that for any $\gamma < c_1$ there exists an infinite set of positive integers $\mathcal{S}$ such that when $\ell \in \mathcal{S}$ , it holds that

\begin{equation*}f_r^{(\ell, \gamma)\prime} \big(\hat{y}_{\ell,\gamma}\big) < f^{\prime}_r (\hat{y};\,W_F^*,p) +\delta,\end{equation*}

and, moreover, $\hat{y}_{\ell,\gamma} <1$ . (Note that $\hat{y} <1$ by its definition.) By Claim 15 below, the family $\big\{ f_r^{(\ell, \gamma)\prime} (x)\big\}_{\ell \geq \ell^{\prime}_1}$ restricted to [0,1] for $\ell^{\prime}_1 = \ell^{\prime}_1(\gamma)$ is equicontinuous provided that $\gamma < c^{\prime}_4$ . Hence, for any $\gamma < c_1 \wedge c^{\prime}_4$ and any $\ell$ sufficiently large in $\mathcal{S}$ , using (56), we conclude that if $\varepsilon$ is sufficiently small we have

$$ f_r^{(\ell,\gamma)\prime} \left(x\left(\frac{T_{D_\epsilon} -1}{n} \right)\right) < f^{\prime}_r (\hat{y};\,W_F^*,p) +2\delta.$$

We select $\delta$ small enough so that the right-hand side of the above is negative. This and (51) imply that there exists $\kappa_0 < 1$ such that (58) holds with probability $1-o(1)$ .

From step $T_{D_\epsilon}$ onward, we will provide a stochastic upper bound on $\mathsf{U}$ by a set $\widehat{\mathsf{U}}$ , whose size is an essentially subcritical multi-type branching process. In particular, the expression in (58) will dominate the principal eigenvalue of the expected progeny matrix of this branching process. In this process, rather than exposing the vertices of $\widehat{\mathsf{U}}$ one at a time, we will expose all of their neighbors simultaneously in each round. We let $\widehat{\mathsf{U}}(s)$ be the set $\widehat{\mathsf{U}}$ after s rounds.

Hence, $\widehat{\mathsf{U}}(s)$ will be the sth generation of this process, which resembles a multi-type branching process. We will keep track of the size of $\widehat{\mathsf{U}}$ through a functional which is well known in the theory of multi-type branching processes to give rise to a supermartingale. Let us proceed with the details of this argument.

We set $t_0\,:\!=\,T_{D_{\epsilon}}-1$ . Let $\widehat{\mathsf{U}} (0) = \mathsf{U}(t_0)$ , $\widehat{\mathsf{C}}_{i,r-1}(0)=\mathsf{C}_{i,r-1}(t_0)$ , and $\widehat{\mathsf{C}}_{i,<r-1}(0) = \cup_{k=2}^r \mathsf{C}_{i,r-k}(t_0)$ , for all $i=1,\ldots,p_\ell$ . Let $\widehat{\mathsf{U}}_i (s)$ denote the subset of $\widehat{\mathsf{U}} (s)$ which consists of those vertices that have weight $W_i$ , and let $u_i(s)\,:\!=\, |\widehat{\mathsf{U}}_i(s)|$ —we say that these vertices are of type i. We set $\hat{c}_{i,<r-1}(s)=|\widehat{\mathsf{C}}_{i, <r-1}(s)|$ and $\hat{c}_{i,r-1}(s) = |\widehat{\mathsf{C}}_{i,r-1}(s)|$ . Let $\overline{u}_s= [u_1(s),\ldots, u_{p_\ell}(s)]^T$ be the vector whose coordinates are the sizes of the sets $\widehat{\mathsf{U}}_i (s)$ . A vertex $v \in\widehat{\mathsf{U}}_j(s)$ (for $j\in\{1,\ldots,p_\ell\}$ ) can ‘give birth’ to vertices of type i (i.e., of weight $W_i$ ). These may be vertices from the set $\widehat{\mathsf{C}}_{i,r-1}(s)$ or from the set $\widehat{\mathsf{C}}_{i,<r-1}(s)$ . If v becomes adjacent to a vertex in $\widehat{\mathsf{C}}_{i,r-1}(s)$ , then a child of v is produced. Similarly, we say that a vertex in $\widehat{\mathsf{C}}_{i,<r-1}(s)$ produces a child of v if it is adjacent to v and to some other vertex in $\widehat{\mathsf{U}}(s)$ . In that sense, a vertex in $\widehat{\mathsf{C}}_{i,r-1} \cup \widehat{\mathsf{C}}_{i,<r-1}$ may be responsible for the birth of a child of more than one vertex in $\widehat{\mathsf{U}}(s)$ .

Furthermore, if a vertex in $\widehat{\mathsf{C}}_{i,<r-1}(s)$ is adjacent to exactly one vertex in $\widehat{\mathsf{U}}(s)$ , then a vertex is moved into $\widehat{\mathsf{C}}_{i,r-1}$ . In this process the set $\widehat{\mathsf{C}}_{i,r-1}$ can only gain, not lose, vertices. Clearly, $|\widehat{\mathsf{U}}(s)|$ is a stochastic upper bound on $\mathsf{U}$ .

If a vertex is a child of more than one vertex, we assume that it is born only once (it could be a child of any adjacent vertex in $\widehat{\mathsf{U}}(s)$ ); hence it is included in $\widehat{\mathsf{U}}(s+1)$ only once. In fact, the former case is much more likely than the latter. The expected number of those children that are born out of $\mathsf{C}_{i,r-1}(s)$ is bounded by $\frac{W_j W_i}{W_{[n]}} c_{i,r-1} (s)$ . The expected number of vertices of type i that originate from $\widehat{\mathsf{C}}_{i,<r-1}$ is bounded by $\hat{c}_{i,<r-1}(s)\frac{W_j W_i}{W_{[n]}} \left( |\widehat{\mathsf{U}}(s)| (2 C_\gamma)^2/W_{[n]} \right)$ . This is the case because the factor $|\widehat{\mathsf{U}}(s)| (2 C_\gamma)^2/W_{[n]}$ bounds from above the probability that a given vertex in $\widehat{\mathsf{C}}_{i,<r-1}(s)$ is adjacent to some other vertex in $\widehat{\mathsf{U}}(s)$ .

Now, if we let $A_s$ be the $p_\ell \times p_\ell$ matrix whose ij entry is the expected number of children of type i that a vertex of type j has, then $\mathbb{E} \left( \overline{u}_{s+1}^{T} | \mathcal{H}_s\right) \leq \overline{u}_s^{T} A_s$ (the inequality is meant to be pointwise), where $\mathcal{H}_s$ is the sub- $\sigma$ -algebra generated by the history of the process up to round s. One can view the matrix $A_s$ as the expected progeny matrix of a multi-type branching process, where the expected number of children of type j that a vertex of type i gives birth to is at most

$$A_s [i,j]\,:\!=\,\frac{W_iW_j}{W_{[n]}}a_j(s), \ \mbox{where} \ a_j(s)\,:\!=\,\hat{c}_{j,r-1}(s) +\hat{u}(s) \frac{4 C_\gamma^2}{W_{[n]}}\hat{c}_{j,<r-1} (s). $$

Throughout this section, we will be working with this upper bound, which comes from a stochastic upper bound on the process. It is not hard to see that the vector $[W_1,\ldots, W_{p_\ell}]^T$ is a right eigenvector of $A_s$ , with

$$\sum_{i=1}^{p_\ell} \frac{W_i^2}{W_{[n]}} a_i(s)\,=\!:\,\rho_s$$

being the corresponding eigenvalue. In fact, this is the unique positive eigenvalue of $A_s$ . Since $\hat{c}_{j,r-1}(s)$ does not decrease, we have $\hat{c}_{j,r-1} (s) \geq \hat{c}_{j,r-1}(0) =c_{i, r-1}\left( \frac{T_{D_{\epsilon}}-1}{n} \right) $ . Thus for $s>0$ we have

$$\rho_s \geq \sum_{i=1}^{p_\ell} \frac{W_i^2}{W_{[n]}}c_{i, r-1}\left( \frac{T_{D_{\epsilon}}-1}{n} \right) >\kappa^{\prime}_0 >0,$$

for some constant $\kappa^{\prime}_0$ and for any n sufficiently large.

Note also that since $\hat{c}_{j,r-1}(s),\hat{u}(s)$ , $\hat{c}_{j,<r-1} (s)\leq n$ , and $W_{[n]} = \Theta (n)$ , we have the bound $\rho_s \leq D$ for some $D>0$ , which depends on $\gamma$ , and for all $s\geq 0$ .

For $s=0$ , it is not hard to see that $\rho_{0}$ is less than and bounded away from 1, if we choose $\epsilon$ small enough. Indeed, by (53),

$$ \hat{u}(0) \frac{4 C_\gamma^2}{W_{[n]}}\hat{c}_{j,<r-1} (0) \leq\hat{u}(0) \frac{4 C_\gamma^2}{W_{[n]}} n < \hat{u} (0) \frac{5 C_\gamma^2}{d n} n \stackrel{(53)}{\leq } \epsilon \frac{15 C_\gamma^2}{2d} n.$$

Hence, combining this with (58), we deduce that if $\epsilon$ is small enough, then $\rho_{0}$ is smaller than 1 and in fact is bounded away from 1.

Let $\lambda_i\,:\!=\, W_i /\sum_j W_j$ and set $\xi\,:\!=\,[\lambda_1,\ldots, \lambda_{p_\ell}]^T$ . Clearly, this is also a right eigenvector of $A_t$ . Consider now the random variable $Z_s = (\xi, \overline{u}_s)$ , where $(\cdot ,\cdot)$ is the usual dot product. Therefore,

$$ \mathbb{E} \left( Z_{s+1} | \mathcal{H}_s\right) \leq \rho_s Z_s. $$

Claim 11. Conditional on $\mathcal{H}_s$ , with probability at least $1-1/n^2$ , we have $Z_s=0$ or

(59) \begin{align}Z_{s+1} \leq \rho_s Z_s + Z_s^{1/2}\log^{3/2} n.\end{align}

Proof. In the following we condition on $\mathcal{H}_s$ , which is suppressed from the notation. Assume that $Z_s >0$ . Note that $Z_{s+1}$ is a weighted sum of Bernoulli-distributed random variables, where the weights are bounded. More specifically,

$$Z_{s+1} = \sum_{j=1}^{p_\ell} \lambda_{j}\left( \sum_{v \in \widehat{\mathsf{C}}_{j,r-1}(s)}\textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 1} + \sum_{v \in \widehat{\mathsf{C}}_{j,<r-1}(s)}\textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 2} \right).$$

This expansion also shows that $Z_s >0$ implies that $Z_s >c$ , for some $c> 0$ which does not depend on s (or n).

We will appeal to Talagrand’s inequality (see for example Theorem 2.29 in [Reference Janson, Łuczak and Ruciński25]).

Theorem 12. Let $Z_1,\ldots, Z_N$ be independent random variables taking values in some sets $\Lambda_1,\ldots, \Lambda_N$ , respectively. Suppose that $X=f(Z_1,\ldots, Z_N)$ , where $f\,:\, \Lambda_1 \times \cdots \times \Lambda_N \to \mathbb{R}$ is a function which satisfies the following conditions:

1. (i) There are constants $c_k$ , for $k=1,\ldots, N$ , such that if $z,z^{\prime} \in \Lambda_1 \times \cdots \times \Lambda_N$ differ only in their kth coordinates, $z_k$ and $z^{\prime}_k$ respectively, then $|f(z) - f(z^{\prime})| \leq c_k$ .

2. (ii) There exists a function $\psi\,:\,\mathbb{R} \to \mathbb{R}$ such that if $z \in \Lambda_1 \times \cdots \times \Lambda_N$ satisfies $f(z)\geq r$ , then there is a witness set $J \subseteq \{1,\ldots, N \}$ with $\sum_{k\in J }c_k^2 \leq \psi (r)$ such that any $y \in \Lambda_1 \times \cdots \times \Lambda_N$ with $y_k=z_k$ , for $k \in J$ , also has $f(y)\geq r$ .

If m is a median of X, then for every $t\geq 0$ ,

$$ \mathbb{P} (X \leq m - t) \leq 2 e^{-t^2/4 \psi (m)}$$

and

$$ \mathbb{P} (X \geq m + t) \leq 2 e^{-t^2/4 \psi (m+t)}.$$

We will apply Theorem 12 to the random variable $Z_{s+1}$ . First, note that $Z_{s+1}$ is a function of independent Bernoulli random variables, which correspond to the (potential) edges that are incident to $\widehat{\mathsf{U}}(s)$ . Let us write the random variable $Z_{s+1}$ more explicitly as a function on the sample space which consists of all subsets of $\cup_{j=1}^{p_\ell} \left( \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s)\right) \times \widehat{\mathsf{U}} (s)$ . More specifically, for any subset

$$E \subseteq \cup_{j=1}^{p_\ell} \left( \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s)\right) \times \widehat{\mathsf{U}} (s)$$

we can write

$$ Z_{s+1} (E)= \sum_{j=1}^{p_\ell} \lambda_{j}\left( \sum_{v \in \widehat{\mathsf{C}}_{j,r-1}(s)}\textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 1}(E) + \sum_{v \in \widehat{\mathsf{C}}_{j,<r-1}(s)}\textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 2}(E) \right),$$

where the $\textbf{1}_{\mathcal{E}}(E)$ denotes the indicator function of the event $\{E \,:\, E \in \mathcal{E}\}$ . For $v \in \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s) $ , if we change any pair of vertices between v and $\widehat{\mathsf{U}}(s)$ (add it if it is not an edge, or remove it if it is), then $Z_{s+1}$ may change by at most $\lambda_j$ .

Now, for any subset of edges $E \subseteq \cup_{j=1}^{p_\ell} \left( \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s)\right) \times \widehat{\mathsf{U}} (s)$ and a subset $J \subseteq \cup_{j=1}^{p_\ell} \left( \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s)\right)$ , let

$$Z_{s+1}^{J} (E) = \sum_{j=1}^{p_\ell} \lambda_{j}\left( \sum_{v \in \widehat{\mathsf{C}}_{j,r-1}(s) \cap J}\textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 1} (E) + \sum_{v \in \widehat{\mathsf{C}}_{j,<r-1}(s)\cap J}\textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 2}(E) \right).$$

Suppose that $Z_{s+1}(E)\geq x$ . Let $J^* = J^*(E) \subseteq \cup_{j=1}^{p_\ell} \left( \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s)\right)$ be a minimal subset which is also a minimizer of $Z_{s+1}^J (E)$ subject to $Z_{s+1}^J(E)\geq x$ . (Note that a minimizer may not be minimal, as it may include a vertex v such that $\textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 1} (E),\ \textbf{1}_{d_{\widehat{\mathsf{U}}(s)}(v) \geq 2} (E)=0$ .) Observe that the minimality of $J^*$ implies that $Z_{s+1}^{J^*}(E) < x + \lambda_{max}$ , where $\lambda_{\max} = \max \{\lambda_j\}_{j=1,\ldots, p_\ell}$ .

We select a set of edges $E_{J^*}\subseteq E$ as follows: for any $v \in \widehat{\mathsf{C}}_{j,r-1}(s) \cap J^*$ , we add to $E_{J^*}$ one of the edges in E that are incident to v, if there are any such; for any $v \in \widehat{\mathsf{C}}_{j,<r-1}(s) \cap J^*$ , we add to $E_{J^*}$ two of the edges in E that are incident to v, if there are at least two such edges. Hence, any subset of edges $E^{\prime} \subseteq \cup_{j=1}^{p_\ell} \left( \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s)\right) \times \widehat{\mathsf{U}} (s)$ such that $E_{J^*} \subseteq E^{\prime}$ also satisfies $Z_{s+1}(E^{\prime})\geq x$ .

For any $e\in \left( \widehat{\mathsf{C}}_{j,r-1}(s) \cup \widehat{\mathsf{C}}_{j,<r-1}(s)\right) \times \widehat{\mathsf{U}} (s)$ , we set $\lambda_e = \lambda_j$ . Consider now $\sum_{e \in E_{J^*}} \lambda_e^2$ . Since $\lambda_e \leq 1$ , we have the bound

\begin{eqnarray*}\sum_{e \in E_{J^*}} \lambda_e^2 &\leq& \sum_{j=1}^{p_\ell} \left(\sum_{e \in \left( \widehat{\mathsf{C}}_{j,r-1}(s) \times \widehat{\mathsf{U}} (s) \right) \cap E_{J^*}} \lambda_e +\sum_{e \in \left( \widehat{\mathsf{C}}_{j,<r-1}(s) \times \widehat{\mathsf{U}} (s) \right) \cap E_{J^*}} \lambda_e \right) \\&=&\sum_{j=1}^{p_\ell} \left(\sum_{e \in \left( \widehat{\mathsf{C}}_{j,r-1}(s) \times \widehat{\mathsf{U}} (s) \right) \cap E_{J^*}} \lambda_j +\sum_{e \in \left( \widehat{\mathsf{C}}_{j,<r-1}(s) \times \widehat{\mathsf{U}} (s) \right) \cap E_{J^*}} \lambda_j \right) \\&=& \sum_{j=1}^{p_\ell} \left(\sum_{v \in \widehat{\mathsf{C}}_{j,r-1}(s) \cap J^*} \lambda_j +2\sum_{v \in \widehat{\mathsf{C}}_{j,<r-1}(s) \cap J^*} \lambda_j \right) \\&\leq &2 Z_{s+1}^{J^*} \leq 2 (x+ \lambda_{\max}).\end{eqnarray*}

Hence, we can apply Theorem 12, taking $\psi (x) = 2(x+\lambda_{\max})$ (conditional on $\mathcal{H}_s$ which we suppress). With $m(Z_{s+1})$ being a median of $Z_{s+1}$ , Talagrand’s inequality yields

(60) \begin{equation} \mathbb{P} \left[Z_{s+1} \geq m(Z_{s+1}) + \frac{1}{2}Z_s^{1/2}\log^{3/2} n\right] \leq 2 e^{-\frac{Z_s \log^3 n}{32\bigl(m (Z_{s+1})+\frac{1}{2} Z_s^{1/2}\log^{3/2} n+\lambda_{\max}\bigr)}}.\end{equation}

Since $\psi (x)$ is increasing with respect to x and $Z_{s+1}$ takes only non-negative values, using an argument similar to that of [Reference Janson, Łuczak and Ruciński25, pp. 41–42] we have

\begin{align*} &|\mathbb{E} \left( Z_{s+1}\right) - m(Z_{s+1}) | \leq \mathbb{E} \left( |Z_{s+1} - m(Z_{s+1})|\right) =\int_0^\infty \mathbb{P} \left[|Z_{s+1} - m(Z_{s+1})|>t\right] dt \\ &\leq \int_0^{m(Z_{s+1})} 4 e^{-\frac{t^2}{4 \psi (2m(Z_{s+1}))}}dt + \int_{m(Z_{s+1})}^{\infty} 2 e^{-\frac{t^2}{4 \psi (m(Z_{s+1})+t)}}dt \\ &\leq \int_0^{m(Z_{s+1})} 4 e^{-\frac{t^2}{16m(Z_{s+1})+8 \lambda_{\max}}}dt + \int_{m(Z_{s+1})}^{\infty} 2 e^{-\frac{t^2}{16t+8\lambda_{\max}}}dt \\ &\leq 8\sqrt{\pi(m(Z_{s+1})+\lambda_{\max})} + 32, \end{align*}

and using that $m(Z_{s+1}) \leq 2 m(Z_{s+1}) \mathbb{P} \left[Z_{s+1}\geq m(Z_{s+1})\right] \leq 2\mathbb{E} \left( Z_{s+1}\right)$ , we obtain

$$ |\mathbb{E} \left( Z_{s+1}\right) - m(Z_{s+1}) | = O(\mathbb{E} \left( Z_{s+1}\right)^{1/2}). $$

Hence, for n large enough, using that $\mathbb{E} \left( Z_{s+1}\right)\leq \rho_s Z_{s}$ , we have

\begin{equation*}\begin{split}&\mathbb{P} \left[Z_{s+1} \geq \mathbb{E} \left( Z_{s+1}\right) + Z_s^{1/2}\log^{3/2} n\right] \\& \leq\mathbb{P} \left[Z_{s+1} \geq m(Z_{s+1}) - O(\mathbb{E} \left( Z_{s+1}\right)^{1/2}) + Z_s^{1/2}\log^{3/2} n\right] \\& \leq \mathbb{P} \left[Z_{s+1} \geq m(Z_{s+1}) + \frac{1}{2}Z_s^{1/2}\log^{3/2} n\right].\end{split}\end{equation*}

So by (60) we conclude (using that $m(Z_{s+1}) \leq 2 \mathbb{E} \left( Z_{s+1}\right)\leq 2 \rho_s Z_{s}$ ) that

since $\rho_s$ and $\lambda_{\max}$ are bounded uniformly over all s and $Z_s$ is bounded away from 0, if $Z_s >0$ .

We denote the above event ( $Z_s=0$ or (59) holds) by $\mathcal{E}_s$ . If $Z_s > \log^6 n$ and $\mathcal{E}_s$ is realized, we have

(61) \begin{equation} \begin{split}Z_{s+1} &\leq \rho_s Z_s \left( 1 + \frac{Z_s^{1/2} \log^{3/2} n}{\rho_s Z_s} \right) \stackrel{\rho_s \geq \kappa^{\prime}_{0}}{\leq} \rho_s Z_s\left( 1 + \frac{\log^{3/2} n}{\kappa^{\prime}_{0} Z_s^{1/2}} \right) \\ &\stackrel{Z_s > \log^6 n}{\leq}\rho_s Z_s \left( 1 + \frac{\log^{3/2} n}{\kappa^{\prime}_{0} \log^3 n} \right) = \rho_s Z_s \left( 1 + \frac{1}{\kappa^{\prime}_{0} \log^{3/2} n} \right) .\end{split}\end{equation}

In a multi-type branching process, the variable $Z_s/\rho^s$ , where $\rho$ is the largest positive eigenvalue of the progeny matrix, is a martingale (see for example Theorem 4 in Chapter V.6 of [Reference Athreya and Ney8]). Here we use this fact only approximately, since the progeny matrix changes as the process evolves. Nevertheless, it does not change immensely, and we are able to control the increase of the eigenvalue $\rho_s$ . Let us now make this precise.

By (58), the largest positive eigenvalue of $A_{0}$ is bounded by a constant $\rho_0 <1$ , with probability $1-o(1)$ . We set $\lambda_{\min}=\min \{ \lambda_i\}_{i=1,\ldots , p_\ell}$ . For any $s \geq 0$ , let

$$\mathcal{D}_s \,:\!=\,\left\{ \sum_{j=1}^{p_\ell} \sum_{v \in \widehat{\mathsf{U}}(s)} d_{\widehat{\mathsf{C}}_{j,<r-1} (s)}(v) <\max \left\{ \frac{10 C_\gamma^2}{\lambda_{\min} d} Z_s ,\log^6 n\right\} \right\}. $$

Proof of Claim 13. The random variable

$$\sum_{j=1}^{p_\ell} \sum_{v \in \widehat{\mathsf{U}}(s)} d_{\widehat{\mathsf{C}}_{j,<r-1} (s)}(v)$$

is stochastically bounded from above by $\sum_{v \in \widehat{\mathsf{U}}(s)} X_v$ , where the $X_v$ are independent and identically distributed random variables that are distributed as $\text{Bin} (n,(2C_\gamma)^2 / W_{[n]})$ . The expected value of this sum is bounded by $\frac{5 C_\gamma^2}{d} u(t)$ for large n. Also, $u(s) \leq Z_s/\lambda_{\min}$ , as $Z_s = (\xi, \overline{u}_{s}) = \sum_{i} \lambda_i u_i(s) \geq \lambda_{\min} \sum_i u_i(s)$ . So the expectation is at most $\frac{5 C_\gamma^2}{\lambda_{\min} d} Z_s$ . The claim follows from a standard Chernoff bound on the binomial distribution (as the sum of binomial is itself binomially distributed).

Let $B_s\,:\!=\, \max \left\{ \frac{10 C_\gamma^2}{\lambda_{\min} d} Z_s ,\log^6 n \right\}$ .

On the event $\mathcal{D}_s$ , the total degree of the vertices in $\widehat{\mathsf{U}} (s)$ into the set $\widehat{\mathsf{C}}_{i,<r-1} (s)$ bounds the number of vertices that enter into the set $\widehat{\mathsf{C}}_{i,r-1}$ . Hence, on the event $\mathcal{D}_s$ , we have

$$\hat{c}_{i, r-1}(s+1) \leq\hat{c}_{i,r-1}(s) + B_s.$$

Furthermore, for large n,

$$u(s+1) \frac{4 C_\gamma^2}{W_{[n]}}\hat{c}_{i,<r-1} (s+1) \leq u(s+1) \frac{4 C_\gamma^2}{W_{[n]}} n \leq u(s+1) \frac{5 C_\gamma^2}{dn}n = u(s+1) \frac{5 C_\gamma^2}{d}\leq Z_{s+1} \frac{5 C_\gamma^2}{\lambda_{\min} d}.$$

Also, on $\mathcal{E}_s$ we have $Z_{s+1} \leq \beta_1 Z_s$ , for some constant $\beta_1 >0$ , if

$$\frac{10 C_\gamma^2}{\lambda_{\min} d} Z_s \geq \log^6 n;$$

otherwise, since $\rho_s$ is uniformly bounded by some constant over all $s>0$ , we have $Z_{s+1}\leq \beta_2 \log^6 n$ for some constant $\beta_2 >0$ . Therefore, on $\mathcal{D}_s \cap \mathcal{E}_s$ we have

\begin{eqnarray}\sum_{i=1}^{p_\ell} \frac{W_i^2}{W_{[n]}} a_i ( s +1) &\leq& \sum_{i=1}^{p_\ell} \frac{W_i^2}{W_{[n]}} \left( \hat{c}_{i, r-1}( s ) + B_s + Z_{s+1} \frac{5 C_\gamma^2}{\lambda_{\min} d}\right) \nonumber \\& \leq&\sum_{i=1}^{p_\ell} \frac{W_i^2}{W_{[n]}} \hat{c}_{i, r-1}( s ) + \beta \frac{B_s}{n} + \beta^{\prime} \frac{Z_{s+1}}{n} \nonumber \\&\leq & \rho_{s} + \beta \frac{B_s}{n} + \beta^{\prime} \frac{Z_{s+1}}{n}, \nonumber\end{eqnarray}

for some constants $\beta, \beta^{\prime}>0$ and any n. Furthermore, for some other constant $\beta^{\prime\prime}>0$ ,

$$B_s \leq \beta^{\prime\prime} (Z_s + \log^6 n ). $$

Therefore, for some $\gamma > 0$ , we finally obtain

(62) \begin{equation} \rho_{s+1} \leq \rho_s +\frac{1}{n} \left( \gamma (Z_s + Z_{s+1}) + \beta^{\prime\prime} \log^6 n\right) .\end{equation}

Let $\lambda_n = 1 + \frac{1}{\kappa^{\prime}_0 \log^2 n}$ and $T_0 = 2 \lceil \log_{1/\tau} n\rceil$ . We use induction to show that for every $\delta >0$ there exists $\varepsilon>0$ such that if $Z_0/n < \varepsilon$ , then for all $s\leq T_0$

(63) \begin{equation} \rho_s \leq \rho_0 + \gamma \frac{Z_0}{n} \left(2 \sum_{k=0}^{s-1} (\rho_0 +\delta)^k \lambda_n^k +(\rho_0 +\delta)^s \lambda_n^s\right) + (4 \gamma \gamma^{\prime} + \beta^{\prime\prime}) \frac{\log^6 n}{n} \sum_{k=1}^{s-1} k + 2 \gamma \gamma^{\prime} \frac{\log^6 n}{n} s.\end{equation}

Now, observe that for n sufficiently large $(\rho_0 +\delta) \lambda_n < \rho^{\prime}_0 <1 $ . From this inequality, we deduce that for every $s \leq T_0$ , we have

(64) \begin{eqnarray}\rho_s &\leq& \rho_0 + \frac{2\gamma Z_0}{n} \sum_{k=0}^\infty {\rho^{\prime}}_0^k + O\left( \frac{\log^8 n}{n}\right)=\rho_0 + \frac{2\gamma Z_0}{n}\,\frac{1}{1-\rho^{\prime}_0} + O\left( \frac{\log^8 n}{n}\right)\nonumber \\ &\stackrel{Z_0/n < \varepsilon}{\leq}& \rho_0 + 2\gamma \varepsilon\,\frac{1}{1-\rho^{\prime}_0} + O\left( \frac{\log^8 n}{n}\right) < \rho_0+\delta < 1, \end{eqnarray}

provided that $\varepsilon>0$ is small enough.

By (61), on the event $\cap_{s^{\prime}=1}^{T_0} \{ \mathcal{E}_{s^{\prime}} \cap \mathcal{D}_{s^{\prime}} \}$ , for any $s < T_0$ we have

$$Z_s \leq \rho_s Z_{s-1} \lambda_n + \gamma^{\prime} \log^6 n$$

for some constant $\gamma^{\prime} >0$ . Repeating this, we get

\begin{eqnarray}Z_s &\leq& \rho_{s-1} \rho_{s-2} Z_{s-2} \lambda_n^2 +\gamma^{\prime} (\lambda_n + 1) \log^6 n \nonumber \\& & \vdots \nonumber \\&\leq & Z_0 \lambda_n^s \prod_{i=1}^{s-1} \rho_{s-i} + \gamma^{\prime} \log^6 n \sum_{i=0}^{s-1} \lambda_n^i \nonumber \\&\leq&Z_0 \lambda_n^s\prod_{i=0}^{s-1} \rho_{s-i} + 2s \gamma^{\prime} \log^6 n, \nonumber\end{eqnarray}

where in the last inequality we used $\lambda_n^{i} \leq 2$ for n sufficiently large, uniformly over $i\leq T_0$ . By the inductive hypothesis, $\rho_{s-i} \leq \rho_0 + \delta$ for all $i\leq s$ . We thus deduce that

(65) \begin{equation} Z_s \leq Z_0 (\rho_0 +\delta )^{s} \lambda_n^s + 2s \gamma^{\prime} \log^6 n.\end{equation}

Substituting (63) into (62) and using (65), we obtain

\begin{eqnarray*}\rho_{s+1} &\leq& \rho_0 +\frac{\gamma Z_0}{n} \left(2 \sum_{k=0}^{s-1} (\rho_0 +\delta)^k \lambda_n^k +(\rho_0 +\delta)^s \lambda_n^s\right) + (4\gamma \gamma^{\prime} + \beta^{\prime\prime}) \frac{\log^6 n}{n} \sum_{k=1}^{s-1} k \\& & + 2 \gamma \gamma^{\prime} \frac{\log^6 n}{n} s + \beta^{\prime\prime} \frac{\log^6 n}{n} \\&&+\frac{1}{n} \gamma \left(Z_0 (\rho_0 +\delta )^{s} \lambda_n^s + 2s \gamma^{\prime} \log^6 n+Z_0 (\rho_0 +\delta )^{s+1} \lambda_n^{s+1} + 2(s+1) \gamma^{\prime} \log^6 n \right) \\&\leq& \rho_0 +\frac{\gamma Z_0}{n} \left(2 \sum_{k=0}^{s} (\rho_0 +\delta)^k \lambda_n^k +(\rho_0 +\delta)^{s+1} \lambda_n^{s+1}\right) + (4 \gamma \gamma^{\prime} + \beta^{\prime\prime}) \frac{\log^6 n}{n}\sum_{k=1}^{s} k \\& & + 2 \gamma \gamma^{\prime} \frac{\log^6 n}{n} (s+1),\end{eqnarray*}

where in the last inequality we used that

$$\beta^{\prime\prime} \frac{\log^6 n}{n} \leq \beta^{\prime\prime} \frac{\log^6 n}{n}s.$$

Set $\tau = \rho_0 +\delta$ and recall that $T_0 = 2 \lceil \log_{1/\tau} n\rceil$ . Claims 11 and 13 imply that

(66) \begin{equation} \mathbb{P} \left[\cap_{s\leq T_0} \{\mathcal{E}_s \cap \mathcal{D}_s \}\right] = 1 -{O(\log n/n^2)}.\end{equation}

For any $S \in \mathbb{N}$ , we let $\mathcal{S}_S = \cap_{s\leq S} \{\mathcal{E}_s \cap \mathcal{D}_s \}$ and note that if $S < S^{\prime}$ , then $\mathcal{S}_{S^{\prime}} \subset \mathcal{S}_S$ .

Using the tower property of the conditional expectation, we write

\begin{equation*}\mathbb{E} \left( Z_{T_0}\right) = \mathbb{E} \left( \mathbb{E} \left( Z_{T_0} \mid \mathcal{H}_{T_0-1}\right)\right) = \mathbb{E} \left( \mathbb{E} \left( Z_{T_0} \mid \mathcal{H}_{T_0-1}\right) \big(\textbf{1}_{\mathcal{S}_{T_0-1}} + \textbf{1}_{\mathcal{S}_{T_0-1}^c} \big)\right). \end{equation*}

But $Z_{T_0} = O(n)$ , whereby

$$ \mathbb{E} \left( \mathbb{E} \left( Z_{T_0} \mid \mathcal{H}_{T_0-1}\right) \textbf{1}_{\mathcal{S}_{T_0-1}^c}\right) = O(n)\mathbb{E} \left( \textbf{1}_{\mathcal{S}_{T_0-1}^c}\right) = {O(\log n/n)}.$$

Therefore,

\begin{eqnarray*} \mathbb{E} \left( Z_{T_0}\right) &\leq&\mathbb{E} \left( \mathbb{E} \left( Z_{T_0} \mid \mathcal{H}_{T_0-1}\right) \textbf{1}_{\mathcal{S}_{T_0-1}} \right) + {O(\log n/n)} \\&\stackrel{(64)}{\leq}& \mathbb{E} \left( (\rho_0 +\delta) Z_{T_0-1}\right) + {O(\log n /n)}.\end{eqnarray*}

Repeating this, we get

(67) \begin{equation} \mathbb{E} \left( Z_{T_0}\right) \leq (\rho_0 +\delta)^{T_0} \mathbb{E} \left( Z_0\right) +{ O(T_0 \log n /n)} \stackrel{\mathbb{E} \left( Z_0\right) = O(n)}{\leq} O(1/n + T_0/n) = o(1).\end{equation}

Therefore, $\mathbb{P} \left[\widehat{\mathsf{U}} (T_0) \not = \varnothing\right] = o(1)$ .