2. II.

We show that on these binomial probabilities the Chernoff bound may be
applied.

  3. III.

We apply the Chernoff bound to achieve an upper-bound, and we show that this
upper-bound converges to zero with the rate we require.

##### Step I.

Intersecting with $\mathcal{V}_{ts}$ yields

$\mathbb{P}(A_{n}^{+}(t,s)<\Lambda_{n}(t,s))\leq\mathbb{P}(\\{A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{ts})+\mathbb{P}(\neg\mathcal{V}_{ts}).$

Applying Lemma 4.4 shows that

$\mathbb{P}(A_{n}^{+}(t,s)<\Lambda_{n}(t,s))\leq\mathbb{P}(\\{A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{ts})+2\exp(-\log(n)^{2}/2).$

Thus, the lemma is true when the leftover probability converges to zero with a
faster rate than $\exp(-\log(n)^{2}/2)$. We will now apply the law of total
probability on this leftover probability, conditioning on the value of $N_{t}$
and $N_{s}$, to find

$\mathbb{P}(\\{A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{ts})=\mathbb{E}[\mathbb{P}(\\{A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{ts}\;|\;N_{t},N_{s})].$
(32)

For the remainder of the proof we will focus on
$\mathbb{P}(\\{A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{ts}\;|\;N_{t},N_{s})$.
Note this probability is zero when $N_{t}$ and $N_{s}$ are such that
$\mathcal{V}_{ts}$ does not hold. If $\mathcal{V}_{ts}$ does hold we can
remove the condition, and rewrite the probability as

$\mathbb{P}(A_{n}^{+}(t,s)-\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]<\Lambda_{n}(t,s)-\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]\;|\;N_{t},N_{s}).$

Since under the conditioning $A_{n}^{+}(t,s)$ is a binomial random variable,
we know that
$\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]=\kappa^{+}_{n}(t,s)N_{t}N_{s}/n$.
Thus, by setting
$\theta(t,s)=\Lambda_{n}(t,s)-\kappa^{+}_{n}(t,s)N_{t}N_{s}/n$ we find that
the probability we seek to control equals

$\mathbb{P}(A_{n}^{+}(t,s)-\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]<\theta(t,s)\;|\;N_{t},N_{s}).$
(33)

##### Step II.

To apply the Chernoff bound (i.e., Theorem 2.21 in [15]) we need to show that
$\theta(t,s)$ is negative. First we bound

$\theta(t,s)=\lfloor
nq_{t}q_{s}\kappa(t,s)\rfloor-\frac{\kappa^{+}_{n}(t,s)N_{t}N_{s}}{n}\leq
nq_{t}q_{s}\kappa(t,s)-\frac{\kappa(t,s)N_{t}N_{s}}{n}-\frac{Cn^{-1/2+\alpha}N_{t}N_{s}}{n\sqrt{q_{t}q_{s}}}.$

Recall that we only consider settings in which $\mathcal{V}_{ts}$ is
satisfied. Thus, we have that $N_{t}\geq q_{t}n-\log(n)\sqrt{q_{t}n}$ and
$N_{s}\geq q_{s}n-\log(n)\sqrt{q_{s}n}$. Using these facts on the already
existing upper-bound of $\theta(t,s)$ yields the larger upper-bound

$\displaystyle\kappa(t,s)q_{t}q_{s}n-\frac{\kappa(t,s)(q_{t}n-\log(n)\sqrt{q_{t}n})(q_{s}n-\log(n)\sqrt{q_{s}n})}{n}-\frac{C(q_{t}n-\log(n)\sqrt{q_{t}n})(q_{s}n-\log(n)\sqrt{q_{s}n})}{n^{3/2-\alpha}\sqrt{q_{t}q_{s}}},$
$\displaystyle\leq\kappa(t,s)\log(n)n^{1/2}(\sqrt{q_{t}}+\sqrt{q_{s}})\sqrt{q_{t}q_{s}}-Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+C\log(n)n^{\alpha}(\sqrt{q_{t}}+\sqrt{q_{s}}),$
$\displaystyle=\sqrt{q_{t}q_{s}}\left(\kappa(t,s)\log(n)n^{1/2}(\sqrt{q_{t}}+\sqrt{q_{s}})-Cn^{1/2+\alpha}+C\log(n)n^{\alpha}\cdot\frac{\sqrt{q_{t}}+\sqrt{q_{s}}}{\sqrt{q_{t}q_{s}}}\right).$
(34)

In the final inequality we have removed all additional negative terms, and
noted that the term $\kappa(t,s)q_{t}q_{s}n$ cancels out. We now deal with the
two remaining positive terms and show they are dominated by the negative term.
We first deal with the last positive term. Since we have assumed $t,s\leq
u_{n}^{\uparrow}(\tau)$ we have that $q_{t},q_{s}\geq n^{-1+\tau}$. Thus, we
have that

$\frac{\sqrt{q_{t}}+\sqrt{q_{s}}}{\sqrt{q_{t}q_{s}}}\leq
q_{t}^{-1/2}+q_{s}^{-1/2}\leq 2n^{1/2-\tau/2}.$ (35)

If we consider the first positive term, we note from Assumption 2.3 that it
implies $\kappa(t,s)\leq 1/\sqrt{q_{t}q_{s}}$ for $t,s\to\infty$. Hence, for
$n$ large we have through (35) that

$\kappa(t,s)(\sqrt{q_{t}}+\sqrt{q_{s}})\leq\frac{\sqrt{q_{t}}+\sqrt{q_{s}}}{\sqrt{q_{t}q_{s}}}\leq
2n^{1/2-\tau/2}.$

Substituting this, together with (35), back into (34) yields (for
$n\to\infty$)

$\theta(t,s)\leq\sqrt{q_{t}q_{s}}\left(\log(n)n^{1-\tau/2}-Cn^{1/2+\alpha}+C\log(n)n^{\alpha+1/2-\tau/2}\right).$

Recall from Assumption 2.3 that $1/2-\tau/2<\alpha<1/2$. Thus, in particular
we have that $1/2+\alpha>1-\tau/2$, meaning it is the dominant term. In
conclusion, we will have for some $\widehat{C}>0$ that

$\theta(t,s)\leq-\widehat{C}n^{1/2+\alpha}\sqrt{q_{t}q_{s}}.$

This is negative, and hence the Chernoff bound can be applied.

##### Step III.

With the result from Step II we may now apply the Chernoff bound on (33) to
find that

$\mathbb{P}(A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\;|\;N_{t},N_{s})\leq\exp\left(-\frac{\widehat{C}^{2}n^{1+2\alpha}q_{t}q_{s}}{2\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]}\right).$
(36)

We now need to find a useful upper-bound on
$\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]$ in order to show (36) converges
to zero. To do this, we first recall that $\mathcal{V}_{ts}$ is satisfied, and
hence that we can use a bound similar to the one applied in Step II. This
approach shows $\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]$ can be upper-
bounded by

$\frac{\kappa(t,s)(q_{t}n+\log(n)\sqrt{q_{t}n})(q_{s}n+\log(n)\sqrt{q_{s}n})}{n}+\frac{C(q_{t}n+\log(n)\sqrt{q_{t}n})(q_{s}n+\log(n)\sqrt{q_{s}n})}{n^{3/2-\alpha}\sqrt{q_{t}q_{s}}}.$

Since $t,s\leq u_{n}^{\uparrow}$, note that $q_{t}n\geq\log(n)\sqrt{q_{t}n}$
and $q_{s}n\geq\log(n)\sqrt{q_{s}n}$. Recall also that $\kappa(t,s)\leq
1/\sqrt{q_{t}q_{s}}$ if Assumption 2.3 is satisfied. Using these facts, the
previously derived upper-bound becomes

$\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}]\leq
4\sqrt{q_{t},q_{s}}+4Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}\leq
5Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}.$

We will now substitute this upper-bound into (36) and show it still converges
to zero. In this computation we will use the fact that for the stable vertex-
type $t$ (at tolerance $\tau$) it is true that $q_{t}\geq n^{-1+\tau}$. We
find

$\mathbb{P}(A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\;|\;N_{t},N_{s})\leq\exp\left(-\frac{\widehat{C}^{2}n^{1/2+\alpha}\sqrt{q_{t}q_{s}}}{10}\right)\leq\exp\left(-\frac{\widehat{C}^{2}n^{-1/2+\alpha+\tau}}{10}\right).$

By recalling from Assumption 2.3 that $\alpha>1/2-\tau$, we find that there
exists a number $\nu>0$ such that

$\mathbb{P}(A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\;|\;N_{t},N_{s})\leq\exp\left(-n^{\nu}\right).$

Substituting this back into (32) and noting that this bound is uniform in
$N_{t}$ and $N_{s}$ yields

$\mathbb{P}(\\{A_{n}^{+}(t,s)<\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{t,s})=\exp\left(-n^{\nu}\right).$

Hence, for the original target probability from Step I we find

$\mathbb{P}(A_{n}^{+}(t,s)<\Lambda_{n}(t,s))\leq\exp\left(-n^{\nu}\right)+2\exp(-\log(n)^{2}/2)\leq
2\exp(-\log(n)^{2}/2).$

Hence, indeed we find that the statement is true. ∎

###### Proof of Lemma 4.6.

This proof is similar to the proof of Lemma 4.5, hence we will not provide the
same amount of detail as we did in its proof. Instead, we will mainly focus on
the differences. For two stable $t,s\in\mathcal{S}$ we define

$\kappa_{n}^{-}(t,s):=(\kappa(t,s)-Cn^{-1/2+\alpha}/\sqrt{q_{t}q_{s}})\wedge
0.$

By recalling Definition 4.1 we then we have the stochastic bound

$A_{n}(t,s)\preceq
A^{-}_{n}(t,s)\sim\texttt{Bin}(N_{t}N_{s},\kappa_{n}^{-}(t,s)/n),$

allowing us to conclude that

$\mathbb{P}(A_{n}(t,s)>\Lambda_{n}(t,s))\leq\mathbb{P}(A^{-}_{n}(t,s)>\Lambda_{n}(t,s)).$

We will now apply same three steps as in the proof of Lemma 4.5.

##### Step I.

Intersecting with $\mathcal{V}_{ts}$, applying Lemma 4.4 and applying the law
of total probability yields

$\mathbb{P}(A^{-}_{n}(t,s)>\Lambda_{n}(t,s))\leq\mathbb{E}[\mathbb{P}(\\{A_{n}^{-}(t,s)>\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{ts}\;|\;N_{t},N_{s})]+2\exp(-\log(n)^{2}/2).$
(37)

We will now focus on
$\mathbb{P}(\\{A_{n}^{-}(t,s)>\Lambda_{n}(t,s)\\}\cap\mathcal{V}_{ts}\;|\;N_{t},N_{s})$,
and note due to the intersection that we can assume $\mathcal{V}_{ts}$ to be
satisfied. Hence, similar to (33) we can write this probability as

$\mathbb{P}(A_{n}^{-}(t,s)-\mathbb{E}[A_{n}^{-}(t,s)\;|\;N_{t},N_{s}]>\theta(t,s)\;|\;N_{t},N_{s}),$

where
$\theta(t,s)=\Lambda_{n}(t,s)-\mathbb{E}[A_{n}^{-}(t,s)\;|\;N_{t},N_{s}]$. To
apply the Chernoff bound (i.e., Theorem 2.21 in [15]), we need to show this
parameter is positive.

##### Step II.

We first bound $\theta(t,s)$ as

$\theta(t,s)=\lfloor
nq_{t}q_{s}\kappa(t,s)\rfloor-\frac{\kappa^{-}(t,s)N_{t}N_{s}}{n}\geq
nq_{t}q_{s}\kappa(t,s)-\frac{\kappa(t,s)N_{t},N_{s}}{n}+\frac{CN_{t}N_{s}}{n^{3/2-\alpha}\sqrt{q_{t}q_{s}}}-1.$

Now, since $\kappa_{n}^{-}(t,s)>0$ and since we can assume $\mathcal{V}_{ts}$
to be satisfied, we note that we can create a further lower-bound by using
$N_{t}\leq q_{t}n+\log(n)\sqrt{q_{t}n}$ and $N_{s}\leq
q_{s}n+\log(n)\sqrt{q_{s}n}$. Substituting these bounds, and simplifying
yields

$\theta(t,s)\geq\sqrt{q_{t}q_{s}}\left(-\kappa(t,s)\log(n)n^{1/2}(\sqrt{q_{t}}+\sqrt{q_{s}})-\log(n)^{2}+Cn^{1/2+\alpha}-\frac{1}{\sqrt{q_{t}q_{s}}}\right).$

Here, we have removed additional positive terms. We now want the sole positive
term to dominate. We have already covered domination over the first negative
term in the proof of Lemma 4.5. The argument is given after (35). We also
trivially see that the positive term dominates the second negative term (the
logarithm). To see domination over the third negative term, we use the fact
that $t$ and $s$ are stable at tolerance $\tau$ to conclude
$1/\sqrt{q_{t}q_{s}}\leq n^{1-\tau}$. By recalling from Assumption 2.3 that
$\alpha>1/2-\tau/2$ we find that $n^{1/2+\alpha}>n^{1-\tau/2}$, which
dominates $n^{1-\tau}$. Hence, indeed we see there exists a constant
$\widehat{C}>0$ such that

$\theta(t,s)\geq\widehat{C}n^{1/2+\alpha}\sqrt{q_{t}q_{s}}.$

This is the positivity we required.

##### Step III.

Applying the Chernoff bound shows

$\mathbb{P}(A_{n}^{-}(t,s)>\Lambda_{n}(t,s)\;|\;N_{t},N_{s})\leq\exp\left(-\frac{\widehat{C}^{2}n^{1+2\alpha}q_{i}q_{j}}{2\mathbb{E}[A_{n}^{-}(t,s)\;|\;N_{t},N_{s}]}\right).$

We will now upper-bound the expectation inside the exponential function.
Recall the definition of $A^{+}_{n}(t,s)$ in the proof of Lemma 4.5 and note
that

$\mathbb{E}[A_{n}^{-}(t,s)\;|\;N_{t},N_{s}]=\frac{\kappa^{-}_{n}(t,s)N_{t}N_{s}}{n}\leq\frac{\kappa^{+}_{n}(t,s)N_{t}N_{s}}{n}=\mathbb{E}[A_{n}^{+}(t,s)\;|\;N_{t},N_{s}].$

Substituting this into the Chernoff bound we just obtained unveils the bound
in (36). From here, repeating the arguments of Step III in the proof of Lemma
4.5 shows there is a $\nu>0$ such that

$\mathbb{P}(A_{n}^{-}(t,s)>\Lambda_{n}(t,s)\;|\;N_{t},N_{s})\leq\exp\left(-n^{\nu}\right).$

Substituting this back into (37) yields the desired result. ∎

###### Proof of Lemma 4.7.

We will only show the increasing case, since the proof for the decreasing case
is similar. Suppose $\mathcal{Q}_{n}$ is increasing. We couple
$\texttt{ARD}_{n}(T,\Lambda_{n})$ and
$\texttt{ARD}_{n}(T,\Lambda_{n}^{\prime})$ using the following procedure:

  1. 1.

Generate the types of each vertex.

  2. 2.

First, for each pair of types $t,s\in\mathcal{S}$ choose $\Lambda_{n}(t,s)$
vertex pairs where the first vertex has type $t$ and the second $s$ uniformly
at random from all possible pairs without replacement. This is the realisation
of $\texttt{ARD}_{n}(T,\Lambda_{n})$.

  3. 3.

Then, for each pair of types $t,s\in\mathcal{S}$ choose
$\Lambda^{\prime}_{n}(t,s)-\Lambda_{n}(t,s)\geq 0$ of the remaining vertex
pairs where the first has type $t$ and the second $s$ uniformly at random
without replacement. This provides the realisation of
$\texttt{ARD}_{n}(T,\Lambda_{n}^{\prime})$.

Since $\Lambda^{\prime}_{n}(t,s)-\Lambda_{n}(t,s)\geq 0$ we can see that step
2 and 3 in the above procedure are equivalent to choosing
$\Lambda^{\prime}_{n}(t,s)$ pairs of vertices where the first has type $t$ and
the second $s$ uniformly at random without replacement. This is what is needed
in Step 2 and 3 of $\texttt{ARD}_{n}(T,\Lambda_{n}^{\prime})$ (cf. Section
2.2). Under this coupling we also have that
$\texttt{ARD}_{n}(T,\Lambda_{n})\subset\texttt{ARD}_{n}(T,\Lambda_{n}^{\prime})$.
Thus, by virtue of $\mathcal{Q}_{n}$ being an increasing event, we have that
$\texttt{ARD}_{n}(T,\Lambda_{n})\in\mathcal{Q}_{n}$ implies
$\texttt{ARD}_{n}(T,\Lambda_{n}^{\prime})\in\mathcal{Q}_{n}$, letting us
conclude that
$\mathbb{P}(\texttt{ARD}_{n}(T,\Lambda_{n})\in\mathcal{Q}_{n})\leq\mathbb{P}(\texttt{ARD}_{n}(T,\Lambda_{n}^{\prime})\in\mathcal{Q}_{n})$.
∎

###  5.3 Proofs of lemmas for Theorem 3.7

###### Proof of Lemma 4.9.

Set $\lambda^{\downarrow}:=\inf_{i}\\{\lambda_{i}:\lambda_{i}>0\\}$ and
similarly $\varrho^{\downarrow}:=\inf_{j}\\{\varrho_{j}:\varrho_{j}>0\\}$.
From Assumption 3.5 we have that
$\lambda^{\downarrow},\varrho^{\downarrow}>0$. Substituting these into (7)
gives us the upper bound

$\kappa(t,s)\leq\frac{\mu}{\lambda^{\downarrow}\varrho^{\downarrow}}\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}p_{ij}I(t,i)J(s,j).$

Finally, by noting that $I$ and $J$ are indicators, and that $(p_{ij})_{ij}$
is a probability mass function, we find an upper-bound that is uniform in $t$
and $s$, proving the claim.

$\kappa(t,s)\leq\frac{\mu}{\lambda^{\downarrow}\varrho^{\downarrow}}\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}p_{ij}=\frac{\mu}{\lambda^{\downarrow}\varrho^{\downarrow}}.$

∎

###### Proof of Lemma 4.11.

Fix an arbitrary number $r\in(0,\delta)$. Since
$\mathbb{E}[T^{\delta}]<\infty$ we have that $q_{t}<t^{-1-\delta}$ (for all
$t$ sufficiently large), implying that

$q_{t}^{(1+r)/(1+\delta)}<t^{-1-r}.$ (38)

We will now split up the desired probability as

$\mathbb{P}(T>u_{n}^{\uparrow}(\tau))=\sum_{t=u_{n}^{\uparrow}}^{\infty}q_{t}=\sum_{t=u_{n}^{\uparrow}}^{\infty}q_{t}^{(\delta-r)/(1+\delta)}q_{t}^{(1+r)/(1+\delta)}.$

From Definition 2.2 we have that $q_{t}<n^{-1+\tau}$. Using this fact yields

$\mathbb{P}(T>u_{n}^{\uparrow}(\tau))=\sum_{t=u_{n}^{\uparrow}}^{\infty}q_{t}^{(\delta-r)/(1+\delta)}q_{t}^{(1+r)/(1+\delta)}\leq
n^{(\tau-1)(\delta-r)/(1+\delta)}\sum_{t=u_{n}^{\uparrow}}^{\infty}q_{t}^{(1+r)/(1+\delta)}.$

Using (38) in the remaining sum yields the desired result (by noticing that
the leftover sum converges).

$\mathbb{P}(T>u_{n}^{\uparrow}(\tau))\leq
n^{(\tau-1)(\delta-r)/(1+\delta)}\sum_{t=1}^{\infty}q_{t}^{(1+r)/(1+\delta)}\leq
n^{(\tau-1)(\delta-r)/(1+\delta)}\sum_{t=1}^{\infty}\frac{1}{t^{1+r}}=\widehat{C}_{r}\cdot
n^{\frac{(\tau-1)(\delta-r)}{1+\delta}}.$

∎

###### Proof of Lemma 4.12.

Fix a constant $\nu<\tau$. First, apply the union bound to find that

$\mathbb{P}\left(\bigcup_{t=1}^{u_{n}^{\uparrow}(\tau)}\left\\{S_{t}>n^{1-\nu}\right\\}\right)\leq\sum_{t=1}^{u_{n}^{\uparrow}}\mathbb{P}(S_{t}>n^{1-\nu}).$
(39)

Now, conditioning on $\mathcal{V}_{tt}$ (cf. Definition 4.3) and applying
Lemma 4.4 shows that

$\mathbb{P}(S_{t}>n^{1-\nu})\leq\mathbb{P}(\\{S_{t}>n^{1-\nu}\\}\cap\mathcal{V}_{tt})+2\exp\left(-\log(n)^{2}/2\right).$
(40)

Now, we apply the law of total probability on the remaining probability
condition on the number of vertices with type $t$. We find
$\mathbb{P}(S_{t}>n^{1-\nu})=\mathbb{E}[\mathbb{P}(\\{S_{t}>n^{1-\nu}\\}\cap\mathcal{V}_{tt}\;|\;N_{t})]$.
Using this, we note that there will be $N_{t}^{2}$ pairs of vertices with type
$t$ between which an arc can be placed and $N_{t}$ of these will create a
self-loop. Thus, for each arc the probability that it creates a self-loop
within type $t$ is upper bounded by $N_{t}/N_{t}^{2}=1/N_{t}$. Thus, we have
that $S_{t}\preceq\texttt{Bin}(\lfloor\mu n\rfloor,1/N_{t})$.

Furthermore, note that $\mathcal{V}_{tt}$ either happens or not based on the
value of $N_{t}$. Specifically, it stipulates that $N_{t}\geq
q_{t}n-\log(n)\sqrt{q_{t}n}$. This means we can further stochastically bound

$S_{t}\preceq\texttt{Bin}\left(\lfloor\mu
n\rfloor,\frac{1}{q_{t}n-\log(n)\sqrt{q_{t}n}}\right)=:B_{t}.$

Altogether, these arguments show that

$\mathbb{E}[\mathbb{P}(\\{S_{t}>n^{1-\nu}\\}\cap\mathcal{V}_{tt}\;|\;N_{t})]\leq\mathbb{P}(B_{t}>n^{1-\nu})\leq\mathbb{P}(|B_{t}-\mathbb{E}[B_{t}]|>n^{1-\nu}-\mathbb{E}[B_{t}]).$

We now seek to apply the Chernoff bound on this binomial probability. For
this, we show that $n^{1-\nu}-\mathbb{E}[B_{t}]>0$. A straightforward
calculation first yields

$n^{1-\nu}-\mathbb{E}[B_{t}]=n^{1-\nu}-\frac{\lfloor\mu
n\rfloor}{q_{t}-\log(n)\sqrt{q_{t}n}}\geq n^{1-\nu}-\frac{\mu
n}{q_{t}-\log(n)\sqrt{q_{t}n}}.$

Now, note that $t\leq u_{n}^{\uparrow}$ which implies that $q_{t}\geq
n^{-1+\tau}$, resulting in the observation that for $n$ large
$q_{t}n>2\log(n)\sqrt{q_{t}n}$. Thus, this shows us that

$n^{1-\nu}-\mathbb{E}[B_{t}]\geq n^{1-\nu}-\frac{2\mu}{q_{t}}\geq
n^{1-\nu}-2\mu n^{1-\tau}.$

Now, since we have chosen $\nu<\tau$ we indeed find that
$n^{1-\nu}-\mathbb{E}[B_{t}]>0$. Moreover, if we apply the Chernoff bound,
then the choice $\nu<\tau$ even ensures there exists a constant
$\widehat{C}>0$ such that

$\mathbb{P}(|B_{t}-\mathbb{E}[B_{t}]|>n^{1-\nu}-\mathbb{E}[B_{t}])\leq\exp\left(-\widehat{C}n^{1-\nu}\right).$

Substituting this together with (40) into (39) yields

$\mathbb{P}(S_{t}>n^{1-\nu})\leq
u_{n}^{\uparrow}\exp\left(-\widehat{C}n^{1-\nu}\right)+2u_{n}^{\uparrow}\exp\left(-\log(n)^{2}/2\right).$

By noting from Lemma 4.2 that $u_{n}^{\uparrow}$ is polynomial, we see that
both terms in this sum decay super-polynomially to zero, verifying the
statement of the lemma. ∎

###### Proof of Lemma 4.13.

The proof is very similar to the proof of Lemma 4.12, so we will mainly
highlight differences. Fix a number $\nu<2\tau-1$. We first apply the union
bound and intersect with $\mathcal{V}_{ts}$ (cf. Definition 2.2) to find
through Lemma 4.4 for any large number $p$ that

$\mathbb{P}\left(\bigcup_{t=1}^{u_{n}^{\uparrow}}\bigcup_{s=1}^{u_{n}^{\uparrow}}\\{M_{ts}>n^{1-\nu}\\}\right)\leq\sum_{t=1}^{u_{n}^{\uparrow}}\sum_{s=1}^{u_{n}^{\uparrow}}\mathbb{P}(\\{M_{ts}>n^{1-\nu}\\}\cap\mathcal{V}_{ts})+2(u_{n}^{\uparrow})^{2}\exp\left(-\log(n)^{2}/2\right).$
(41)

We now use the law of total probability to condition on the outcomes of both
$N_{t}$ and $N_{s}$. If we know these values, then in our model the worst-case
scenario for preventing multi-arcs would be the situation that $\mu n-1$ arcs
have already been placed between unique vertex-pairs with type $t$ and $s$,
respectively. So, the probability for a new arc to form a multi-arc from a
vertex with type $t$ to a vertex with type $s$ would be bounded by $\frac{\mu
n}{N_{t}N_{s}}$. Once again $\mathcal{V}_{ts}$ stipulates that $N_{t}\geq
q_{t}n-\log(n)\sqrt{q_{t}n}$ and $N_{s}\geq q_{s}n-\log(n)\sqrt{q_{s}n}$.
Thus, together with the previously derived multi-arc probability upper-bound,
we may conclude that

$M_{ts}\preceq\texttt{Bin}\left(\lfloor\mu n\rfloor,\frac{\mu
n}{N_{t}N_{s}}\right)\preceq\texttt{Bin}\left(\lfloor\mu n\rfloor,\frac{\mu
n}{(q_{t}n-\log(n)\sqrt{q_{t}n})(q_{s}n-\log(n)\sqrt{q_{s}n})}\right)=:B_{ts}.$

Hence, we find that

$\displaystyle\mathbb{E}[\mathbb{P}(\\{M_{ts}>n^{1-\nu}\\}\cap\mathcal{V}_{ts})\;|\;N_{t},N_{s}]$
$\displaystyle\leq\mathbb{P}(|B_{ts}-\mathbb{E}[B_{ts}]|>n^{1-\nu}-\mathbb{E}[B_{ts}]).$

We now show that $B_{ts}-\mathbb{E}[B_{ts}]>0$. Recall from the proof of Lemma
4.12 that $q_{t}n\geq\sqrt{q_{t}n}$ and $q_{s}n\geq\sqrt{q_{s}n}$ when
$t,s\leq u_{n}^{\uparrow}$. Moreover, we also have that $q_{t},q_{s}\geq
n^{-1+\tau}$. Hence, we may conclude for $n$ large that

$n^{1-\nu}-\mathbb{E}[B_{ts}]\geq
n^{1-\nu}-\frac{\mu^{2}n^{2}}{(q_{t}n-\log(n)\sqrt{q_{t}n})(q_{s}n-\log(n)\sqrt{q_{s}n})}\geq
n^{1-\nu}-\frac{2\mu}{q_{t}q_{s}}\geq n^{1-\nu}-2\mu n^{1-(2\tau-1)}.$

Now, since we have assumed that $\nu<2\tau-1$ we indeed find that
$n^{1-\nu}-\mathbb{E}[B_{ts}]>0$. When we apply the Chernoff bound, the
inequality $\nu<2\tau-1$ specifically shows that there exists a
$\widehat{C}>0$ such that

$\mathbb{P}(|B_{ts}-\mathbb{E}[B_{ts}]|>n^{1-\nu}-\mathbb{E}[B_{ts}])\leq\exp\left(-\widehat{C}n^{1-\nu}\right).$

Substituting this back into (41) shows

$\mathbb{P}\left(\bigcup_{t=1}^{u_{n}^{\uparrow}}\bigcup_{s=1}^{u_{n}^{\uparrow}}\\{M_{ts}>n^{1-\nu}\\}\right)\leq(u_{n}^{\uparrow})^{2}\exp\left(-\widehat{C}n^{1-\nu}\right)+2(u_{n}^{\uparrow})^{2}\exp\left(-\log(n)^{2}/2\right).$

Like at the end of the proof of Lemma 4.12, the statement is true due to the
fact that $u_{n}^{\uparrow}$ is polynomial in size (cf. Lemma 4.2). ∎

###### Proof of Lemma 4.15.

Let $C_{a}$ denote the colour assigned to arc $a\in[\lfloor\mu n\rfloor]$, and
denote by $(N_{k})_{k\in\mathcal{S}}$ the sequence that records for each
vertex-type the amount of vertices of said type. Finally, set a dummy upper-
bound (cf. Definition 2.2)

$M_{n}:=u_{n}^{\uparrow}\left(1-\frac{2+\varepsilon}{2(1+\varepsilon)}\right).$

This dummy value serves to ensure that $N_{k}$ concentrates for as many
vertex-types simultaneously as possible. Note from step 3–5 in the generation
algorithm for $\texttt{CCI}_{n,\mu}$ that

$\mathbb{P}\left(\mathcal{A}_{ts}^{(a)}\;\Bigg{|}\;\bigcap_{k=1}^{M_{n}}\bigcap_{k^{\prime}=1}^{M_{n}}\mathcal{V}_{kk^{\prime}},\mathcal{V}_{ts},C_{a}=(i,j),(N_{k})_{k\in\mathcal{S}}\right)=\frac{N_{t}N_{s}I(t,i)J(s,j)}{\left(\sum_{k\in\mathcal{S}}N_{k}I(k,i)\right)\left(\sum_{k^{\prime}\in\mathcal{S}}N_{k^{\prime}}J(k^{\prime},j)\right)},$
(42)

Where $\mathcal{V}_{ts}$ is the event from Definition 4.3. Now, since the
intersection of the $\mathcal{V}_{kk^{\prime}}$ events and $\mathcal{V}_{ts}$
occurs, we have for all types $k\leq M_{n}$ and $k\in\\{t,s\\}$ that

$nq_{k}-\log(n)\sqrt{nq_{k}}\leq N_{k}\leq nq_{k}+\log(n)\sqrt{nq_{k}}.$ (43)

In essence, the rest of the proof consists of using (43) to find bounds on
(42) independent of $(N_{k})_{k\in\mathcal{S}}$, and then use the law of total
probability on these bounds to achieve the desired result. More precisely, we
shall derive the following upper and lower bound:

$\frac{N_{t}N_{s}I(t,i)J(s,j)}{\left(\sum_{k\in\mathcal{S}}N_{k}I(k,i)\right)\left(\sum_{k^{\prime}\in\mathcal{S}}N_{k^{\prime}}J(k^{\prime},j)\right)}\leq\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}+\tilde{C}^{\uparrow}\log(n)n^{-\frac{\tau}{2}},$
(44)

and

$\frac{N_{t}N_{s}I(t,i)J(s,j)}{\left(\sum_{k\in\mathcal{S}}N_{k}I(k,i)\right)\left(\sum_{k^{\prime}\in\mathcal{S}}N_{k^{\prime}}J(k^{\prime},j)\right)}\geq\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}-\tilde{C}^{\downarrow}\log(n)n^{-\frac{\tau}{2}},$
(45)

for some constants $\tilde{C}^{\uparrow}$ and $\tilde{C}^{\downarrow}$. We
first finish the proof using these bounds. We use the law of total probability
to write

$\mathbb{P}(\mathcal{A}^{(a)}_{ts})=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}p_{ij}\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j)).$
(46)

Now, we condition on the intersection of $\mathcal{V}_{kk^{\prime}}$ events
and $\mathcal{V}_{ts}$ to find that

$\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle=\mathbb{P}\left(\mathcal{A}^{(a)}_{ts}\;\Bigg{|}\;C_{a}=(i,j),\bigcap_{k=1}^{M_{n}}\bigcap_{k^{\prime}=1}^{M_{n}}\mathcal{V}_{kk^{\prime}},\mathcal{V}_{ts}\right)\mathbb{P}\left(\bigcap_{k=1}^{M_{n}}\bigcap_{k^{\prime}=1}^{M_{n}}\mathcal{V}_{kk^{\prime}},\mathcal{V}_{ts}\;\Bigg{|}\;C_{a}=(i,j)\right),$
$\displaystyle+\mathbb{P}\left(\mathcal{A}^{(a)}_{ts}\;\Bigg{|}\;C_{a}=(i,j),\bigcup_{k=1}^{M_{n}}\bigcup_{k^{\prime}=1}^{M_{n}}\neg\mathcal{V}_{kk^{\prime}}\cup\neg\mathcal{V}_{ts}\right)\mathbb{P}\left(\bigcup_{k=1}^{M_{n}}\bigcup_{k^{\prime}=1}^{M_{n}}\neg\mathcal{V}_{kk^{\prime}}\cup\neg\mathcal{V}_{ts}\;\Bigg{|}\;C_{a}=(i,j)\right).$

By noting from Step 1 and 2 from the $\texttt{CCI}_{n,\mu}$ generation
algorithm that all $\mathcal{V}_{kk^{\prime}}$ and $C_{a}$ are independent
this reduces into

$\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle=\mathbb{P}\left(\mathcal{A}^{(a)}_{ts}\;\Bigg{|}\;C_{a}=(i,j),\bigcap_{k=1}^{M_{n}}\bigcap_{k^{\prime}=1}^{M_{n}}\mathcal{V}_{kk^{\prime}},\mathcal{V}_{ts}\right)\mathbb{P}\left(\bigcap_{k=1}^{M_{n}}\bigcap_{k^{\prime}=1}^{M_{n}}\mathcal{V}_{kk^{\prime}},\mathcal{V}_{ts}\right),$
(47)
$\displaystyle+\mathbb{P}\left(\mathcal{A}^{(a)}_{ts}\;\Bigg{|}\;C_{a}=(i,j),\bigcup_{k=1}^{M_{n}}\bigcup_{k^{\prime}=1}^{M_{n}}\neg\mathcal{V}_{kk^{\prime}}\cup\neg\mathcal{V}_{ts}\right)\mathbb{P}\left(\bigcup_{k=1}^{M_{n}}\bigcup_{k^{\prime}=1}^{M_{n}}\neg\mathcal{V}_{kk^{\prime}}\cup\neg\mathcal{V}_{ts}\right).$

Now we use $(N_{k})_{k\in\mathcal{S}}$-independent bounds (44) and (45) to
create upper- and lower-bounds of (47). Specifically, it shows that

$\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle\leq\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}+\tilde{C}^{\uparrow}\log(n)n^{-\frac{\tau}{2}}+\mathbb{P}\left(\bigcup_{k=1}^{M_{n}}\bigcup_{k^{\prime}=1}^{M_{n}}\neg\mathcal{V}_{kk^{\prime}}\cup\neg\mathcal{V}_{ts}\right),\text{
and}$ $\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle\geq\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}-\tilde{C}^{\downarrow}\log(n)n^{-\frac{\tau}{2}}-\mathbb{P}\left(\bigcup_{k=1}^{M_{n}}\bigcup_{k^{\prime}=1}^{M_{n}}\neg\mathcal{V}_{kk^{\prime}}\cup\neg\mathcal{V}_{ts}\right).$

We use the union bound on the $\mathcal{V}_{kk^{\prime}}$-terms and use Lemma
4.4 to create further upper- and lower-bounds given by

$\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle\leq\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}+\tilde{C}^{\uparrow}\log(n)n^{-\frac{\tau}{2}}+2(M_{n}^{2}+1)\exp\left(-\log(n)^{2}/2\right),\text{
and}$ $\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle\geq\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}-\tilde{C}^{\downarrow}\log(n)n^{-\frac{\tau}{2}}-2(M_{n}^{2}+1)\exp\left(-\log(n)^{2}/2\right).$

Using Lemma 4.2 to conclude that $M_{n}\leq n$, we find that the final terms
are not dominant. Substituting these bounds back into (46) yields

$\frac{q_{t}q_{s}\kappa(t,s)}{\mu}-\widehat{C}\log(n)n^{-\frac{\tau}{2}}\leq\mathbb{P}(\mathcal{A}^{(a)}_{ts})\leq\frac{q_{t}q_{s}\kappa(t,s)}{\mu}+\widehat{C}\log(n)n^{-\frac{\tau}{2}},$

for some $\widehat{C}>0$. Together, these two bounds indeed show that

$\left|\mathbb{P}(\mathcal{A}^{(a)}_{ts})-\frac{q_{t}q_{s}\kappa(t,s)}{\mu}\right|\leq\widehat{C}\log(n)n^{-\frac{\tau}{2}},$

which proves the main result. What is left now is to establish the upper and
lower bound (44) and (45).

##### The upper bound (44).

Define the indicator

$\hat{I}_{k}:=\mathbbm{1}\\{q_{k}n-\log(n)\sqrt{nq_{k}}\geq 0\\}.$

Substituting the upper-bound of (43) in the numerator of (42), and
substituting the lower bound of (43) in the denominator of (42) yields the
upper-bound of (42) given by

$\frac{(q_{t}n+\log(n)\sqrt{q_{t}n})(q_{s}n+\log(n)\sqrt{q_{s}n})I(i,t)J(j,s)}{\left(\sum_{k\in\mathcal{S}}[q_{k}n-\log(n)\sqrt{q_{k}n}]I(i,k)\hat{I}_{k}\right)\left(\sum_{k^{\prime}\in\mathcal{S}}[q_{k^{\prime}}n-\log(n)\sqrt{q_{k^{\prime}}n}]J(j,k^{\prime})\hat{I}_{k^{\prime}}\right)}.$

Here, the inclusion of the indicators $\hat{I}_{k}$ is possible in the
denominator, since we know $N_{k}\geq 0$ for all $k\in\mathcal{S}$. Now, we
will extend this upper bound by only considering the first $M_{n}$ terms in
the sum. Note for these terms that $\hat{I}_{k}=1$ (cf. Definition 2.2). Thus,
we find the further upper-bound

$\frac{(q_{t}n+\log(n)\sqrt{q_{t}n})(q_{s}n+\log(n)\sqrt{q_{s}n})I(i,t)J(j,s)}{\left(\sum_{k=1}^{M_{n}}[q_{k}n-\log(n)\sqrt{q_{k}n}]I(i,k)\right)\left(\sum_{k^{\prime}=1}^{M_{n}}[q_{k^{\prime}}n-\log(n)\sqrt{q_{k^{\prime}}n}]J(j,k^{\prime})\right)}.$

Next, we expand the products in the upper-bound and remove the additional
positive term from the denominator to derive a further upper-bound. It is
given by

$\frac{(q_{t}q_{s}n^{2}+(\sqrt{q_{t}}+\sqrt{q_{s}})n\log(n)\sqrt{q_{t}q_{s}n}+n\log(n)^{2}\sqrt{q_{t}q_{s}})I(i,t)J(j,s)}{\sum_{k=1}^{M_{n}}\sum_{k^{\prime}=1}^{M_{n}}q_{k}q_{k^{\prime}}n^{2}I(i,k)J(j,k^{\prime})-\sum_{k=1}^{M_{n}}\sum_{k^{\prime}=1}^{M_{n}}n\log(n)\sqrt{q_{k}q_{k^{\prime}}n}(\sqrt{q_{k}}+\sqrt{q_{k^{\prime}}})}.$

Now, we further bound the negative term in the denominator to attain an error
sum that only depends on $\sqrt{q_{k}q_{k^{\prime}}}$. We find

$\frac{(q_{t}q_{s}n^{2}+(\sqrt{q_{t}}+\sqrt{q_{s}})n\log(n)\sqrt{q_{t}q_{s}n}+n\log(n)^{2}\sqrt{q_{t}q_{s}})I(i,t)J(j,s)}{\sum_{k=1}^{M_{n}}\sum_{k^{\prime}=1}^{M_{n}}q_{k}q_{k^{\prime}}n^{2}I(i,k)J(j,k^{\prime})-n\log(n)\sqrt{n}\sum_{k=1}^{M_{n}}\sqrt{q_{k}}\sum_{k^{\prime}=1}^{M_{n}}\sqrt{q_{k^{\prime}}}}.$
(48)

Since $\mathbb{E}[T^{1+\varepsilon}]<\infty$ for some $\varepsilon>0$ (cf.
Assumption 3.5), it holds that $q_{k}\leq 1/k^{2+\varepsilon}$ for $k$ large.
Thus, we have that $\sum_{k=1}^{\infty}\sqrt{q_{k}}<\infty$. Using this in
(48) we find there exists a constant $\widehat{C}^{\prime}>0$ such that it is
upper-bounded by

$\frac{(q_{t}q_{s}n^{2}+(\sqrt{q_{t}}+\sqrt{q_{s}})n\log(n)\sqrt{q_{t}q_{s}n}+n\log(n)^{2}\sqrt{q_{t}q_{s}})I(i,t)J(j,s)}{\sum_{k=1}^{M_{n}}\sum_{k^{\prime}=1}^{M_{n}}q_{k}q_{k^{\prime}}n^{2}I(i,k)J(j,k^{\prime})-\widehat{C}^{\prime}\cdot
n\log(n)\sqrt{n}}.$ (49)

Note that the double sum in (49) is close to $\lambda_{i}\varrho_{j}$ (cf.
(6a) and (6b)). We will now make these parameters visible in the denominator
by adding and subtracting the remainders of the sum. We find for any
$r\in(0,1+\varepsilon)$ (cf. Assumption 3.5) and some corresponding
$\widehat{C}_{r}>0$ that

$\displaystyle\sum_{k=1}^{M_{n}}\sum_{k^{\prime}=1}^{M_{n}}q_{k}q_{k^{\prime}}n^{2}I(i,k)J(j,k^{\prime})$
$\displaystyle\geq
n^{2}\lambda_{i}\varrho_{j}-\sum_{k=1}^{\infty}\sum_{k^{\prime}=M_{n}+1}^{\infty}q_{k}q_{k^{\prime}}n^{2}-\sum_{k=u_{n}^{\uparrow}+1}^{\infty}\sum_{k^{\prime}=1}^{\infty}q_{k}q_{k^{\prime}}n^{2},$
$\displaystyle\geq n^{2}\lambda_{i}\varrho_{j}-2n^{2}\mathbb{P}(T>M_{n}),$
$\displaystyle\geq n^{2}\left(\lambda_{i}\varrho_{j}-2\widehat{C}_{r}\cdot
n^{-\frac{1}{2}+\frac{r}{2(1+\varepsilon)}}\right).$

We used Lemma 4.11 in the final line of this string of inequalities.
Substituting this back into (49) yields

$\frac{(q_{t}q_{s}n^{2}+(\sqrt{q_{t}}+\sqrt{q_{s}})n\log(n)\sqrt{q_{t}q_{s}n}+n\log(n)^{2}\sqrt{q_{t}q_{s}})I(i,t)J(j,s)}{n^{2}\left(\lambda_{i}\varrho_{j}-2\widehat{C}_{r}\cdot
n^{-\frac{1}{2}+\frac{r}{2(1+\varepsilon)}}-\widehat{C}^{\prime}\cdot\log(n)n^{-\frac{1}{2}}\right)}.$

Next, we divide everything through by $n^{2}$ and extract the factor
$q_{t}q_{s}I(i,t)J(j,s)/(\lambda_{i}\varrho_{j})$ to find the following upper-
bound

$\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}\cdot\frac{1+(\sqrt{q_{t}}+\sqrt{q_{s}})n^{-1/2}\log(n)/\sqrt{q_{t}q_{s}}+n^{-1}\log(n)^{2}/\sqrt{q_{t}q_{s}}}{1-\widehat{C}_{1}\cdot
n^{-\frac{1}{2}+\frac{r}{2(1+\varepsilon)}}-\widehat{C}_{2}\cdot\log(n)n^{-\frac{1}{2}}}.$
(50)

Here,
$\widehat{C}_{1}=2\widehat{C}_{r}/(\lambda^{\downarrow}\varrho^{\downarrow})$
and
$\widehat{C}_{2}=\widehat{C}^{\prime}/(\lambda^{\downarrow}\varrho^{\downarrow})$
with $\lambda^{\downarrow}:=\inf_{i}\\{\lambda_{i}:\lambda_{i}>0\\}$ and
$\varrho^{\downarrow}:=\inf_{j}\\{\varrho_{j}:\varrho_{j}>0\\}$. We recall
that $\lambda^{\downarrow},\varrho^{\downarrow}>0$ due to Assumption 3.5. By
noting that all the $n$-dependent terms in the denominator (and numerator,
since $\tau>0$) of (50) converge to zero, we can use the Taylor expansion of
this error-fraction to conclude there exists a constant $\tilde{C}>0$ such
that it is bounded by

$1+\tilde{C}\left(\frac{\log(n)}{\sqrt{n}}\left(\frac{1}{\sqrt{q_{t}}}+\frac{1}{\sqrt{q_{s}}}\right)+\frac{\log(n)^{2}}{n\sqrt{q_{t}q_{s}}}+n^{-\frac{1}{2}+\frac{r}{2(1+\varepsilon)}}+\log(n)n^{-\frac{1}{2}}\right).$

Now, recall that $t,s\leq u_{n}^{\uparrow}(\tau)$ and hence that
$q_{t},q_{s}\geq n^{-1+\tau}$. Thus to remove $t$ and $s$ dependence we
further bound this expression by

$1+\tilde{C}\left(2\log(n)n^{-\frac{\tau}{2}}+\log(n)^{2}n^{-\tau}+n^{-\frac{1}{2}+\frac{r}{2(1+\varepsilon)}}+\log(n)n^{-\frac{1}{2}}\right).$

From this expression we note that only the first term can be dominant if we
choose $r$ sufficiently close to zero. Thus, we find that there exists a
constant $\tilde{C}^{\uparrow}>0$ such that (49) is bounded from above by

$\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}+\tilde{C}^{\uparrow}\log(n)n^{-\frac{\tau}{2}},$

which proves (44).

##### The lower bound (45).

The proof is similar to the upper bound. The biggest difference is the way we
bound the denominator in (42) using (43). For this we first note
$\sum_{k=1}^{\infty}N_{k}=n.$ Thus, we can write

$\sum_{k=M_{n}+1}^{\infty}N_{k}I(i,k)\leq\sum_{k=M_{n}+1}^{\infty}N_{k}=n-\sum_{k=1}^{M_{n}}N_{k}=\sum_{k=1}^{\infty}q_{k}n-\sum_{k=1}^{M_{n}}N_{k}.$

Now, using the lower bound in (43) we can conclude that

$\displaystyle\sum_{k=M_{n}+1}^{\infty}N_{k}I(i,k)$
$\displaystyle\leq\sum_{k=1}^{\infty}q_{k}n-\sum_{k=1}^{M_{n}}\left[q_{k}n-\log(n)\sqrt{q_{k}n}\right]=\sum_{k=1}^{\infty}q_{k}n+\log(n)\sqrt{n}\sum_{k=1}^{n}\sqrt{q_{k}}-\sum_{k=1}^{M_{n}}q_{k}n,$
$\displaystyle=\sum_{k=M_{n}+1}^{\infty}q_{k}n+\log(n)\sqrt{n}\sum_{k=1}^{n}\sqrt{q_{k}}=\mathbb{P}(T>M_{n})n+\widehat{C}^{\prime}\cdot\log(n)\sqrt{n}.$

Similarly, using the upper bound in (43) we have that

$\sum_{k=1}^{M_{n}}N_{k}I(i,k)\leq\sum_{k=1}^{M_{n}}q_{k}I(i,k)n+\widehat{C}^{\prime}\cdot\log(n)\sqrt{n}.$

Now, using these bounds in the denominator of (42) and using the lower-bound
of (43) yields the following lower-bound

$\frac{(q_{t}n-\log(n)\sqrt{nq_{t}})(q_{s}n-\log(n)\sqrt{nq_{s}})I(i,t)J(j,s)}{\left(\sum_{k=1}^{M_{n}}q_{k}nI(i,k)+2\widehat{C}^{\prime}\log(n)\sqrt{n}+n\mathbb{P}(T>M_{n})\right)\left(\sum_{k^{\prime}=1}^{M_{n}}q_{k^{\prime}}nJ(i,k^{\prime})+2\widehat{C}^{\prime}\log(n)\sqrt{n}+n\mathbb{P}(T>M_{n})\right)}.$

We expand the factors in this bound, remove the additional positive terms from
the numerator, and only keep the dominant terms in the expansion of the
denominator. This yields a lower-bound of (42) similar to (49) given by

$\frac{(q_{t}q_{s}n^{2}-(\sqrt{q_{t}}+\sqrt{q_{s}})n\log(n)\sqrt{nq_{t}q_{s}})I(i,t)J(j,s)}{\sum_{k=1}^{M_{n}}\sum_{k^{\prime}=1}^{M_{n}}q_{k}q_{k^{\prime}}n^{2}I(i,k)J(j,k^{\prime})+\widetilde{C}^{\prime}\left(n\log(n)\sqrt{n}+n^{2}\mathbb{P}(T>M_{n}))\right)},$

where $\widetilde{C}^{\prime}>0$ is some constant. Now, we create a further
lower bound by running the sum in the denominator up to infinity (revealing
$\lambda_{i}\varrho_{j}$), and applying Lemma 4.11 for the remainder two
terms. We find

$\frac{(q_{t}q_{s}n^{2}-(q_{t}+q_{s})n\log(n)\sqrt{n})I(i,t)J(j,s)}{n^{2}\left(\lambda_{i}\varrho_{j}+\widehat{C}_{r}\cdot
n^{-\frac{1}{2}+\frac{r}{2(1+\varepsilon)}}+\widehat{C}n^{-\frac{1}{2}}\log(n)\right)}.$

Now, we extract $q_{t}q_{s}I(i,t)J(j,s)/(\lambda_{i}\varrho_{j})$ from the
fraction to find a lower-bound similar to (50) given by

$\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}\cdot\frac{1-(\sqrt{q_{t}}+\sqrt{q_{s}})n^{-1/2}\log(n)/\sqrt{q_{t}q_{s}}}{1+\widehat{C}_{1}\cdot
n^{-\frac{1}{2}+\frac{r}{2(1+\varepsilon)}}+\widehat{C}_{2}\cdot\log(n)n^{-\frac{1}{2}}},$

where $\widehat{C}_{1},\widehat{C}_{2}>0$. Repeating the same arguments as in
for the upper bound finally yields the desired lower-bound

$\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}-\tilde{C}^{\downarrow}\log(n)n^{-\frac{\tau}{2}},$

for some $\tilde{C}^{\downarrow}>0$ and any $r\in(0,1+\varepsilon)$. ∎

###### Proof of Lemma 4.16.

The approach is similar to the proof of Lemma 4.15. However, this time we only
focus on an upper-bound. First, we set $M_{n}:=u_{n}^{\uparrow}(\nu)$ for some
$\nu$ close to zero, and write similar to (42) that

$\mathbb{P}\left(\mathcal{A}_{ts}^{(a)}\;\Bigg{|}\;\bigcap_{k=1}^{M_{n}}\bigcap_{k^{\prime}=1}^{M_{n}}\mathcal{V}_{kk^{\prime}},\mathcal{V}_{ts},C_{a}=(i,j),(N_{k})_{k\in\mathcal{S}}\right)=\frac{N_{t}N_{s}I(t,i)J(s,j)}{\left(\sum_{k\in\mathcal{S}}N_{k}I(k,i)\right)\left(\sum_{k^{\prime}\in\mathcal{S}}N_{k^{\prime}}J(k^{\prime},j)\right)}.$
(51)

Now, since both the intersection and $\mathcal{V}_{ts}$ occurs, we have that

$\displaystyle nq_{k}-\log(n)\sqrt{q_{k}n}\leq N_{k}\leq
nq_{k}+\log(n)\sqrt{q_{k}n}\enspace$ $\displaystyle\text{for }k\leq
M_{n}\text{ and }k\in\\{t,s\\}.$ (52)

The rest of the proof consists of using (52) to find an upper-bound of (51)
independent of $(N_{k})_{k\in\mathcal{S}}$, and then use the law of total
probability on these bounds to achieve the desired result. We will proceed in
the following steps:

  1. I.

Derive a desirable upper-bound on (51).

  2. II.

Using the law of total probability on the bounds to find the desired result.

##### Step I.

Repeat the argumentation for the upper bound in the proof of Lemma 4.15 until
(50). We find the upper-bound

$\frac{q_{t}q_{s}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}\cdot\frac{1+(q_{t}^{-1/2}+q_{s}^{-1/2})n^{-1/2}\log(n)+q_{t}^{-1/2}q_{s}^{-1/2}n^{-1}\log(n)^{2}}{1-\widehat{C}_{1}\cdot
n^{\frac{(\nu-1)(1+\varepsilon-r)}{2+\varepsilon}}-\widehat{C}_{2}\cdot\log(n)n^{-\frac{1}{2}}}.$

Note we cannot repeat the Taylor expansion argument from the proof of Lemma
4.15 here, since the two $n$-dependent terms in the numerator might diverge as
$n\to\infty$, due to the instability of either $t$ or $s$. Thus, we slightly
rewrite this expression to make the Taylor expansion argument viable again.

$\frac{\sqrt{q_{t}q_{s}}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}\cdot\frac{\sqrt{q_{t}q_{s}}+(\sqrt{q_{t}}+\sqrt{q_{s}})n^{-1/2}\log(n)+n^{-1}\log(n)^{2}}{1-\widehat{C}_{1}\cdot
n^{\frac{(\nu-1)(1+\varepsilon-r)}{2+\varepsilon}}-\widehat{C}_{2}\cdot\log(n)n^{-\frac{1}{2}}}.$

Now we continue repeating the rest of the arguments for the upper bound in the
proof of Lemma 4.15, but keep the error-term multiplicative. This yields for
some $\tilde{C}>0$ and any $r\in(0,1+\varepsilon)$ that

$\frac{\sqrt{q_{t}q_{s}}I(i,t)J(j,s)}{\lambda_{i}\varrho_{j}}\left(\sqrt{q_{t}q_{s}}+\tilde{C}\left(\frac{(\sqrt{q_{t}}+\sqrt{q_{s}})\log(n)}{\sqrt{n}}+\frac{\log(n)^{2}}{n}+n^{\frac{(\nu-1)(1+\varepsilon-r)}{2+\varepsilon}}+\frac{\log(n)}{\sqrt{n}}\right)\right).$

Due to Assumption 3.5 we can bound $1/(\lambda_{i}\varrho_{j})$ by a constant.
Hence, if we take $\nu$ and $r$ close enough to zero, then there exists a
constant $\widehat{C}>0$ for which we can bound (51) from above by

$\widehat{C}^{\prime}\sqrt{q_{t}q_{s}}\left(\sqrt{q_{t}q_{s}}+\frac{\log(n)}{\sqrt{n}}\right).$
(53)

##### Step II.

We use the law of total probability to write

$\mathbb{P}(\mathcal{A}^{(a)}_{ts})=\sum_{i=1}^{\infty}\sum_{j=1}^{\infty}p_{ij}\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j)).$
(54)

Now, we condition on the intersection of $\mathcal{V}_{kk^{\prime}}$ events
and $\mathcal{V}_{ts}$ to bound

$\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle\leq\mathbb{P}\left(\mathcal{A}^{(a)}_{ts}\;\Bigg{|}\;C_{a}=(i,j),\bigcap_{k=1}^{u_{n}^{\uparrow}}\bigcap_{k^{\prime}=1}^{u_{n}^{\uparrow}}\mathcal{V}_{kk^{\prime}},\mathcal{V}_{ts}\right)+\sum_{k=1}^{u_{n}^{\uparrow}}\sum_{k^{\prime}=1}^{u_{n}^{\uparrow}}\mathbb{P}(\neg\mathcal{V}_{kk^{\prime}})+\mathbb{P}(\neg\mathcal{V}_{ts}).$

Using the $(N_{k})_{k\in\mathcal{S}}$-independent bound (53) together with
Lemma 4.4 shows there exists a constant $\widehat{C}>0$ such that

$\displaystyle\mathbb{P}(\mathcal{A}^{(a)}_{ts}\;|\;C_{a}=(i,j))$
$\displaystyle\leq\widehat{C}\sqrt{q_{t}q_{s}}\left(\sqrt{q_{t}q_{s}}+\frac{\log(n)}{\sqrt{n}}\right)+2((u_{n}^{\uparrow})^{2}+1)\exp\left(-\log(n)^{2}/2\right).$

Substituting this back into (54) and computing the sum shows the desired
result, since the second term in the upper-bound is super-polynomial (cf.
Lemma 4.2). ∎

###### Proof of Lemma 4.17.

Fix a constant $\alpha>3/8$. We fix two auxiliary constants
$\tau_{1}\in(2/3,2\alpha)$ and $\tau_{2}\in(1/2-\alpha,1/2)$ and set
$\zeta_{n}:=u_{n}^{\uparrow}(\tau_{1})$ and
$\xi_{n}:=u_{n}^{\uparrow}(\tau_{2})$. Using these two constants, we will
apply the union bound and split up the resulting bound on the target
probability as follows:

$\displaystyle\sum_{t=1}^{\zeta_{n}}\sum_{s=1}^{\zeta_{n}}\mathbb{P}\left(\left|\bar{\bar{A}}_{n}(t,s)-\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right|>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}\right)$
$\displaystyle+\sum_{t=\zeta_{n}}^{\xi_{n}}\sum_{s=1}^{\xi_{n}}\mathbb{P}\left(\left|\bar{\bar{A}}_{n}(t,s)-\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right|>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}\right)$
$\displaystyle+\sum_{t=1}^{\xi_{n}}\sum_{s=\zeta_{n}}^{\xi_{n}}\mathbb{P}\left(\left|\bar{\bar{A}}_{n}(t,s)-\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right|>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}\right).$

Our goal is now to show that each of these sums converge to zero in order to
prove the claim. This is what we will do in the rest of the proof.

##### First double sum.

In essence, this computation will consist of an application of the Chernoff
bound together with Lemma 4.15. We will first stochastically bound
$\bar{\bar{A}}_{n}(t,s)$ in terms of binomial distributions. To do this, we
write the probability inside this sum as

$\mathbb{P}\left(\bar{\bar{A}}_{n}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right)+\mathbb{P}\left(\bar{\bar{A}}_{n}(t,s)<\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-
Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}\right).$ (55)

Denote by $\mathcal{A}_{ts}^{(a)}$ the event that arc $a\in[\mu n]$ gets
placed from a vertex with type $t$ to a vertex with type $s$. We note
conditional on $(N_{k})_{k\in\mathcal{S}}$ that

$\bar{\bar{A}}_{n}(t,s)\sim\texttt{Bin}\left(\lfloor\mu
n\rfloor,\mathbb{P}(\mathcal{A}_{ts}^{(a)})\right).$

Thus, using Lemma 4.15 we can stochastically bound this from above and below
for some $\widehat{C}>0$ by

$\underbrace{\texttt{Bin}\left(\lfloor\mu
n\rfloor,\frac{q_{t}q_{s}\kappa(t,s)}{\mu}-\widehat{C}\log(n)n^{-\frac{\tau}{2}}\right)}_{B_{n}^{-}(t,s)}\preceq\bar{\bar{A}}_{n}(t,s)\preceq\underbrace{\texttt{Bin}\left(\lfloor\mu
n\rfloor,\frac{q_{t}q_{s}\kappa(t,s)}{\mu}+\widehat{C}\log(n)n^{-\frac{\tau}{2}}\right)}_{B_{n}^{+}(t,s)},$

where we use $B_{n}^{-}(t,s)$ and $B_{n}^{+}(t,s)$ to denote the random
variables on, respectively, the left and right hand side. Using this in (55)
allows us to bound the terms in the first sum as

$\mathbb{P}\left(B_{n}^{+}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right)+\mathbb{P}\left(B_{n}^{-}(t,s)<\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-
Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}\right).$ (56)

We now apply the Chernoff bound on both these probabilities. We will only work
out the first of the two, since the argument for the second is analogous. Like
for all the previous applications of the Chernoff bound, we first sequentially
bound
$Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-\mathbb{E}[B^{+}_{n}(t,s)]$
from below to show that it is positive. First, a direct calculation of this
expression and using $\lfloor\mu n\rfloor\leq\mu n$ shows that it is bounded
by

$Cn^{\frac{1}{2}+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-\kappa(t,s)q_{t}q_{s}n-\mu\widehat{C}\log(n)n^{1-\frac{\tau_{1}}{2}}\geq
Cn^{\frac{1}{2}+\alpha}\sqrt{q_{t}q_{s}}-1-\mu\widehat{C}\log(n)n^{1-\frac{\tau_{1}}{2}}.$

Using the fact that $t,s\leq\zeta_{n}$ allows us to further lower-bound this
expression by

$Cn^{-\frac{1}{2}+\alpha+\tau_{1}}-1-\mu\widehat{C}\log(n)n^{1-\frac{\tau_{1}}{2}}.$

Note that by our condition on $\alpha$ and $\tau_{1}$ it holds that
$3\tau_{1}+2\alpha>3$, which implies that $\tau_{1}+\alpha-1/2>1-\tau_{1}/2$.
Therefore, the first term in the expression above dominates. Thus, indeed
there exists a $\widetilde{C}>0$ such that for large enough $n$

$Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-\mathbb{E}[B^{+}_{n}(t,s)]\geq\widetilde{C}n^{\alpha+\tau_{1}-\frac{1}{2}}>0.$

We can now apply the Chernoff bound, which shows the following bound for some
constant $C^{-}>0$:

$\mathbb{P}\left(B_{n}^{+}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right)\leq\exp\left(-C^{-}n^{\alpha+\tau_{1}-\frac{1}{2}}\right).$

We repeat the same arguments, and find a similar bound for the probability
involving $B_{n}^{-}(t,s)$ in (56). Then, we substitute both bounds in (55),
revealing a uniform bound for all probabilities in the furst sum. Thus, we see
that there exists a $C^{\pm}>0$ such that the first sum is bounded by

$2\zeta_{n}^{2}\cdot\exp\left(-C^{\pm}n^{\alpha+\tau_{1}-\frac{1}{2}}\right)\to
0,$

by Lemma 4.2.

##### Second and third double sum.

We will only give the argument for the second sum, because the argument for
the third is the same. Similar to (55), we start by noting that each term in
the second sum is equal to

$\mathbb{P}\left(\bar{\bar{A}}_{n}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right)+\mathbb{P}\left(\bar{\bar{A}}_{n}(t,s)<\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-
Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}\right).$

We will proceed to show that the second probability is zero by showing that
$\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}$ is
negative. To do this, we subsequently bound

$\displaystyle\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-
Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}$ $\displaystyle\leq
n^{1/2+\alpha}\sqrt{q_{t}q_{s}}\left(\kappa(t,s)n^{1/2-\alpha}\sqrt{q_{t}q_{s}}-C\right),$
$\displaystyle\leq
n^{1/2+\alpha}\sqrt{q_{t}q_{s}}\left(\kappa^{+}n^{\tau_{1}/2-\alpha}-C\right)\leq
0.$

Here, in the second inequality we have used that either $t$ or $s$ is larger
than $\zeta_{n}$ and that $\kappa$ is bounded (Lemma 4.9). In the final
inequality we used that $\tau_{1}<2\alpha$. Thus, to bound the second (and
third) sum, we only need to bound

$\mathbb{P}\left(\bar{\bar{A}}_{n}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right).$
(57)

Like in the previous step, we again have

$\bar{\bar{A}}_{n}(t,s)\sim\texttt{Bin}\left(\lfloor\mu
n\rfloor,\mathbb{P}(\mathcal{A}_{ts}^{(a)})\right),$

which we can stochastically bound using Lemma 4.16 for some $\widehat{C}>0$
and all fixed $r>0$ as

$\bar{\bar{A}}_{n}(t,s)\preceq\underbrace{\texttt{Bin}\left(\lfloor\mu
n\rfloor,\widehat{C}\sqrt{q_{t}q_{s}}\left(\sqrt{q_{t}q_{s}}+\frac{\log(n)}{\sqrt{n}}\right)+\frac{\widehat{C}}{n^{r}}\right)}_{B_{n}^{+}(t,s)},$

where we now use $B_{n}^{+}(t,s)$ to denote the random variable on the right
hand side. This show we can bound (57) by

$\mathbb{P}\left(B_{n}^{+}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right).$

As always, we seek to apply the Chernoff bound, so we will show that indeed
$\theta_{ts}:=Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-\mathbb{E}[B_{n}^{+}(t,s)]\geq
0$. Substituting the expectation and bounding $\lfloor\mu n\rfloor\leq\mu n$
yields

$\theta_{ts}=Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor-\mu\widehat{C}nq_{t}q_{s}-\mu\widehat{C}\log(n)\sqrt{q_{t}q_{s}n}-\mu\widehat{C}n^{1-r}.$

Since both $t,s\leq\xi_{n}$ we have that the first term in this expression is
larger that $Cn^{-1/2+\alpha+\tau_{2}}$. Hence, by choosing $r$ sufficiently
large in the last term, we see that the first term dominates it. Moreover, we
also see that the first term dominates the fourth. In principle, this means
that the fourth and final term are insignificant. Therefore, we rewrite to
obtain the following lower bound:

$\theta_{ts}\geq
n^{1/2+\alpha}\sqrt{q_{t}q_{s}}\left(C-\mu\widehat{C}n^{1/2-\alpha}\sqrt{q_{t}q_{s}}\right)-\mu\widehat{C}\log(n)\sqrt{q_{t}q_{s}n}-\mu\widehat{C}n^{1-r}.$

Without loss of generality, we know in these sums that $q_{t}\leq
n^{-1+\tau_{1}}$ (otherwise, this would be true for $q_{s}$). Hence, we can
further bound

$\theta_{ts}\geq
n^{1/2+\alpha}\sqrt{q_{t}q_{s}}\left(C-\mu\widehat{C}n^{\tau_{1}/2-\alpha}\right)-\mu\widehat{C}\log(n)\sqrt{q_{t}q_{s}n}-\mu\widehat{C}n^{1-r}.$

Again, since $\tau_{1}<2\alpha$ we know from all previous arguments there
exists a $\widetilde{C}>0$ such that

$\theta_{ts}\geq\widetilde{C}n^{1/2+\alpha}\sqrt{q_{s}q_{t}}>0.$

This means we can apply the Chernoff bound. It shows for some $C^{+}>0$ that

$\mathbb{P}\left(B_{n}^{+}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right)\leq\exp\left(-C^{+}n^{1/2+\alpha}\sqrt{q_{t}q_{s}}\right).$

Since $t,s\leq\xi_{n}$, meaning $q_{t},q_{s}\geq n^{-1+\tau_{2}}$, we can
further bound this as

$\mathbb{P}\left(B_{n}^{+}(t,s)>Cn^{1/2+\alpha}\sqrt{q_{t}q_{s}}+\lfloor\kappa(t,s)q_{t}q_{s}n\rfloor\right)\leq\exp\left(-C^{+}n^{\alpha+\tau_{2}-1/2}\right).$

Since we have assumed that $\alpha>1/2-\tau_{2}$, we have that
$\alpha+\tau_{2}-1/2>0$, showing that (57) converges exponentially to zero.
Thus, for the second (and third) sum we find it is bounded by

$\xi_{n}^{2}\cdot\exp\left(-C^{+}n^{\alpha+\tau_{2}-1/2}\right)\to 0,$

by Lemma 4.2. Since all the sums converge to zero, we also have that the
target probability converges to zero. ∎

##### Acknowledgments.

The research of Mike van Santvoort is funded by the Institute for Complex
Molecular Systems (ICMS) at Eindhoven University of Technology.

## References

  * [1] Emmanuel Abbe.  Community Detection and Stochastic Block Models: Recent Developments.  Journal of Machine Learning Research, 18:1–86, 2018.
  * [2] Erick Armingol, Adam Officer, Olivier Harismendy, and Nathan E. Lewis.  Deciphering cell–cell interactions and communication from gene expression.  Nature Reviews Genetics, 22(2):71–88, 2 2021.
  * [3] Frank Ball and David Sirl.  Evaluation of vaccination strategies for SIR epidemics on random networks incorporating household structure.  Journal of Mathematical Biology, 76(1-2):483–530, 1 2018.
  * [4] Béla Bollobás, Svante Janson, and Oliver Riordan.  The phase transition in inhomogeneous random graphs.  Random Structures and Algorithms, 31(1):3–122, 8 2007.
  * [5] Junyu Cao and Mariana Olvera-Cravioto.  On a general class of inhomogeneous random digraphs.  Random Structures & Algorithms, 56(3):722–774, 5 2019.
  * [6] Hyejin Choi, Jianting Sheng, Dingcheng Gao, Fuhai Li, Anna Durrans, Seongho Ryu, Sharrell B. Lee, Navneet Narula, Shahin Rafii, Olivier Elemento, Nasser K. Altorki, Stephen T.C. Wong, and Vivek Mittal.  Transcriptome Analysis of Individual Stromal Cell Populations Identifies Stroma-Tumor Crosstalk in Mouse Lung Cancer Model.  Cell Reports, 10(7):1187–1201, 2 2015.
  * [7] Fan Chung and Linyuan Lu.  The volume of the giant component of a random graph with given expected degrees.  SIAM Journal on Discrete Mathematics, 20(2):395–411, 2006.
  * [8] Daniel Dimitrov, Dénes Türei, Martin Garrido-Rodriguez, Paul L. Burmedi, James S. Nagai, Charlotte Boys, Ricardo O. Ramirez Flores, Hyojin Kim, Bence Szalai, Ivan G. Costa, Alberto Valdeolivas, Aurélien Dugourd, and Julio Saez-Rodriguez.  Comparison of methods and resources for cell-cell communication inference from single-cell RNA-Seq data.  Nature Communications, 13(1), 12 2022.
  * [9] Mikhail Drobyshevskiy and Denis Turdakov.  Random graph modeling: A survey of the concepts.  ACM Computing Surveys, 52(6), 12 2019.
  * [10] P. Erdős and A. Rényi.  On random graphs I.  Publicationes Mathematicae Debrecen, 6:290–297, 1959.
  * [11] Santo Fortunato and Darko Hric.  Community detection in networks: A user guide.  Physics Reports, 659:1–44, 11 2016.
  * [12] E.N. Gilbert.  Random graphs.  The Annals of Mathematical Statistics 1, 30:1141–1144, 1959.
  * [13] Roger Guimerà and Marta Sales-Pardo.  Missing and spurious interactions and the reconstruction of complex networks.  Proceedings of the National Academy of Sciences of the United States of America, 106(52):22073–22078, 12 2009.
  * [14] Aric Hagberg and Nathan Lemons.  Fast generation of sparse random kernel graphs.  PLoS ONE, 10(9), 9 2015.
  * [15] Remco van der Hofstad.  Random Graphs and Complex Networks, volume 1.  Cambridge University Press, Cambridge, 2016.
  * [16] Svante Janson, Tomasz Luczak, and Andrzej Rucinnski.  Random graphs.  John Wiley & Sons, New York, 2000.
  * [17] Clement Lee and Darren J. Wilkinson.  A review of stochastic block models and extensions for graph clustering.  Applied Network Science, 4(1), 12 2019.
  * [18] Joel C. Miller and Aric Hagberg.  Efficient Generation of Networks with Given Expected Degrees.  In Alan Frieze, Paul Horn, and Pawel Pralat, editors, Algorithms and Models for the Web Graph, pages 115–126, Atlanta, 2011. Springer.
  * [19] Tiago P. Peixoto.  Bayesian stochastic blockmodeling.  In Patrick Doreian, Vladimir Batagelj, and Anuska Ferligoj, editors, Advances in Network Clustering and Blockmodeling, chapter 11, pages 289–332. John Wiley & Sons, first edition, 12 2019.
  * [20] Natalie Stanley, Thomas Bonacci, Roland Kwitt, Marc Niethammer, and Peter J. Mucha.  Stochastic block models with multiple continuous attributes.  Applied Network Science, 4(1), 12 2019.
  * [21] Robert Tarjan.  Depth-First Search and Linear Graph Algorithms.  SIAM Journal on Computing, 1(2):146–160, 1972.
  * [22] Pim van der Hoorn and Mariana Olvera-Cravioto.  Typical distances in the directed configuration model.  The Annals of Applied Probability, 28(3):1739–1792, 11 2018.
  * [23] Mike van Santvoort, Óscar Lapuente-Santana, Francesca Finotello, Pim van der Hoorn, and Federica Eduati.  Mathematically mapping the network of cells in the tumor microenvironment.  Pre-print, 2023.
  * [24] Jeffrey Scott Vitter.  An Efficient Algorithm for Sequential Random Sampling.  ACM Transactions on Mathematical Software, 13(1):58–67, 1987.
  * [25] Shuxiong Wang, Matthew Karikomi, Adam L. Maclean, and Qing Nie.  Cell lineage and communication network inference via optimization for single-cell transcriptomics.  Nucleic Acids Research, 47(11), 6 2019.
  * [26] Aleksandr Zaitsev, Maksim Chelushkin, Daniiar Dyikanov, Ilya Cheremushkin, Boris Shpak, Krystle Nomie, Vladimir Zyrin, Ekaterina Nuzhdina, Yaroslav Lozinsky, Anastasia Zotova, Sandrine Degryse, Nikita Kotlov, Artur Baisangurov, Vladimir Shatsky, Daria Afenteva, Alexander Kuznetsov, Susan Raju Paul, Diane L. Davies, Patrick M. Reeves, Michael Lanuti, Michael F. Goldberg, Cagdas Tazearslan, Madison Chasse, Iris Wang, Mary Abdou, Sharon M. Aslanian, Samuel Andrewes, James J. Hsieh, Akshaya Ramachandran, Yang Lyu, Ilia Galkin, Viktor Svekolkin, Leandro Cerchietti, Mark C. Poznansky, Ravshan Ataullakhanov, Nathan Fowler, and Alexander Bagaev.  Precise reconstruction of the TME using bulk RNA-seq and a machine learning algorithm trained on artificial transcriptomes.  Cancer Cell, 40(8):879–894, 8 2022.