Maximum degree in WRT with bounded random weights]Fine asymptotics for the maximum degree in weighted recursive trees with bounded random weights

Eslava]Laura Eslava$^\dagger$
$^\dagger$Universidad Nacional Autonoma Mexico, Instituto de investigaciones en matematicas y en sistemas, CDMX, 04510, Mexico
Lodewijks]Bas Lodewijks$^{\dagger\dagger}$
$^{\dagger\dagger}$ Université Jean Monnet, Saint-Etienne, France and  Institut Camille Jordan, Lyon and Saint-Etienne, France
Ortgiese]Marcel Ortgiese$^\star$

$^\star$Department of Mathematical Sciences,
University of Bath,
Claverton Down,
BA2 7AY,
United Kingdom.

A weighted recursive tree is an evolving tree in which vertices are assigned random vertex-weights and new vertices connect to a predecessor with a probability proportional to its weight. Here, we study the maximum degree and near-maximum degrees in weighted recursive trees when the vertex-weights are almost surely bounded and their distribution function satisfies a mild regularity condition near zero.
We are able to specify higher-order corrections to the first order growth of the maximum degree established in prior work. The accuracy of the results depends on the behaviour of the weight distribution near the largest possible value and in certain cases we manage to find the corrections up to random order. Additionally, we describe the tail distribution of the maximum degree, the distribution of the number of vertices attaining the maximum degree, and establish asymptotic normality of the number of vertices with near-maximum degree. Our analysis extends the results proved for random recursive trees (where the weights are constant) to the case of random weights. The main technical result shows that the degrees of several uniformly chosen vertices are asymptotically independent with explicit error corrections.

§ INTRODUCTION

The Weighted Recursive Tree model (WRT), first introduced by Borovkov and Vatutin [4], is a recursive tree process $(T_n,n\in\N)$ and a generalisation of the random recursive tree model. Here we consider a variation, first studied by Hiesmayr and Işlak [11], where the first vertex does not necessarily have weight one. Let $(W_i)_{i\in\N}$ be a sequence of positive vertex-weights. Initialise the process with the tree $T_1$, which consists of the vertex $1$ (which denotes the root) and assign vertex-weight $W_1$ to it. Recursively, at every step $n\geq 2$, we obtain $T_n$ by adding to $T_{n-1}$ the vertex $n$, assigning vertex-weight $W_n$ to it and connecting $n$ to a vertex $i\in[n-1]$, which, conditionally on the vertex-weights $W_1,\ldots, W_{n-1}$, is selected with a probability proportional to $W_i$. In this paper, we consider edges to be directed towards the vertex with the smaller label. We note that allowing every vertex to connect to $m\in\N$ many predecessors, each one selected independently, yields the more general Weighted Recursive Graph model (WRG) introduced in [15]. The focus of this paper is the WRT model in the case when the vertex-weights are almost surely bounded random variables.

Lodewijks and Ortgiese [15] established that, in the case of positive, bounded random vertex-weights, the maximum degree $\Delta_n$ of the WRG model grows logarithmically and that $\Delta_n/\log n\toas 1/\log \theta_m$, where $\theta_m:=1+\E W/m$ with $\E W$ the mean of the vertex-weight distribution and $m\in\N$ the out-degree of each vertex. Note that setting $m=1$ yields the result for the WRT model. In this paper, we improve this result by describing the higher-order asymptotic behaviour of the maximum degree when the vertex-weights are almost surely bounded. In this case we are able to distinguish several classes of vertex-weight distributions for which different higher-order behaviour can be observed.

Beyond the initial work of Borovkov and Vatutin and also Hiesmayr and Işlak studying the height, depth and size of branches of the WRT model, other properties such as the degree distribution, large and maximum degrees, and weighted profile and height of the tree have been studied. Mailler and Uribe Bravo [17], as well as Sénizergues [19] and Sénizergues and Pain [18] study the weighted profile and height of the WRT model. Mailler and Uribe Bravo consider random vertex-weights with particular distributions, whereas Sénizergues and Pain allow for a more general model with both sequences of deterministic as well as random weights.

Iyer [12] and the more general work by Fountoulakis and Iyer [8] study the degree distribution of a large class of evolving weighted random trees, and Lodewijks and Ortgiese [15] study the degree distribution of the WRG model. In both cases, the WRT model is a particular example of the models studied and all results prove the existence of an almost sure limiting degree distribution for the empirical degree distribution.

Finally, Lodewijks and Ortgiese [15] and Lodewijks [14] study the maximum degree and the labels of the maximum degree vertices of the WRG model for a large range of vertex-weight distributions. In particular, a distinction between distributions with unbounded support and bounded support is observed. In the former case the behaviour and size of the label of the maximum degree is mainly controlled by a balance of vertices being old (i.e.  having a small label) and having a large vertex-weight. In the latter case, due to the fact that the vertex-weights are bounded, the behaviour is instead controlled by a balance of vertices being old and having a degree which significantly exceeds their mean degree.

A particular case of the WRT model is the Random Recursive Tree (RRT) model, which is obtained when each vertex-weight equals one almost surely. As a result, techniques used to study the maximum degree in the RRT model can be adapted to analyse the maximum degree in the WRT model. Lodewijks and Ortgiese [15] demonstrate this by adapting the approach of Devroye and Lu [6] for proving the almost sure convergence of the rescaled maximum degree in the Directed Acyclic Graphs model (DAG) (the multigraph case of the RRT model) and using it for the analysis of the maximum degree in the WRG model, as discussed above. Hence, we survey the development of the properties of the maximum degree of the RRT model.

Szymańsky was the first to study the maximum degree of the RRT model and proved its convergence of the mean; $\E{\Delta_n/\log n}\to 1/\log 2$. Later, Devroye and Lu [6] extend this to almost sure convergence and extended this to the DAG model as well. Goh and Schmutz [10] showed that $\Delta_n-\lfloor \log_2 n\rfloor$ converges in distribution along suitable subsequences and identified possible distributions for the limit. Adarrio-Berry and Eslava [1] provide a precise characterisation of the subsequential limiting distribution of rescaled large degrees in terms of a Poisson point process as well as a central limit theorem result for near-maximum degrees (of order $\log_2 n- i_n$ where $i_n\to\infty,i_n=o(\log n)$). Eslava [7] extends this to the joint convergence of the degree and depth of high degree vertices.

In this paper we adapt part of the techniques developed by Adarrio-Berry and Eslava in [1]. They consist of two main components: First, they establish an equivalence between the RRT model and a variation of the Kingman $n$-coalescent and use this to provide a detailed asymptotic description of the tail distribution of the degrees of $k$ vertices selected uniformly at random, for any $k\in\N$. This variation of the Kingman $n$-coalescent is a process which starts with $n$ trees, each consisting of only a single root. Then, at every step $1$ through $n-1$, a pair of roots is selected uniformly at random and independently of this selection, each possibility with probability $1/2$, one of the two roots is connected to the other with a directed edge. This reduces the number of trees by one and, after $n-1$ steps, yields a directed tree. It turns out that this directed tree is equal in law to the random recursive tree. In the $n$-coalescent all $n$ roots in the initialisation are equal in law and the degrees of the vertices are exchangeable. This allows Adarrio-Berry and Eslava to obtain the degree tail distribution with a precise error rate. Second, this precise tail distribution is used to obtain joint factorial moments of the quantities

X^(n)_i   :=|{j∈[n]:_n(j)= ⌊log_2 n⌋+i}|,  i∈,

X^(n)_≥i   :=|{j∈[n]:_n(j)≥⌊log_2 n⌋+i}|,  i∈,
where $\Zm_n(j)$ denotes the in-degree of vertex $j$ in the tree of size $n$. The joint factorial moments of these $X^{(n)}_i,X^{(n)}_i$ are used to identify the limiting distribution of high degrees in the tree. The sub-sequential convergence, as mentioned above, is due to the floor function applied to $\log_2 n$ and the integer-valued in-degrees $\Zm_n(j)$.

For the WRT model, however, it provides no advantage to construct a `weighted' Kingman $n$-coalescent to obtain precise asymptotic expression for the tail distribution of vertex degrees. As pairs of roots in the Kingman $n$-coalescent are selected uniformly at random and hence the roots are equal in law, it is not necessary to keep track of which roots are selected at what step. In a weighted version of the Kingman $n$-coalescent, pairs of roots would have to be selected with probabilities proportional to their weights, so that it is necessary to record which roots are selected at which step. As a result, a weighted Kingman $n$-coalescent is not (more) useful in analysing the tail distribution of vertex degrees.

Instead, we improve results on the convergence of the empirical degree distribution of the WRT model obtained by Iyer [12] and Lodewijks and Ortgiese [15]. We obtain a convergence rate to the limiting degree distribution, the asymptotic empirical degree distribution for degrees $k=k(n)$ which diverge with $n$, as well as asymptotic independence of degrees of vertices selected uniformly at random. We combine this with the joint factorial moments of quantities similar to (<ref>) and use the techniques developed by Adarrio-Berry and Eslava [1] to derive fine asymptotics of the maximum degree in the WRT model.

Notation. Throughout the paper we use the following notation: we let $\N:=\{1,2,\ldots\}$ be the natural numbers, set $\N_0:=\{0,1,\ldots\}$ to include zero and let $[t]:=\{i\in\N: i\leq t\}$ for any $t\geq 1$. For $x\in\R$, we let $\lceil x\rceil:=\inf\{n\in\Z: n\geq x\}$ and $\lfloor x\rfloor:=\sup\{n\in\Z: n\leq x\}$, and for $x\in\R,k\in\N$, let $(x)_k:=x(x-1)(x-2)\cdots(x-(k-1))$ and $(x)^{(k)}:=x(x+1)(x+2)\cdots(x+(k-1))$, and $(x)_0=(x)^{(0)}:=1$. For $x,y \in \R$, we write $x\wedge y := \min \{ x,y\}$ and $x \vee y := \max\{ x, y\}$. Moreover, for sequences $(a_n,b_n)_{n\in\N}$ such that $b_n$ is positive for all $n$ we say that $a_n=o(b_n), a_n\sim b_n, a_n=\mathcal{O}(b_n)$ if $\lim_{n\to\infty}a_n/b_n=0, \lim_{n\to\infty} a_n/b_n=1$ and if there exists a constant $C>0$ such that $|a_n|\leq Cb_n$ for all $n\in\N$, respectively. For random variables $X,(X_n)_{n\in\N},Y$ we denote $X_n\toindis X, X_n\toinp X$ and $X_n\toas X$ for convergence in distribution, probability and almost sure convergence of $X_n$ to $X$, respectively. Also, we write $X_n=o_\mathbb{P}(1)$ if $X_n \toinp 0$ and $X\preceq Y$ if $Y$ stochastically dominates $X$. Finally, we use the conditional probability measure $\Pf{\cdot}:=\mathbb{P}(\,\cdot\, |(\F_i)_{i\in\N})$ and conditional expectation $\Ef{}{\cdot}:=\E{\,\cdot\,|(\F_i)_{i\in\N}}$, where the $(W_i)_{i\in\N}$ are the i.i.d. vertex-weights of the WRT model.

§ DEFINITIONS AND MAIN RESULTS

The weighted recursive tree (WRT) model is a growing random tree model that generalises the random recursive tree (RRT), in which vertices are assigned (random) weights and new vertices connect with existing vertices with a probability proportional to the vertex-weights.

The definition of the WRT model follows the one in [11]:

Let $(\F_i)_{i\geq 1}$ be a sequence of i.i.d. copies of a positive random variable $\F$ such that $\P{\F>0}=1$ and set
We construct the weighted recursive tree as follows:

1) Initialise the tree with a single vertex $1$, denoted as the root, and assign to the root a vertex-weight $\F_1$. Denote this tree by $T_1$.

2) For $n\geq 1$, introduce a new vertex $n+1$ and assign to it the vertex-weight $\F_{n+1}$. Conditionally on $T_n$, connect to some $\inn$ with probability $\F_i/S_n$. Denote the resulting tree by $T_{n+1}$.

We treat $T_n$ as a directed tree, where edges are directed from new vertices towards old vertices.

$(i)$ Note that the edge connection probabilities are invariant under a rescaling of the vertex-weights. In particular, we may without loss of generality assume for vertex-weight distributions with bounded support that $x_0:=\sup\{x\in\R\,|\, \P{\F\leq x}<1\}=1$.

$(ii)$ The model can be adapted to allow for a random out-degree: at every step the newly introduced vertex $n+1$ connects with every vertex $\inn$ independently with a probability equal to $W_i/S_n$. The results presented below still hold for this model definition as well.

Lodewijks and Ortgiese studied certain properties of the Weighted Recursive Graph (WRG) model in [15]. This is a more general version of the WRT model that allows every vertex to connect to $m\in\N$ vertices when introduced, yielding a multigraph when $m>1$. This paper aims to recover and extend some of these results in the tree case ($m=1$) when the vertex-weights are almost surely bounded, i.e. $x_0<\infty$. As stated in Remark <ref>$(i)$, we can set $x_0=1$ without loss of generality. To formulate the results we need to assume that the distribution of the weights is sufficiently regular, allowing us to control their extreme value behaviour. In certain cases it is more convenient to formulate the assumptions in terms of the distribution of the random variable $(1-W)^{-1}$:
[Vertex-weight distribution]
The vertex-weights $W,(W_i)_{i\in\N}$ are i.i.d. strictly positive random variables, which satisfy:

ass:weightsup$($C$1)$ The random variable $W$ takes values in $(0,1]$ and $x_0:=\sup\{x\in \R|\P{W\leq x}<1\}=1$.

There exist $C,\rho>0,x_0\in(0,1)$ such that for all $x\in[0,x_0]$ it holds that  $\P{W \leq x} \leq C x^\rho .$

Furthermore, the vertex-weights satisfy one of the following conditions:

ass:weightatom$($Atom$)$ The vertex weights follow a distribution that has an atom at one, i.e. there exists a $q_0\in(0,1]$ such that $\P{W=1}=q_0$. (Note that $q_0=1$ recovers the RRT model)

ass:weightweibull$($Weibull$)$ The vertex-weights follow a distribution that belongs to the Weibull maximum domain of attraction (MDA). This implies that there exist some $\alpha>1$ and a positive function $\ell$ which is slowly varying at infinity, such that
W≥1-1/x=(1-W)^-1≥x=ℓ(x)x^-(α-1),    x>0.

ass:weightgumbel$($Gumbel$)$ The distribution belongs to the Gumbel maximum domain of attraction (MDA) (and $x_0=1$). This implies that there exist sequences $(a_n,b_n)_{n\in\N}$, such that
where $\Lambda$ is a Gumbel random variable.

Within this class, we further distinguish the following two sub-classes:

There exist $a,c_1,\tau>0$, and $b\in\R$ such that

\[ \hspace{1.5cm}\P{W>1-1/x}=\P{ (1-\F)^{-1} > x} \sim a x^b 	\e^{-( x/c_1)^\tau} \quad \mbox{as } x \rightarrow \infty .\]

There exist $a,c_1>0, b\in\R,$ and $\tau>1$ such that

\[ \hspace{1.5cm}\P{W>1-1/x}=\P{ (1-\F)^{-1} > x} \sim a (\log x)^b 	\e^{- (\log (x)/c_1)^\tau} \quad \mbox{as } x \rightarrow \infty .\]

Condition <ref> is required only for a very specific part of the proof of Proposition <ref>. Though we were unable to omit this assumption, it covers a wide range of vertex-weight distributions. Still, we believe it is a mere technicality that can be overcome.

Throughout, we will write

\[  	\zni := \mbox{ in-degree of vertex } i \mbox{ in } T_n . \]

Working with the in-degree allows us to (in principle) generalise our methods to graphs with random out-degree, as mentioned in Remark <ref>. Obviously, if the out-degree is fixed, we can recover the results for the degree from our results on the $\zni$.

In [15], the following results are obtained for the WRG model: if we let $\theta_m:=1+\E{W}/m$,

p_k(m):=θ_m-1/θ_m-1+W(W/θ_m-1+W)^k,  p_≥k(m):=∑_j=k^∞p_k(m) =(W/θ_m-1+W)^k,
then almost surely for any $k\in\N$ fixed,

lim_n→∞1/n ∑_i=1^n _{=k}=p_k(m)    and     lim_n→∞1/n∑_i=1^n _{≥k}=p_≥k(m),
whenever $W$ follows a distribution with a finite mean. In particular, the above is satisfied for all cases in Assumption <ref>. Moreover, if the vertex-weights are bounded almost surely (without loss of generality $x_0=1$),

In this paper we improve these results when considering the WRT model with almost surely bounded weights. That is, we consider the case $m=1$. For ease of writing, we let
θ:=θ_1=1+W and p_k:=p_k(1),p_≥k:=p_≥k(1).
First, we are able to extend the result in (<ref>) to the case when $k=k(n)$ diverges with $n$ in the sense that the difference between both sides converges to zero in mean, under certain constraints on $k(n)$, and we obtain a convergence rate as well. Combining this result with techniques developed by Addario-Berry and Eslava in [1] for random recursive trees we are then able to identify the higher-order asymptotic behaviour of the maximum degree depending on the cases in Assumption <ref>. Additionally, in certain cases we are able to derive an asymptotic tail distribution for the maximum degree and obtain an asymptotic normality result for the number of vertices with `near-maximal' degrees (in certain cases). These results can be extended to the model with a random out-degree as mentioned in Remark <ref> as well.

Recall that $\theta:=1+\E W$ and define

X^(n)_i   :=|{j∈[n]:_n(j)= ⌊log_θn⌋+i}|,

X^(n)_≥i   :=|{j∈[n]:_n(j)≥⌊log_θn⌋+i}|.
For certain classes of vertex-weight distributions, we can prove the distributional convergence of these quantities along subsequences, as is the case for the RRT model in [1]. This result can be formulated in terms of convergence of point processes. Let $\Z^*:=\Z\cup \{\infty\}$ and endow $\Z^*$ with the metric $d(i,j)=|2^{-i}-2^{-j}|$ and $d(i,\infty)=2^{-i}$ for any $i,j\in\Z$, so that $[i,\infty]$ is a compact set. Following the notation in [5], let $\mathcal M^\#_{\Z^*}$ be the space of boundedly finite measures on $\Z^*$ (which in this case corresponds to  locally finite measures) equipped with the vague topology. If we let $\mathcal P$ be a Poisson point process on $\R$ with intensity measure $\lambda(\d x):=q_0\theta^{-x}\log \theta\, \d x,q_0\in(0,1]$, and define

𝒫^:=∑_x∈𝒫δ_⌊x+⌋,    𝒫^(n):=∑_δ_-⌊log_θn⌋,   and    _n:=log_θn-⌊log_θn⌋,
then $\mathcal P^\eps$ and $\mathcal P^{(n)}$ are random elements in $\mathcal M^\#_{\Z^*}$ and we can provide conditions such that $\mathcal P^{(n_\ell)}$ converges weakly to $\mathcal P^\eps$, for subsequences $(n_\ell)_{\ell\in\N}$ such that $\eps_{n_\ell}\to\eps$ as $\ell\to\infty$. We abuse notation to write $\mathcal P^\eps(i)=\mathcal P^\eps(\{i\})=|\{x\in\mathcal P: \lfloor x+\eps\rfloor =i\}|=|\{x\in\mathcal P: x\in [i-\eps,i+1-\eps)\}|$.
The choice of the metric on $\Z^*$ is convenient since, by Theorem 11.1.VII of [5], weak convergence in $\mathcal M^\#_{\Z^*}$ is equivalent to convergence of finite dimensional distributions, see Definition 11.1.IV of [5]. In particular, the weak convergence of $\cP^{(n_\ell)}$ implies the convergence in distribution of $X_{\ge i}^{(n_l)} = \cP^{(n_\ell)}[i,\infty)$.

We now state our main results, which we split into several theorems based on the cases in Assumption <ref>.

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ that satisfy the <ref> case in Assumption <ref> for some $q_0\in(0,1]$. Fix $\eps\in[0,1]$. Let $(n_\ell)_{\ell\in\N}$ be a positive integer sequence such that $\eps_{n_\ell}\to \eps$ as $\ell\to\infty$. Then $\mathcal P^{(n_\ell)}$ converges weakly in $\mathcal M^\#_{\Z^*}$ to $\mathcal P^\eps$ as $\ell\to \infty$. Equivalently, for any $i<i'\in\Z$, jointly as $\ell\to \infty$,

We note that this result recovers and extends <cit.>, in which an equivalent result is presented which only holds for the random recursive tree, i.e. the particular case of the weighted recursive tree in which $q_0:=\P{W=1}=1$. In Theorem <ref> we allow $q_0\in(0,1)$ as well, under the additional condition <ref>.

When the vertex-weight distribution belongs to the Weibull MDA, we can prove convergence in probability under a deterministic second-order scaling, but are unable to obtain what we conjecture to be a random third-order term similar to the result in Theorem <ref>:

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ that satisfy the <ref> case in Assumption <ref> for some $\alpha>1$. Then,

Finally, when the vertex-weight distribution belongs to the Gumbel MDA, we have similar results compared to the Weibull MDA case in the above theorem. Here we are also able to obtain a deterministic second-order scaling for both the <ref> and <ref> sub-cases, as well as a third- and fourth-order scaling for the <ref> sub-case:

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ that satisfy the <ref> case in Assumption <ref>.

In the <ref> sub-case, let $\gamma:=1/(1+\tau)$. Then,

In the <ref> sub-case,

C_1   :=(logθ)^τ-1c_1^-τ,    C_2:=(logθ)^τ-1τ(τ-1)c_1^-τ,

C_3   :=(log_θ(logθ) (τ-1)logθ-log(c_1^τ(1-θ^-1)/τ))(logθ)^τ-2τc_1^-τ.

We see that only in the <ref> case we are able to obtain the higher-order asymptotics up to random order. This is due to the fact that, in this particular case, the vertices with high degree all have vertex-weight one. In the other classes covered in Theorems <ref> and <ref> vertices with high degrees have a vertex-weight close to one, which causes their degrees to grow slightly slower. This results in the higher-order asymptotics as observed in these theorems.

We are able to obtain more precise results related to the maximum and near-maximum degree vertices in the <ref> case as well, which again recover and extend the results in [1].

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ that satisfy the <ref> case in Assumption <ref> for some $q_0\in(0,1]$ and recall $\eps_n$ from (<ref>). Then, for any integer-valued $i_n=i(n)$ with $i_n+\log_\theta n <(\theta/(\theta-1)) \log n$ and $\liminf_{n\to\infty}i_n>-\infty$,
Moreover, let $\M_n\subseteq [n]$ denote the $($random$)$ set of vertices that attain the maximum degree in $T_n$, fix $\eps\in[0,1]$, and let $(n_\ell)_{\ell\in\N}$ be a positive integer sequence such that $\eps_{n_\ell}\to\eps$ as $\ell\to\infty$. Then, $|\M_{n_\ell}|\toindis M_\eps$, where $M_\eps$ has distribution

M_=k=∑_j∈1/k!(q_0(1-θ^-1)θ^-j+)^k ^-q_0θ^-j+,    k∈.

Finally, we establish an asymptotic normality result for the number of vertices which have `near-maximum' degrees. For a precise definition of `near-maximum', we define sequences $(s_k,r_k)_{k\in\N}$ as

s_k   :=inf{x∈(0,1): W∈(x,1)≤exp(-(1-θ^-1)(1-x)k)},

r_k   :=exp(-(1-θ^-1)(1-s_k)k).
As a result, $r_k$ can be used as the error term in the asymptotic expression of $p_{\geq k}$ (as in (<ref>)) when the weight distribution satisfies the <ref> case (see Theorem <ref>) and is essential in quantifying how much smaller `near-maximum' degrees are relative to the maximum degree of the graph in this case. We note that $r_k$ is decreasing and converges to zero with $k$ (see Lemma <ref>), and that in the definition of $s_k$ and $r_k$ we can allow the index to be continuous rather than just an integer (the proof of Lemma <ref> can be adapted to still hold in this case). We can then formulate the following theorem:

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ that satisfy the <ref> case in Assumption <ref> for some $q_0\in(0,1]$. Then, for an integer-valued $i_n=i(n)\to-\infty$ such that $i_n=o(\log n \wedge |\log r_{\log_\theta n}|)$,

The constraint $i_n=o(\log n\wedge \log r_{\log_\theta n})$ can be simplified by providing more information on the tail of the weight distribution. Only when $W$ has an atom at one and support bounded away from one do we have that $o(\log n\wedge \log r_{\log_\theta n})=o(\log n)$. That is, when there exists an $s\in(0,1)$ such that $\P{W\in(s,1)}=0$. In that case, we can set $s_k= s$ and $r_k= \exp(-(1-\theta^{-1})(1-s)k)$ for all $k$ large, so that
logr_ log_θn= -(1-θ^-1)(1-s)log_θn,
so that indeed $o(\log n\wedge \log r_{\log_\theta n})=o(\log n)$. In all other cases it follows that $s_k\uparrow 1$, so that $\log r_{\log_\theta n}=o(\log n)$ and the constraint simplifies to $i_n=o(\log r_{\log_\theta n})$.

Outline of the paper

In Section <ref> we provide a short overview and intuitive idea of the proofs of Theorems <ref>, <ref>, <ref>, <ref> and <ref>. In Section <ref> we discuss two examples of vertex-weight distributions which satisfy the <ref> and <ref> cases, respectively, for which more precise results can be obtained. We then provide the key concepts and results that are used in the proofs of the main theorems in Section <ref>. We use these results to prove the main theorems in Section <ref>. Finally, in Section <ref> we provide the necessary techniques and results, comparable to what is presented in Section <ref>, to prove the statements regarding the examples of Section <ref>.

§ INTUITIVE IDEA OF (THE PROOF OF) THE MAIN THEOREMS

We provide a short intuitive idea as to why the results stated in Section <ref> hold.

The main elements in obtaining a more precise understanding of the behaviour of the maximum degree of the WRT are the following:

item:i$(i)$ A precise expression of the tail distribution of the in-degree of uniformly at random selected vertices $(v_\ell)_{\ell\in[k]}$, for any $k\in\N$. That is,
_n(v_ℓ)≥m_ℓ for all  ℓ∈[k]=∏_ℓ=1^k p_≥m_ℓ(1+o(n^-β)),
for some $\beta>0$ and where the $m_\ell\in\N$ are such that $m_\ell\leq c \log n$ for some $c\in(0,\theta/(\theta-1))$. This extends (<ref>) in the sense of convergence in mean to $k\in\N$ many uniformly at random selected vertices rather than just one, and allows the $m_\ell$ to grow with $n$ rather than being fixed. Moreover, the error term $1+o(n^{-\beta})$ extends previously known results as well, for which no convergence rate was known.

item:ii$(ii)$ The asymptotic behaviour of $p_{\geq k}$, as defined in (<ref>), as $k\to\infty$ for each case in Assumption <ref>.

Element <ref>, which is proved in Proposition <ref>, allows us to obtain bounds on the probability of the event $\{\max_{\jnn}\znj\geq k_n\}$ for any sequence $k_n\to\infty $ as $n\to\infty$. These probabilities can be expressed in terms of $n p_{\geq k_n}$ (using union bounds and
the second moment method in the form of the Chung-Erdős inequality, as is shown in Lemma <ref>). By <ref> we can then precisely quantify $k_n$ such that these bounds either tend to zero or one, which implies whether $\{\max_{\jnn}\zni\geq k_n\}$ does or does not hold with high probability. This is the main approach for Theorems <ref> and <ref>.

To obtain the random limits described in terms of the Poisson process $\mathcal P^\eps$, as in Theorem <ref>, we use a similar approach as in [1]. Both <ref> and <ref> are still essential, but are now used to obtain factorial moments of the quantities $X^{(n)}_i$ and $X^{(n)}_{\geq i}$, defined in (<ref>), as shown in Proposition <ref>. More specifically, for any $i<i'\in\Z$ and $a_i,\ldots,a_{i'}\in\N_0$, and recalling that $(x)_k:=x(x-1)\ldots (x-(k-1))$,

We stress that the specific form of the right-hand side is due to the underlying assumption in Theorem <ref> that the vertex-weight distribution has an atom at one, as in the <ref> case of Assumption <ref>. The error term can be specified in more detail, but we omit this as it serves no further purpose here. The result essentially follows directly from these estimates by observing that the right-hand side of (<ref>) can be understood as an approximation of the factorial moment of the Poisson random variables $\mathcal P^\eps([i-\eps,i+1-\eps)),\ldots, \mathcal P^\eps([i'-\eps,\infty))$, when $\eps_n$ converges to some $\eps$.

The equality in (<ref>) follows from the fact that $X^{(n)}_i$ and $X^{(n)}_{\geq i}$ can be expressed as sums of indicator random variables of disjoint events, so that their factorial means can be understood via the probabilities in <ref>. Then, again using the asymptotic behaviour of $p_{\geq k}$ (as in <ref>), allows us to obtain the right-hand side of (<ref>).

Finally, Theorems <ref> and <ref> are also a result of (<ref>). This is due to the fact that the events $\{\max_{\jnn}\znj \geq \lfloor\log_\theta n\rfloor +i\}$ can be understood via the events $\{X^{(n)}_{\geq i}>0\}$. Again using ideas similar to ones developed in [1] then allow us to obtain the results.

§ EXAMPLES

In this section we discuss some particular choices of distributions for the vertex-weights for which more precise statements can be made compared to those stated in Section <ref>. The reason we can improve on these more general results is due to a better understanding of the asymptotic behaviour of $p_k$ and $p_{\geq k}$ (see (<ref>)) as $k\to\infty$. As discussed in Section <ref>, to understand the asymptotic behaviour of the (near-)maximum degree(s) up to random order a very precise asymptotic expression for $p_{\geq k}$ is required. Though not possible in general in the <ref> and <ref> cases of Assumption <ref>, certain choices of vertex-weight distributions do allow for a more explicit formulation of $p_{\geq k}$, yielding improved asymptotics. The proofs of the results presented here are deferred to Section <ref>.

[Beta distribution]
We consider a random variable $W$ with a tail distribution

W≥x=∫_x^1 Γ(α+β)/Γ(α)Γ(β)s^α-1(1-s)^β-1 ṣ,     x∈[0,1),
for some $\alpha,\beta>0$. Clearly, $W$ belongs to the <ref> case of Assumption <ref>. Moreover, $W$ satisfies condition <ref> of Assumption <ref>. Since for any $x_0\in(0,1)$ we can bound $(1-s)^{\beta-1}\leq 1\vee (1-x_0)^{\beta-1}$ for all $s\in(0,x_0)$, it follows that for any $x\in[0,x_0]$,
W≤x=∫_0^x Γ(α+β)/Γ(α)Γ(β)s^α-1(1-s)^β-1 ṣ≤(1∨(1-x_0)^β-1)Γ(α+β)/Γ(α+1)Γ(β)x^α,
so that condition <ref> is satisfied with $C=(1\vee (1-x_0)^{\beta-1})\Gamma(\alpha+\beta)/(\Gamma(\alpha+1)\Gamma(\beta))$, the constant $x_0\in(0,1)$ arbitrary, and $\rho=\alpha$.

We set, for $\theta:=1+\E W\in(1,2),$

X^(n)_i   :=|{: =⌊log_θn-βlog_θlog_θn ⌋+i}|,

X^(n)_≥i   :=|{: ≥⌊log_θn-βlog_θlog_θn⌋+i}|,

_n   :=(log_θn-βlog_θlog_θn)-⌊log_θn-βlog_θlog_θn ⌋,

c_α,β,θ   :=Γ(α+β)/Γ(α)(1-θ^-1)^-β.
Then, we can formulate the following results.

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ whose distribution satisfies (<ref>) for some $\alpha,\beta>0$, and recall $\eps_n$ and $c_{\alpha,\beta,\theta}$ from (<ref>). Fix $\eps\in[0,1]$, let $(n_\ell)_{\ell\in\N}$ be an increasing integer sequence such that $\eps_{n_\ell}\to \eps$ as $\ell \to \infty$ and let $\mathcal P$ be a Poisson point process on $\R$ with intensity measure $\lambda(x)=c_{\alpha,\beta,\theta}\theta^{-x}\log \theta\,\d x$. Define
𝒫^:=∑_x∈𝒫δ_⌊x+⌋    and    𝒫^(n):=∑_δ_-⌊log_θn-βlog_θlog_θn ⌋.
Then in $\mathcal M^\#_{\Z^*}$ $($the space of boundedly finite measures on $\Z^*=\Z\cup\{\infty\}$ with the metric defined in Section <ref>$)$, $\mathcal P^{(n_\ell)}$ converges weakly to $\mathcal P^\eps$ as $\ell\to \infty$. Equivalently, for any $i<i'\in\Z$, jointly as $\ell\to \infty$,

We remark that the second-order term $\beta \log_\theta\log_\theta n$ is established in Theorem <ref> as well and that the above theorem recovers this result and extends it to the random third-order term, which is similar to the result in Theorem <ref>.

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ whose distribution satisfies (<ref>) for some $\alpha,\beta>0$, and recall $\eps_n$ and $c_{\alpha,\beta,\theta}$ from (<ref>). Then, for any integer-valued $i_n$ with $i_n= \delta\log_\theta n+o(\log n)$ for some $\delta\in[0,\theta\log\theta/(\theta-1)-1)$ and $\liminf_{n\to\infty}i_n>-\infty$,
ℙ   (max_≥⌊log_θn-βlog_θlog_θn⌋+i_n)=(1-exp(-c_α,β,θ(1+δ)^-βθ^-i_n+_n))(1+o(1)).
Moreover, let $\M_n\subseteq [n]$ denote the (random) set of vertices that attain the maximum degree in $T_n$, fix $\eps\in[0,1]$ and let $(n_\ell)_{\ell\in\N}$ be a positive integer sequence such that $\eps_{n_\ell}\to\eps$ as $\ell\to\infty$. Then, $|\M_{n_\ell}|\toindis M_\eps$, where $M_\eps$ has distribution
M_=k=∑_j∈1/k!(c_α,β,θ(1-θ^-1)θ^-j+)^kexp(-c_α,β,θθ^-j+),    k∈.

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ whose distribution satisfies (<ref>) for some $\alpha,\beta>0$ and recall $\eps_n$ and $c_{\alpha,\beta,\theta}$ from (<ref>). Then, for an integer-valued $i_n\to-\infty$ such that $i_n=o(\log\log n)$,

The three theorems are the analogue of Theorems <ref>, <ref> and <ref>, respectively, where we now consider vertex-weights distributed according to a beta distribution rather than a distribution with an atom at one.

[Fraction of `gamma' random variables]
We consider a random variable $W$ with a tail distribution

W≥x=(1-x)^-b^-x/(c_1(1-x)),    x∈[0,1),
for some $b\in\R,c_1>0$ with $bc_1\leq 1$. The random variable $(1-W)^{-1}$ belongs to the Gumbel maximum domain of attraction, as
(1-W)^-1≥x=W≥1-1/x=^1/c_1x^b^-x/c_1,    x≥1,
so that $W$ belongs to the Gumbel MDA as well by <cit.>, and satisfies the <ref>-<ref> sub-case with $a=\e^{1/c_1},b\in\R,c_1>0$, and $\tau=1$. As a result, $X:=(1-W)^{-1}$ is a `gamma' random variable in the sense that its tail distribution is asymptotically equal to that of a gamma random variable, up to constants. We can then write $W=(X-1)/X$, a fraction of these `gamma' random variables.

Let $f_W$ denote the probability density function of $W$. It follows from (<ref>) that
f_W(x)=(1/c_1 – b(1-x)) (1-x)^-(b+2) ^ - x/ (c_1 (1-x)).
Observe that the requirement $bc_1\leq 1$ ensures that $f_W(x)\geq 0$ for all $x\in[0,1)$. As $\lim_{x\uparrow 1}f_W(x)=0$ and the density is bounded from above in a neighbourhood of the origin, it follows that $f_W(x)\leq C$ for some $C>0$ and all $x\in[0,1)$. As a result, this distribution satisfies condition <ref> of Assumption <ref> with $\rho=1$, $x_0\in(0,1)$ arbitrary, and some sufficiently large $C>0$.

Recall $C_{\theta,\tau,c_1}$ from (<ref>). We set, for $\theta:=1+\E W\in(1,2),$

C:=^c_1^-1(1-θ^-1)/2√(π)c_1^-1/4+b/2(1-θ^-1)^1/4+b/2,    and  c_c_1,b,θ:=Cθ^C_θ,1,c_1^2/2,

X^(n)_i:=   |{: =⌊log_θn-C_θ,1,c_1√(log_θn)+(b/2+1/4) log_θlog_θn ⌋+i}|,

X^(n)_≥i:=   |{: ≥⌊log_θn-C_θ,1,c_1√(log_θn)+(b/2+1/4) log_θlog_θn ⌋+i}|,

_n:=   (log_θn-C_θ,1,c_1√(log_θn)+(b/2+1/4) log_θlog_θn)

-⌊log_θn-C_θ,1,c_1√(log_θn)+(b/2+1/4) log_θlog_θn ⌋.
Then, we can formulate the following results.

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ whose distribution satisfies (<ref>) for some $b\in\R,c_1>0$ such that $bc_1\leq 1$, and recall $C_{\theta,\tau,c_1}$ from (<ref>). Then,

Furthermore, recall $\eps_n$ from (<ref>), fix $\eps\in[0,1]$, and let $(n_\ell)_{\ell\in\N}$ be an increasing integer sequence such that $\eps_{n_\ell}\to \eps$ as $\ell \to \infty$. Let $\mathcal P$ be a Poisson point process on $\R$ with intensity measure $\lambda(x)=c_{c_1,b,\theta}\theta^{-x}\log \theta\, \d x$, where we recall $c_{c_1,b,\theta}$ from (<ref>). Define
𝒫^:=∑_x∈𝒫δ_⌊x+⌋    and   𝒫^(n):=∑_δ_-⌊log_θn-C_θ,1,c_1√(log_θn)+(b/2+1/4) log_θlog_θn ⌋.
Then in $\mathcal M^\#_{\Z^*}$ $($the space of boundedly finite measures on $\Z^*=\Z\cup\{\infty\}$ with the metric defined in Section <ref>$)$, $\mathcal P^{(n_\ell)}$ converges weakly to $\mathcal P^\eps$ as $\ell\to \infty$. Equivalently, for any $i<i'\in\Z$, jointly as $\ell\to \infty$,

We remark that the second-order term in (<ref>) is established in Theorem <ref>, (<ref>), as well. The above theorem recovers this former result and extends it to the third-order rescaling and to the random fourth-order term, which is similar to the result in Theorem <ref>.

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ whose distribution satisfies (<ref>) for some $b\in \R,c_1>0$ such that $bc_1\leq 1$, and recall $C_{\theta,\tau,c_1}$, $c_{c_1,b,\theta}$, and $\eps_n$ from (<ref>), (<ref>), and (<ref>), respectively. Then, for any integer-valued $i_n$ with $i_n= \delta\sqrt{\log_\theta n}+o(\sqrt{\log n})$ for some $\delta\geq 0$ and $\liminf_{n\to\infty}i_n>-\infty$,
ℙ   (max_≥⌊log_θn-C_θ,1,c_1√(log_θn)+(b/2+1/4) log_θlog_θn ⌋+i_n)

Moreover, let $\M_n\subseteq [n]$ denote the $($random$)$ set of vertices that attain the maximum degree in $T_n$, fix $\eps\in[0,1]$ and let $(n_\ell)_{\ell\in\N}$ be a positive integer sequence such that $\eps_{n_\ell}\to\eps$ as $\ell\to\infty$. Then, $|\M_{n_\ell}|\toindis M_\eps$, where $M_\eps$ has distribution
M_=k=∑_j∈1/k!(c_c_1,b,θ(1-θ^-1)θ^-j+)^kexp(-c_c_1,b,θθ^-j+),    k∈.

Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ whose distribution satisfies (<ref>) for some $b\in \R,c_1>0$ such that $bc_1\leq 1$, and recall $c_{c_1,b,\theta}$ and $\eps_n$ from (<ref>) and (<ref>), respectively. Then, for an integer-valued $i_n\to-\infty$ such that $i_n=o(\log\log n)$,

The three theorems are the analogue of Theorems <ref>, <ref> and <ref>, respectively, where we now consider vertex-weights distributed according to a distribution as in (<ref>) rather than a distribution with an atom at one.

In both examples we see that a better understanding of the asymptotic behaviour of the tail of the degree distribution, $(p_{\geq k})_{k\in\N_0}$, allows us to identify the higher-order asymptotic behaviour of the (near-)maximum degree(s). It also shows that a higher-order random limit as in the sense of Theorems <ref> and <ref> is not expressed just by vertex-weights whose distribution has an atom at one, and we conjecture that this result is in fact universal for all vertex-weights distributions with bounded support.

§ DEGREE TAIL DISTRIBUTIONS AND FACTORIAL MOMENTS

In this section we state and prove the key elements required to prove the main results as stated in Section <ref>. We stress that the results presented and proved in this section cover all the classes introduced in Assumption <ref> (in fact, they cover any vertex-weight $W$ that satisfies conditions <ref> and <ref>) and that the distinction between the classes of Assumption <ref> follows in Section <ref>. The intermediate results presented here form the main technical contribution, and their proofs are the main body of the paper.

§.§ Statement of intermediate results and main ideas

As discussed in Section <ref>, to understand the asymptotic behaviour of the maximum degree and near-maximum degrees we require a more precise understanding of the convergence in mean of the empirical degree distribution. To that end, we present the following result:

Let $W$ be a positive random variable that satisfies conditions <ref> and <ref> of Assumption <ref>. Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ which are i.i.d. copies of $W$, fix $k\in\N$, and let $(v_\ell)_{\ell\in[k]}$ be $k$ vertices selected uniformly at random without replacement from $[n]$. For a fixed $c\in (0,\theta/(\theta-1))$, there exist $\beta\geq \beta'>0$ such that uniformly over non-negative integers $m_\ell< c\log n$ with $\ell\in[k]$,

\begin{align}
\P{\Zm_n(v_\ell)=m_\ell,\text{ for all }\ell\in[k]}&= \prod_{\ell=1}^k \E{\frac{\E{W}}{\E{W}+W}\Big(\frac{W}{\E{W}+W}\Big)^{m_\ell}}\big(1+o\big(n^{-\beta}\big)\big),\label{eq:degdist}
\intertext{and}
\P{\Zm_n(v_\ell)\geq m_\ell,\text{ for all }\ell\in[k]}&= \prod_{\ell=1}^k \E{\Big(\frac{W}{\E{W}+W}\Big)^{m_\ell}}\big(1+o\big(n^{-\beta'}\big)\big).	\label{eq:degtail}
\end{align}

$(i)$ In <cit.>, it is proved that the degrees $(\znj)_{\jnn}$ are negative quadrant dependent when considering the random recursive tree model (the WRT with deterministic weights, all equal to $1$). That is, for any $k\in\N$ and any $j_1\neq \ldots \neq j_k\in[n]$ and $m_1,\ldots,m_k\in\N$,
⋂_ℓ=1^k{_n(j_ℓ)≥m_ℓ}≤∏_j=1^k _n(j_ℓ)≥m_ℓ.
This property only holds for the conditional probability measure $\mathbb P_W$ when considering the WRT (or, more generally, the WRG) model, as follows from <cit.>, and can be obtained `asymptotically' for the probability measure $\mathbb P$, as in the proof of <cit.>. Proposition <ref> improves on this by establishing asymptotic independence under the non-conditional probability measure $\mathbb P$ of the degrees of typical vertices, which allows us to extend the results in [15] to more precise asymptotics.

$(ii)$ We note that the result only requires the two main conditions in Assumption <ref> on the behaviour of the vertex-weight distribution close to zero and one. Hence, results for other vertex-weight distributions that do not satisfy any of the particular cases outlined in this assumption can be obtained as well using the methods presented in this paper.

$(iii)$ The result in Proposition <ref> improves on known results, especially those in [9, 12]. In these papers similar techniques are used to prove a weaker result, in which the $m_\ell$ are not allowed to diverge with $n$ and where no convergence rate is provided.

$(iv)$ The constraint $c\in(0,\theta/(\theta-1))$ arises from the following: when $m=c\log n+o(\log n)$, as we shall encounter later in the proof of Lemma <ref>, see Equation (<ref>), for $\eps>0$ small,
1/n ∑_i<n^_n(v_1)≥m≤exp(logn(-(1-)+(c+o(1))(1-1/c(θ-1)+log(1/c(θ-1))))).
We want the contribution of left-hand side, compared to the left-hand side of (<ref>) to be negligible. Hence, it needs to be $o(p_{\geq m})=o(\theta^{-m})$ (recall $p_{\geq m}$ from (<ref>)). We thus have the requirement that

-(1-)+c(1-1/c(θ-1)+log(1/c(θ-1)))>-clogθis satisfied. The inequality in (<ref>) becomes an equality exactly when $c=\theta/(\theta-1)$ and $\eps=0$. Hence the need for $c$ to be strictly smaller than $\theta/(\theta-1)$. Also, a more technical reason is  that certain error terms no longer converge to zero with $n$ when $c\geq \theta/(\theta-1)$. Moreover, we observe that $\frac{1}{\log\theta}< \frac{\theta}{\theta-1}$ when $\theta\in(1,2]$, so that Proposition <ref> covers degrees that extend beyond the value of the maximum degree (see (<ref>)). This is a crucial element of Proposition <ref> and the reason that strong claims regarding the largest degrees in the tree can be proved.

To use this (tail) distribution of $k$ typical vertices $v_1,\ldots,v_k$, a precise expression for the expected values on the right-hand side in Proposition <ref> is required. Recall $p_k$ from (<ref>). The following theorem comes from <cit.>, in which the maximum degree of weighted recursive graphs is studied for a large class of vertex-weight distribution and in which asymptotic expressions of $p_k$ are presented.

Recall that $\theta:=1+\E W$. We consider the different cases with respect to the vertex-weights as in Assumption <ref>, but do not require condition <ref> to hold.

thrm:pkatom$(\mathrm{\mathbf{Atom}})$ Recall that $q_0=\P{W=1}>0$ and recall $r_k$ from (<ref>). Then,

thrm:pkweibull$(\mathrm{\mathbf{Weibull}})$ Recall that $\alpha>1$ is the power-law exponent. Then, for all $k>1/\E W$,

L(k)k^-(α-1) θ^-k≤p_k≤L(k)k^-(α-1)θ^-k,
where $\underline L$ and $\overline L$ are slowly varying at infinity.

$(i)$ If $W$ satisfies the <ref> sub-case with parameter $\tau>0$, set $\gamma:=1/(\tau+1)$. Then,

$(ii)$ If $W$ satisfies the <ref> sub-case with parameter $\tau>1$,

where $K_{\tau,c_1,\theta}:=\tau\log(\e c_1^\tau(1-\theta^{-1})/\tau)$.

Equivalent upper and lower bounds can be obtained for $p_{\geq k}$ as in (<ref>) (with $m=1$), by adjusting the multiplicative constants in front of the asymptotic expressions by a factor $(1-\theta^{-1})^{-1}$ only. This is due to the fact that
Equivalently, the proof of <cit.> can be adapted to work for $p_{\geq k}$ in which case the same asymptotic behaviour is established for $p_{\geq k}$, but with different constants in the front.

We also provide less precise but more general bounds on the degree distribution.

Let $W$ be a positive random variable with $x_0:=\sup\{x>0:\P{W\leq x}<1\}=1$. Then, for any $\xi>0$ and $k$ sufficiently large,

The upper bound on $p_{\geq k}$ directly follows from the fact that $x\mapsto (x/(\theta-1+ x))^k$ is increasing in $x$, so that
For the lower bound, let us take some $\delta\in(0,\xi/(\theta-1+\xi))$ and define

Note that $p_k=\E{f_k(\theta,W)}$. Then, since $f_k(\theta,x)$ is increasing in $x$ on $(0,1]$ for $k$ sufficiently large,
We note that, since $x_0=1$, it holds that $\P{W>1-\delta}>0$ for any $\delta>0$. Now, by the choice of $\delta$, we have $(\theta+\xi)(1-\delta)/(\theta-\delta)>1$, so we can find some $\zeta>0$ sufficiently small so that
f_k(θ,W)(θ+ξ)^k ≥W>1-δθ-1/θ-δ((θ+ξ)(1-δ)/θ-δ)^k≥(1+ζ)^k≥1,
as required.

Recall the definition of $X_i^{(n)},X_{\geq i}^{(n)}$ and $\eps_n$ from (<ref>) and (<ref>), respectively. Proposition <ref> combined with Theorem <ref> then allows us to obtain the following result.

Consider the WRT model as in Definition <ref> with vertex-weights $(W_i)_{\inn}$ that satisfy the <ref> case in Assumption <ref> for some $q_0\in(0,1]$. Recall $r_k$ from (<ref>), recall that $\theta:=1+\E W$, and that $(x)_k:=x(x-1)\cdots (x-(k-1))$ for $x\in\R,k\in\N$, and $(x)_0:=1$. For fixed $K\in\N$ and $c\in(0,\theta/(\theta-1))$, there exists $\beta>0$ such that the following holds. For any integer-valued $i_n$ and $i_n',$ such that $0<i_n+\log_\theta n<i_n'+\log_\theta n< c\log n$ and any $(a_j)_{i_n\le j\le i_n'}$ non-negative integer sequence such that $\sum_{j=i_n}^{i_n'}a_j=K$,
(X^(n)_≥i_n')_a_i_n'∏_k=i_n^i_n'-1(X_k^(n))_a_k=   (q_0θ^-i_n'+_n)^a_i_n'∏_k=i_n^i_n'-1(q_0(1-θ^-1)θ^-k+_n)^a_k

$(i)$ Intuitively, the result of this proposition tells us that the random variables $(X^{(n)}_k)_{k=i_n}^{i_n'-1}$ and $X(n)_{\geq i_n'}$ are, jointly, approximately Poisson distributed, since their factorial moments approximate those of Poisson random variables. This result hence plays an essential role in proving the weak convergence to a Poisson point process in Theorem <ref>.

$(ii)$ Related to Remark <ref>, the error term decays polynomially only if $W$ has an atom at one and support bounded away from one and $\log_\theta n+i_n>\eta \log n$ for some $\eta>0$. That is, when there exists an $s\in(0,1)$ such that $\P{W\in(s,1)}=0$. In that case, $s_k\leq s$ and $r_k\leq \exp(-(1-\theta^{-1})(1-s)k)$ for all $k$ large, so that
In all other cases, the error term decays slower than polynomially.

We closely follow the approach in <cit.>, where an analogue result is presented for the case $q_0=1$, i.e. for the random recursive tree. Set $K':=K-a_{i_n'}$ and for each $i_n\leq k\leq i_n'$ and each $u\in\N$ such that $\sum_{\ell=i_n}^{k-1}a_\ell<u\leq \sum_{\ell=i_n}^k a_\ell$, let $m_u=\lfloor \log_\theta n \rfloor +k$. We note that $m_u<\log_\theta n+i_n'<c\log n$, so that the results in Proposition <ref> can be used. Also, let $(v_u)_{u\in[K]}$ be $K$ vertices selected uniformly at random without replacement from $[n]$, and define $I:=[K]\backslash[K']$. Then, as the $X^{(n)}_{\geq k}$ and $X^{(n)}_{k}$ can be expressed as sums of indicators,

𝔼[(X^(n)_≥i_n')_a_i_n'∏_k=i_n^i_n'-1(X_k^(n))_a_k]   =(n)_K_n(v_u)=m_u, _n(v_w)≥m_w for all  u∈[K'],w∈I

|S|=ℓ(-1)^ℓ_n(v_u)≥m_u+_{u∈S} for all  u∈[K],
where the second step follows from <cit.> and is based on an inclusion-exclusion argument. We can now use Proposition <ref>. First, we note that there exists a $\beta>0$ such that for non-negative integers $m_1,\ldots, m_K< c\log n$,

_n(v_u)≥m_u+_{u∈S} for all  u∈[K]=∏_u=1^K 𝔼[(W/W+W)^m_u+_{u∈S}](1+o(n^-β)).
Now, by Theorem <ref> and the definition of $r_k$ in (<ref>) and as $r_k$ is decreasing by Lemma <ref> in the [sec:appendix]Appendix, when $|S|=\ell$,

∏_u=1^K (W/W+W)^m_u+_{u∈S}=q_0^Kθ^-ℓ-∑_u=1^K m_u(1+𝒪(r_⌊log_θn⌋+i_n∨n^-β')),
as the smallest $m_u$ equals $\lfloor \log_\theta n\rfloor+i_n$. We have

(n)_K ∑_ℓ=0^K'∑_S⊆[K']
|S|=ℓ(-1)^ℓq_0^K θ^-ℓ-∑_u=1^K m_u   =(n)_Kq_0^K θ^-K'-∑_u=1^K m_u∑_ℓ=0^K'K'ℓ(-1)^ℓθ^K'-ℓ

=(n)_Kq_0^K(1-θ^-1)^K'θ^-∑_u=1^K m_u.
We then observe that $(n)_K=\theta^{K\log_\theta n}(1+\mathcal O(1/n))$. Moreover, we recall that $K=\sum_{k=i_n}^{i_n'}a_k$ and $K'=\sum_{k=i_n}^{i_n'-1}a_k$, while $m_u=\lfloor \log_\theta n\rfloor +k$ if $\sum_{\ell=i_n}^{k-1}a_\ell\leq u<\sum_{\ell=i_n}^k a_\ell$ for $i_n\leq \ell\leq i_n'$; in addition, recall $\eps_n$ from (<ref>). Using (<ref>) combined with (<ref>) and (<ref>) in (<ref>), we obtain
𝔼[(X^(n)_≥i_n')_a_i_n'∏_k=i_n^i_n'-1(X_k^(n))_a_k]=   	q_0^K(1-θ^-1)^K'θ^Klog_θn-∑_u=1^K m_u(1+𝒪(r_⌊log_θn⌋+i_n∨n^-β))

=   (q_0θ^-i_n'+_n)^a_i_n'∏_k=i_n^i_n'-1(q_0(1-θ^-1)θ^-k+_n)^a_k

as desired.

The next lemma builds on <cit.> and <cit.> and provides bounds on the maximum degree that hold with high probability.

Let $W$ be a positive random variable that satisfies conditions <ref> and <ref> of Assumption <ref>. Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ which are i.i.d. copies of $W$. Fix $c\in(0,\theta/(\theta-1))$ and let $(k_n)_{n\in\N}$ be a non-negative, diverging integer sequence such that $k_n< c\log n$ and let $v_1$ be a vertex selected uniformly at random from $[n]$. If $\lim_{n\to\infty}n\P{\Zm_n(v_1)\geq k_n}=0$, then
Similarly, when instead $\lim_{n\to\infty}n\P{\Zm_n(v_1)\geq k_n}=\infty$,

Similar to what is discussed in Remark <ref>$(i)$, the result in this lemma is stronger than the results presented in <cit.> and <cit.>. It extends the latter to the WRT model rather than just the RRT model, and improves the former as the result holds for the non-conditional probability measure $\mathbb P$ rather than $\mathbb P_W$, which is what is used in [15]. Due to the difficulties of working with the conditional probability measure, only a first order asymptotic result can be proved there. With the improved understanding of the degree distribution, as in Proposition <ref>, the above result can be obtained, which allows for finer asymptotics to be proved.

The first result immediately follows from a union bound and the fact that

n_n(v_1)≥k_n=∑_i=1^n ≥k_n.
For the second result, let $A_{n,i}:=\{\zni\geq k_n\},i\in[n]$. Then, by the Chung-Erdős inequality (which is one way of formalizing the second moment method),
max_≥k_n=∪_i=1^n A_n,i≥(∑_i=1^n A_n,i)^2/∑_i≠jA_n,i∩A_n,j+∑_i=1^n A_n,i.
By (<ref>) it follows that $\sum_{i=1}^n\P{A_{n,i}}=n\P{\Zm_n(v_1)\geq k_n}$. Furthermore, by Proposition <ref>,
where $v_2$ is another vertex selected uniformly at random, unequal to $v_1$. Note that the condition that $k_n<c\log n$ is required for this to hold. Together with the above lower bound, these two observations yield
∪_i=1^n A_n,i≥(nA_n,v_1)^2/(nA_n,v_1)^2(1+o(1))+nA_n,v_1=nA_n,v_1/nA_n,v_1(1+o(1))+1.
Hence, when $n\P{A_{n,v_1}}=n\P{\Zm_n(v_1)\geq k_n}$ diverges with $n$, we obtain the desired result.

§.§ Non-rigorous proof of Proposition <ref> when $k=1$

What remains for this section is to prove Proposition <ref>. As the proof is rather long and involved, we first provide a non-rigorous step-by-step proof of the case $k=1$. That is, we provide an asymptotic estimate for $\P{\Zm_n(v)=m}$, where $v$ is a vertex selected uniformly at random. Though this part is not essential for the proof of Proposition <ref>, it helps the reader in understanding the complete proof of the proposition later in this section. In the next sub-section, we discuss the strategy of the full proof and take care of certain parts of the proof in separate lemmas. Whilst proving these lemmas, we refer back to the simpler non-rigorous proof provided here for guidance.
The main part of the proof is dedicated to proving (<ref>). Once this is established, (<ref>) follows without much effort. We thus focus on discussing the proof of (<ref>) here first.

To provide a non-rigorous proof of the asymptotic estimate of $\P{\Zm_n(v)=m}$, we first make the following simplification: we assume that $S_\ell=(\ell+1)\E W$ for all $\ell\in\N$. Naturally, the law of large numbers implies that $S_\ell/\ell\toas \E W$, so that, up to lower-order error terms, this equality holds. Using this simplification, however, allows us to omit many details and focus on the most important steps of the proof.

Let us fix an $\eps\in(0,1)$, which we shall choose sufficiently small later. We then first condition  on the value of the uniform vertex $v$, and distinguish between its values being smaller or larger than $n^\eps$. That is,

_n(v)=m   =1/n ∑_j=1^n _n(j)=m

=1/n ∑_1≤j< n^_n(j)=m+1/n ∑_n^≤j≤n_n(j)=m.
We first take care of the second sum, and start by determining $\Pf{\Zm_n(j)=m}$ when $j\geq n^\eps$, under the simplification that $S_\ell=(\ell+1)\E W$. Since $\Zm_n(j)$ is a sum of independent indicator random variables, we will see that $\Zm_n(j)$ is well-approximated by a Poisson random variable, whose rate equals the sum of the success probabilities of the indicator random variables. By the simplification $\cS_\ell=(\ell+1)\E W$, we can thus determine that
_n(j)=∑_i=j+1^n _{i→j}=∑_i=j+1^n Ber(W_j/S_i-1)≈Poi(∑_j=i+1^n W_j/iW)≈Poi(W_j/Wlog(n/j))=:P_j.
It thus follows that $\Pf{\Zm_n(j)=m}\approx \Pf{P_j=m}$. We now provide the necessary steps to obtain this intuitive result. The degree of vertex $j$ in $T_n$ equals exactly $m$ when there exist vertices $i_1,\ldots ,i_m$ that connect to $j$, and all other vertices do not. Since these connections are independent,

_n(j)=m   =∑_j<i_1<…<i_m≤n∏_s=1^m W_j/S_i_s-1∏_s=j+1
s≠i_ℓ, ℓ∈[m]^n (1-W_j/S_s-1)

=∑_j<i_1<…<i_m≤n∏_s=1^m W_j/i_sW∏_s=j+1
s≠i_ℓ, ℓ∈[m]^n (1-W_j/sW)
Here, we sum over all possible choices of vertices $i_1<\ldots <i_m$ that connect to $j$, and the final step follows from the simplifying assumption. We now include the terms $s \in \{i_1, \ldots, i_m\}$
in the second product, by changing the denominator in the fraction in the first product to $i_s\E W- W_j$. This yields

_n(j)=m=∑_j<i_1<…<i_m≤n∏_s=1^m W_j/i_sW-W_j∏_s=j+1^n (1-W_j/sW).
Since $W_j\in(0,1]$ almost surely, $i_s>j\geq n^\eps$, and $m<c\log n$, it follows that for any $\xi\in(0,1)$,

∏_s=1^m 1/i_sW-W_j=∏_s=1^m 1/i_sW(1+(n^-))=(1+(n^-(1-ξ)))∏_s=1^m 1/i_sW.
∏_s=j+1^n (1-W_j/sW)=exp(∑_s=j+1^n log(1-W_j/sW))=exp(-(1+(n^-))∑_s=j+1^n W_j/sW).
∑_s=j+1^n 1/s≈log(n/j),
we arrive at

∏_s=j+1^n (1-W_j/sW)≈(j/n)^(1+ζ_n)W_j/W,
where $\zeta_n=\cO(n^{-\eps})$. Combined with (<ref>) in (<ref>), this yields
_n(j)=m=(1+(n^-(1-ξ)))(j/n)^(1+ζ_n)W_j/W( W_j/W)^m∑_j<i_1<…<i_m≤n∏_s=1^m 1/i_s.
We can approximate the sum by the multiple integrals
∫_j^n ∫_x_1^n ⋯∫_x_m-1^n ∏_s=1^m x_s^-1 x̣_m…x̣_1.
By Lemma <ref> we obtain that this equals $(\log(n/j))^m/m!$. So, we finally have
_n(j)=m   ≈(j/n)^W_j/W(W_j/Wlog(n/j))^m1/m!

as desired. Since all vertex-weights are i.i.d., when we take an expectation over the weights, we can in fact omit the index $j$ from $W_j$ and use a general random variable $W$ instead, so that $P_j$ has mean $\log(n/j)W/\E W$. Using this expression in the second sum in (<ref>) approximately yields

1/n ∑_n^≤j≤n P_j=m.
To avoid confusion between different parametrisations, we say that a random variable $X$ has a Gamma$(\alpha,\beta)$ distribution for some $\alpha,\beta>0$ when it has a probability density function $f:\R_+\to \R_+$ with

f(x)=β^α/Γ(α)x^α-1^-βx,    x>0.
We now use the following duality between Poisson and gamma random variables. Let
$G\sim \text{Gamma}(m,1)$ be a gamma random variable for some integer $m$. Note that we can also interpret $G$ as a sum of $m$ independent rate one exponential random variables. Then, conditionally on $W$, the event $\{P_j=m\}$ can be thought of as the event that in a rate one Poisson process exactly $m$ particles have arrived before time $\log(n/j)W/\E W$. This is equivalent to the sum of the first $m$ inter-arrival times (which are rate one exponentially distributed) being at most $\log(n/j)W/\E W$, and the sum of the first $m+1$ inter-arrival times exceeding this quantity. As we mentioned, this sum of $m$ rate one exponential random variables is, in law, identical to $G$. So, if we let $V$ be the $m+1^{\text{st}}$ inter-arrival time, independent of $G$, then
P_j=m   =G≤log(n/j)W/W, G+V>log(n/j)W/W

=Y≤log(n/j), Y+V>log(n/j).
where, conditionally on $W$, we have $Y\sim \text{Gamma}(m,W/\E W)$ and $ \wt V\sim \text{Exp}(W/\E W)$. In (<ref>), this yields
1/n ∑_n^≤j≤nY≤log(n/j),Y+V>log(n/j)≈Y≤log(n/v),Y+V>log(n/v),
where we recall that $v$ is a uniform element of $[n]$. Observe that $\log(n/v)\approx T$, where $T\sim \text{Exp}(1)$. As a result, the conditional probability can be expressed, using that $Y$ can be viewed as a sum of $m$ i.i.d. copies of $\wt V$ and the memoryless property of exponential random variables, as
Y≤T, Y+V≥T =W/W+W(W/W+W)^m,
as desired. We provide some more details for this derivation. First, we write the sum as

1/n ∑_n^≤j≤nY≤log(n/j)-Y+V≤log(n/j) .
Since $Y+\wt V\sim \text{Gamma}(m+1,W/\E W)$, it suffices to deal with the first conditional probability only. We can approximate the sum by
∑_n^≤j≤nY≤log(n/j)   ≈∫_n^^n Y≤log(n/x) x̣=n∫_0^(1-)logn^-yY≤y ỵ.
The second step follows from a variable transformation $y=\log(n/x)$. We write $\Pf{Y\leq y}=\int_0^y f_{Y|W}(x)\d x$, where $f_{Y|W}(x)$ is as in (<ref>) with $\alpha=m-1, \beta=W/\E W$, the conditional probability density function of $Y$, conditionally on $W$. Changing the order of integration  yields
n   ∫_0^(1-)logn^-x f_Y|W(x) x̣-n^Y≤(1-)logn

=n(W/W+W)^m Y'≤(1-)logn-n^Y≤(1-)logn,
where $Y'\sim \text{Gamma}(m,1+W/\E W)$, conditionally on $W$. A similar result with $m+1$ and $Y''\sim\text{Gamma}(m+1,1+W/\E W)$ instead of $m$ and $Y'$ follows for the probability of the event $\{Y+\wt V\leq \log(n/j)\}$. We remark that, via the construction of the random variables $Y'$ and $Y''$ using $Y$ and $Y+\wt V$, respectively, they are defined on the same probability space and that in fact $Y''$ stochastically dominates $Y'$. As such, combining both in (<ref>) approximately provides
𝔼[(W/W+W   )^m (Y'≤(1-)logn-W/W+WY”≤(1-)logn)]

=   (1+(n^-(1-ξ)))W/W+W(W/W+W)^mY'≤(1-)logn

+(W/W+W)^mW/W+WY'≤(1-)logn, Y”>(1-)logn.
Here, the second step follows from the fact that $Y'\preceq Y''$. We finally show that this quantity equals
for some small $\beta>0$, when $\eps$ is sufficiently small, by proving that $\Pf{Y'\leq (1-\eps)\log n}$ and $\Pf{Y''>(1-\eps)\log n}$ are sufficiently close to one and zero, respectively. We thus conclude that

1/n ∑_n^≤j≤n_n(j)=m   =W/W+W(W/W+W)^m(1+o(n^-β))

where $\beta$ and $\eps$ are sufficiently small and where we recall $p_m$ from (<ref>).

It remains to show that the first term on the right-hand side of (<ref>) can be included in the $o(n^{-\beta})$ term. The main difficulty here for the actual proof is controlling the partial sums $S_\ell$, which, for `too small' $\ell$, do not concentrate around the expected value with probability sufficiently close to one. In this simplified non-rigorous proof, however, the assumption that $S_\ell=(\ell+1)\E W$ allows us to ignore this technical difficulty for now and focus on the main probabilistic arguments. The aim is to show that

1/n ∑_1≤j<n^_n(j)=m=o(p_mn^-β),
for some small $\beta$ when $\eps$ is sufficiently small.

We first focus on the case that $m=\wt c\log n+o(\log n)$ with $\wt c<1/\log \theta$. In this case, we can simply bound the conditional probability from above by one to obtain the upper bound $n^{-(1-\eps)}$. Then, by Lemma <ref>, we  have that $p_m\geq (\theta+\xi)^{-m}=n^{-\wt c\log(\theta+\xi)}$ for any $\xi>0$. Since $\wt c<1/\log \theta$, it follows that we can choose $\xi, \beta$, and $\eps$ sufficiently small such that $n^{-(1-\eps)}=o(n^{-\beta-\wt c\log(\theta+\xi)})=o(p_mn^{-\beta})$, from which the claim in (<ref>) follows.

When $\wt c\in[1/\log \theta,c)$ instead (where we recall that $c<\theta/(\theta-1)$), a more careful approach is required.
In this case, we bound $\Pf{\Zm_n(j)=m}\leq \Pf{\Zm_n(j)\geq m}$ and use a Chernoff bound on the right-hand side of the inequality. This bound follows from the proof of <cit.> and yields

1/n ∑_1≤j<n^_n(j)=m≤1/n ∑_1≤j<n^exp(m(1-u_j+logu_j)),
u_j:=1/m∑_ℓ=j^n-1W_j/S_ℓ=1/m∑_ℓ=j+1^nW_j/ℓW≤log(n/j)/mW≤logn/mW=1+o(1)/c W.
Note that the second step follows from our simplifying assumption on $S_\ell$ and we bound $W_j$ from above by one in the inequality. Using that $x\mapsto 1-x+\log x$ is increasing on $(0,1)$, that $1/(\wt c\E W)\leq \log \theta/(\theta-1)<1$, and that we have a bound for $u_j$ uniformly in $1\leq j\leq n^\eps$, (<ref>) yields

1/n ∑_1≤j<n^_n(j)=m   ≤1/n^1-exp((1+o(1))clogn (1-1/c(θ-1)+log(1/c (θ-1))))

=  n^-(1-)+(1+o(1))c(1-1/(c(θ-1))+log(1/(c (θ-1)))).
The aim is to show that this last expression is $o(p_mn^{-\beta})$ for some sufficiently small $\beta>0$. Again using that $p_mn^{-\beta}\geq n^{-\wt c\log(\theta+\xi)-\beta}$, it suffices to show that
-(1-)+c(1-1/c(θ-1)+log(1/c (θ-1)))<-clog(θ+ξ)-βholds when we choose $\xi,\eps,$ and $\beta$ sufficiently small. Since the right-hand side is continuous in $\xi$ and $\beta$, and the left-hand side is continuous in $\eps$, it suffices to prove that
-1+c(1-1/c(θ-1)+log(1/c (θ-1)))<-clogθholds for any $\theta\in(1,2]$ and any $\wt c<\theta/(\theta-1)$. As the second derivative of the mapping $x\mapsto -1+x-1/(\theta-1)+x\log(1/(x(\theta-1)))$ is negative and the mapping $x\mapsto -x\log \theta$ is tangent to the former mapping at $x=\theta/(\theta-1)$, the inequality follows for all $\wt c<\theta/(\theta-1)$. This completes the proof of (<ref>) for some sufficiently small $\eps$ and $\beta$. Combined with (<ref>), this yields (<ref>) for $k=1$.

§.§ Complete proof of Proposition <ref>

Before we provide the complete proof, we first discuss the proof strategy. Though this is similar to the approach of the non-rigorous proof provided in the previous sub-section, dealing with $k>1$ many uniformly selected vertices provides technical challenges worth addressing. Let us start by introducing the following notation: for two sequences $f(n)$ and $g(n)$, we let $f(n)\leq j_1\neq \ldots \neq j_k\leq g(n)$ denote the set

{(j_1,…, j_k)∈^k: j_ℓ∈[f(n),g(n)] for all ℓ∈[k],  and j_ℓ_1≠j_ℓ_2 for any 1≤ℓ_1<ℓ_2≤k}.
In words, summing over all indices $f(n)\leq j_1\neq \ldots \neq j_k\leq g(n)$ denotes summing over all distinct indices $j_1,\ldots, j_k$ which are at least $f(n)$ and at most $g(n)$.

The left-hand side of (<ref>) can be expressed by conditioning on the values of the typical vertices, and splitting between cases of young and old vertices. That is,

_n(v_ℓ)=m_ℓ for all ℓ∈[k]=   1/(n)_k∑_1≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all ℓ∈[k]

=   1/(n)_k∑_n^ ≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all ℓ∈[k]

+1/(n)_k∑_j∈I_n()_n(j_ℓ)=m_ℓ for all ℓ∈[k],

I_n():={j=(j_1,…,j_k):1≤j_1≠…≠j_k≤n, ∃i∈[k] j_i<n^ }
for any $\eps\in(0,1)$. Splitting the sum on the first line into the two sums on the second and third line allows us to deal with them in a different way, and is similar to the distinction made in (<ref>). In the sum on the second line, in which all indices are at least $n^{ \eps}$, we can apply the law of large numbers on sums of vertex-weights to gain more control over the conditional probability of the event $\{\Zm_n(j_\ell)=m_\ell\text{ for all }\ell\in[k]\}$. The aim is to show that this first sum has the desired form, as on the right-hand side of (<ref>). This uses the same ideas as in the non-rigorous proof in the previous sub-section, but increases in difficulty due to multiple summations, integrals, and careful `book-keeping' of a large number of distinct indices.

The sum on the third line, in which at least one of the indices takes on values strictly smaller than $n^{\eps}$ can be shown to be negligible compared to the first sum. Especially when $m_\ell$ is large, this is non-trivial. To do this, we consider the tail events $\{\Zm_n(j_\ell)\geq m_\ell\text{ for all }\ell\in[k]\}$ and use the negative quadrant dependence of the degrees (see Remark <ref> and <cit.>), so that we can deal with the more tractable probabilities $\Pf{\Zm_n(j_\ell)\geq m_\ell}$ for all $\ell\in[k]$, rather than the probability of the intersection of all tail degree events. We observe that this is not required when $k=1$ (that is, using the negative quadrant dependence), and significantly increases the technical difficulty of this part of the proof compared to the non-rigorous proof provided in the previous sub-section. Depending on whether the indices in $I_n(\eps)$ are at most or at least $n^{\eps}$, we then use bounds similar to one developed in the proof of <cit.> or use an approach similar to what we use to bound the sum on the second line of (<ref>), respectively.

In the following lemma, we deal with the sum on the second line of (<ref>).

Let $W$ be a positive random variable that satisfies condition <ref> of Assumption <ref>. Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ which are i.i.d. copies of $W$ and fix $k\in\N$ and $c\in (0,\theta/(\theta-1))$. Then, there exist $\beta>0$ and an $\eps\in(0,1)$ that can be made arbitrarily small, such that uniformly over non-negative integers $m_\ell< c\log n, \ell\in[k]$,
1/(n)_k∑_n^≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all  ℓ∈[k]=∏_ℓ=1^k 𝔼[W/W+W(W/W+W)^m_ℓ](1+o(n^-β)).

We note that condition <ref> of Assumption <ref> is not required for this result to hold. To prove this lemma, we sum over all possible $m_\ell$ vertices that connect to $j_\ell$ for each $\ell\in[k]$ and use the fact that the $j_1,\ldots, j_k$ are at least $n^{\eps}$ to precisely control the connection probabilities and to evaluate the sums over all the possible $m_\ell$ vertices for all $\ell\in[k]$, as well as the sum over the indices $j_1,\ldots, j_k$.

In the following lemma, we show the sum on the third line of (<ref>) is negligible compared to the sum on the second line.

Let $W$ be a positive random variable that satisfies conditions <ref> and <ref> of Assumption <ref>. Consider the WRT model in Definition <ref> with vertex-weights $(W_i)_{\inn}$ which are i.i.d. copies of $W$. Fix $k\in\N,c\in (0,\theta/(\theta-1))$ and recall $I_n(\eps)$ from (<ref>). There exist $\eps\in(0,1)$ and a $\beta>0$ such that uniformly over non-negative integers $m_\ell< c\log n, \ell\in[k]$,
1/(n)_k∑_j∈I_n()_n(j_ℓ)=m_ℓ for all ℓ∈[k]=o(∏_ℓ=1^k W/W+W(W/W+W)^m_ℓ n^-β).

Note that condition <ref> of Assumption <ref> is required only in this lemma, where it was not necessary in Lemma <ref>. In fact, it is required for one inequality in the proof only, which convinces us that it could possibly be avoided.

It is clear that (<ref>) in Proposition <ref> immediately follows from using the results of Lemmas <ref> and <ref> in (<ref>). Namely, in Lemma <ref> we can take $\eps $ arbitrarily small and the left-hand side of the equality in Lemma <ref> is monotone decreasing as $\eps$ decreases, so that we can take $\eps$ as small as required. In what follows we first prove Lemma <ref> in Section <ref>, prove Lemma <ref> in Section <ref>, and finally complete the proof of Proposition <ref> in Section <ref>. After each of the proofs we discuss the required adaptations to prove the results of Lemmas <ref> and <ref> for the model with random out-degree, as introduced in Remark <ref>$(ii)$.

§.§ Proof of Lemma <ref>

We provide a matching upper bound and lower bound for
1/(n)_k∑_n^≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all  ℓ∈[k].

Upper bound. Let  $\zeta_n=n^{-\delta\eps}/\E{W}$ for some $\delta\in(0,1/2)$. We define the event

E^(1)_n:={ ∑_ℓ=1^j W_ℓ∈((1-ζ_n)Wj,(1+ζ_n)Wj), for all  n^≤j≤n},
We use $E^{(1)}_n$ to mimic the simplified assumption that $S_j=(j+1)\E W$ in the non-rigorous proof in Section <ref>. We know that $\mathbb P((E^{(1)}_n)^c)=o(n^{-\gamma})$ for any $\gamma>0$ (and thus of smaller order than $\prod_{\ell=1}^k p_{m_\ell}n^{-\beta}$ for any $\beta>0$ and uniformly in $m_1,\ldots m_k<(\theta/(\theta-1))\log n$) from Lemma <ref> in the [sec:appendix]Appendix. By also conditioning on the vertex-weights, this yields for any $\gamma>0$ the upper bound

1/(n)_k   ∑_n^≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all ℓ∈[k]

≤   1/(n)_k∑_n^≤j_1≠…≠j_k≤n𝔼[_n(j_ℓ)=m_ℓ for all ℓ∈[k]_E_n^(1)]+o(n^-γ),
Now, to express the first term on the right-hand side of (<ref>), we consider ordered indices rather than unordered ones. We provide details for the case $n^{\eps}\leq j_1<j_2<\ldots<j_k\leq n$ and discuss later on how the other permutations of $j_1,\ldots,j_k$ can be dealt with. Moreover, for every $\ell\in[k]$, we introduce the ordered indices $j_{\ell}<i_{1,\ell}<\ldots<i_{m_\ell,\ell}\leq n,\ell\in[k]$, which denote the steps at which vertex $\ell$ increases it degree by one. Note that for every $\ell\in[k]$ these indices are distinct by definition, but we also require that $i_{s,\ell}\neq i_{t,j}$ for any $\ell,j\in[k],s\in[m_\ell]$ and $t\in[m_j]$ (equality is allowed only when $\ell=j$ and $s=t$). Indeed, a new vertex can only connect to one already present vertex. We denote this constraint by adding a $*$ on the summation symbol. Finally, we define $j_{k+1}:=n$. Combining these additional steps, we arrive at

1/(n)_k   ∑_n^≤j_1< …< j_k≤n_n(j_ℓ)=m_ℓ for all  ℓ∈[k]_E^(1)_n

=   1/(n)_k∑_n^≤j_1<…<j_k≤n   ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
s≠i_ℓ,t,ℓ∈[m_t],t∈[k]^j_u+1(1-∑_ℓ=1^u W_j_ℓ/∑_ℓ=1^s-1W_ℓ)_E^(1)_n].
This step is equivalent to (<ref>) in the non-rigorous proof. The terms in the first double product denote the probabilities that vertices $i_{s,t}$ connect to $j_t$, whereas the terms in the second double product denote the probabilities that vertices $i_{s,t}$ do not connect to the vertices $j_\ell$ such that $j_\ell<i_{s,t}$. Similar to (<ref>) in the non-rigorous proof, we then include the terms where $s=i_{\ell,t}$ for all $\ell\in[m_t]$ and $t\in[k]$ in the second double product. To do this, we change the first double product to

∏_t=1^k ∏_s=1^m_tW_j_t/∑_ℓ=1^i_s,t-1W_ℓ-∑_ℓ=1^k W_j_ℓ_{i_s,t>j_ℓ}≤∏_t=1^k ∏_s=1^m_t W_j_t/∑_ℓ=1^i_s,t-1W_ℓ-k,
that is, we subtract the vertex-weight $W_{j_\ell}$ in the numerator when the vertex  $j_\ell$ has already been introduced by step $i_{s,t}$. In the upper bound we use that the weights are bounded from above by one. We thus arrive at the upper bound

1/(n)_k∑_n^≤j_1<…<j_k≤n   ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]𝔼[∏_t=1^k∏_s=1^m_tW_j_t/∑_ℓ=1^i_s,t-1W_ℓ-k∏_u=1^k∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_j_ℓ/∑_ℓ=1^s-1W_ℓ)_E^(1)_n].
For ease of writing, we omit the first sum until we actually intend to sum over the indices $j_1,\ldots,j_k$. We use the bounds from the event $E^{(1)}_n$ to bound
∑_ℓ=1^i_s,t-1W_ℓ≥(i_s,t-1)W(1-ζ_n),    ∑_ℓ=1^s-1W_ℓ≤sW (1+ζ_n).
For $n$ sufficiently large, we observe that $(i_{s,t}-1)\E W(1-\zeta_n)-k\geq i_{s,t}\E W(1-2\zeta_n)$, which yields
1/(n)_k  ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]𝔼[∏_t=1^k∏_s=1^m_tW_j_t/i_s,tW (1-2ζ_n) ∏_u=1^k∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_j_ℓ/sW(1+ζ_n))_E^(1)_n].
Moreover, relabelling the vertex-weights $W_{j_t}$ to $W_t$ for $t\in[k]$ does not change the distribution of the terms within the expected value, so that the expected value remains unchanged. We can also bound the indicator from above by one, to arrive at the upper bound
1/(n)_k  ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]𝔼[∏_t=1^k∏_s=1^m_tW_t/i_s,tW (1-2ζ_n) ∏_u=1^k∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_ℓ/sW(1+ζ_n))].
We bound the final product from above by

∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_ℓ/sW(1+ζ_n))   ≤exp(-1/W(1+ζ_n) ∑_s=j_u+1^j_u+1∑_ℓ=1^u W_ℓ/s)

≤exp(-1/W(1+ζ_n) ∑_ℓ=1^u W_ℓlog(j_u+1/j_u+1))

= (j_u+1/j_u+1)^-∑_ℓ=1^u W_ℓ/(W(1+ζ_n)).
As the weights are almost surely bounded by one, we thus find
∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_ℓ/sW(1+ζ_n))≤(j_u+1/j_u)^-∑_ℓ=1^u W_ℓ/(W(1+ζ_n))(1+𝒪(n^-)),
which is equivalent to (<ref>) in the non-rigorous proof.
As a result, we obtain the upper bound
1/(n)_k  ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]   𝔼[∏_t=1^k ((W_t/W)^m_t∏_s=1^m_t1/i_s,t(1-2ζ_n))∏_u=1^k(j_u+1/j_u)^-∑_ℓ=1^u W_ℓ/(W(1+ζ_n))]

As $j_{k+1}=n$, we can simplify the final product to obtain
1/(n)_k   ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k](1-2ζ_n)^-∑_h=1^k m_h𝔼[   ∏_t=1^k (W_t/W)^m_t∏_t=1^k (j_t^W_t/(W(1+ζ_n))∏_s=1^m_ti_s,t^-1)

×n^-∑_ℓ=1^k W_ℓ/(W(1+ζ_n))](1+𝒪(n^-)).
We bound this from above even further by no longer constraining the indices $i_{s,t}$ to be distinct. That is, for distinct $t_1$ and $t_2\in[k]$, we allow $i_{s_1,t_1}=i_{s_2,t_2}$ to hold for any $s_1\in[m_{t_1}]$ and $s_2\in[m_{t_2}]$. This yields

1/(n)_k  ∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k](1-2ζ_n)^-∑_h=1^k m_h𝔼[   ∏_t=1^k (W_t/W)^m_t∏_t=1^k (j_t^W_t/(W(1+ζ_n))∏_s=1^m_ti_s,t^-1)

×n^-∑_ℓ=1^k W_ℓ/(W(1+ζ_n))](1+𝒪(n^-)).
We set

and look at the terms

n^-∑_t=1^k a_t/(n)_k ∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]∏_t=1^k ( (a_t(1+ζ_n))^m_tj_t^a_t ∏_s=1^m_ti_s,t^-1) .
We bound the sums from above by multiple integrals, almost surely, which yields

n^-∑_t=1^k a_t/(n)_k∏_t=1^k (a_t(1+ζ_n))^m_tj_t^a_t ∫_j_t^n ∫_x_1,t^n⋯∫_x_m_t-1,t^n ∏_s=1^m_tx_s,t^-1 x̣_m_t,t…x̣_1,t.
Using (<ref>) in Lemma <ref>, we obtain that this equals
n^-∑_t=1^k a_t/(n)_k∏_t=1^k (a_t(1+ζ_n))^m_tj_t^a_t (log(n/j_t))^m_t/m_t!.
Substituting this in (<ref>) and reintroducing the sum over the indices $j_1,\ldots, j_k$, we arrive at

(1+ζ_n)^∑_h=1^k m_h/(n)_k∑_n^≤j_1<…<j_k≤n∏_t=1^k(j_t/n)^a_t(a_tlog(n/j_t))^m_t/m_t!.
We observe that switching the order of the indices $j_1,\ldots,j_k$ achieves the same result as permuting the $m_1,\ldots,m_k$ and $a_1,\ldots, a_k$. Hence, if we let $\pi:[k]\to[k]$ be a permutation, then considering the indices $n^{\eps}\leq j_{\pi(1)}<j_{\pi(2)}<\ldots<j_{\pi(k)}\leq n$ yields a similar result as in (<ref>) but with a term $j_{\pi(t)}^{a_{\pi(t)}}(\log(n/j_{\pi(t)}))^{m_{\pi(t)}}/m_{\pi(t)}!$ in the final product. Since this product is invariant to such permutations of the $m_t$ and $a_t$, the only thing that would change is the summation order of the indices $j_1,\ldots,j_k$.

By using (<ref>) in (<ref>) and incorporating all permutations of the indices, i.e. $n^\eps \leq j_{\pi(1)}<j_{\pi(2)}<\ldots<j_{\pi(k)}\leq n$ for all $\pi\in P_k$ (where $P_k$ denotes the set of all permutations on $[k]$), we arrive at

1/(n)_k   ∑_n^≤j_1≠…≠j_k≤n𝔼[_n(j_ℓ)=m_ℓ,ℓ∈[k]_E^(1)_n]

≤    1/(n)_k(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h∑_π∈P_k∑_n^≤j_π(1)<…<j_π(k)≤n∏_t=1^k(j_π(t)/n)^a_t(a_tlog(n/j_π(t)))^m_t/m_t!

=   1/(n)_k(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h∑_n^≤j_1≠…≠j_k≤n∏_t=1^k(j_t/n)^a_t(a_tlog(n/j_t))^m_t/m_t!.
We bound the last expression from above even further by allowing the indices $j_1,\ldots, j_k$ to take any integer value in $[n^\eps,n]$. That is, $j_{\ell_1}=j_{\ell_2}$ is allowed for $\ell_1\neq \ell_2$. As this introduces more non-negative terms, it yields the upper bound
1/(n)_k(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h𝔼[∑_n^≤j_1≤n⋯    ∑_n^≤j_k≤n∏_t=1^k(j_t/n)^a_t(a_tlog(n/j_t))^m_t/m_t!]

=1/(n)_k(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h∏_t=1^k    ∑_n^≤j≤n(j/n)^a_t(a_tlog(n/j))^m_t/m_t!,
where we note that the product can be taken out in the second line, since the weights are independent. We now observe two things: First, we can redefine $a_t=a:=W/(\E W(1+\zeta_n))$. After all, the index of the vertex-weights $W_1,\ldots, W_k$ is irrelevant, since they are independent and identically distributed. Second, the summand is equal to $\Pf{P(a)=m_t}$, where $P(a)\sim \text{Poi}(a\log(n/j))$, conditionally on $W$. So we obtain, similar to (<ref>) in the non-rigorous proof,
1/(n)_k(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h∏_t=1^k∑_n^≤j≤nP(a)=m_t.
We now use the duality between Poisson and gamma random variables, as also explained in the intuitive proof after (<ref>). That is, let $G_t\sim \text{Gamma}(m_t,1)$ and $V\sim \text{Exp}(1)$ be independent random variables. Then, $\{P(a)=m_t\}=\{G_t\leq a\log(n/j), G_t+V>a\log(n/j)\}$, so that

P(a)=m_t   =G_t≤alog(n/j), G_t+V>alog(n/j)

=Y_t≤log(n/j), Y_t+V>log(n/j)

where $Y_t\sim \text{Gamma}(m_t,a)$ and $\wt V\sim \text{Exp}(a)$, conditionally on $W$ (and observe that $Y_t+\wt V\sim \text{Gamma}(m_t+1,a)$). We thus obtain

1/(n)_k(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h∏_t=1^k∑_n^≤j≤n(Y_t≤log(n/j)-ℙ_(Y_t+V≤log(n/j))),
similar to (<ref>) in the non-rigorous proof. We now compare the sum of the gamma probabilities with an integral. That is, since both probabilities are decreasing in $j$, we can bound the sum from above by

∫_⌊n^⌋^n    Y_t≤log(n/x) x̣-∫_⌈n^⌉^n ℙ_(Y_t+V≤log(n/x)) x̣

=n∫_0^log(n/⌊n^⌋) ^-yY_t≤y ỵ-n∫_0^log(n/⌈n^⌉)^-yℙ_(Y_t+V≤y) ỵ,
where we use a variable substitution $y=\log(n/x)$ to obtain the second line. Writing the cumulative density function as an integral from zero to $y$ and switching the order of integration, we find
n   ^-Y_t_{Y_t≤log(n/⌊n^⌋)}-n^-(Y_t+V)_{Y_t+V≤log( n/⌈n^⌉)}

As the last term is negative, we can omit it to obtain an upper bound. The first term on the second line can be bounded from above by
Combined, this yields the upper bound

n^-Y_t_{Y_t≤log(n/⌊n^⌋)}-n^-(Y_t+V)_{Y_t+V≤log( n/⌈n^⌉)}+n^1-(a/1+a)^m_t+1.
We now distinguish two cases:

item:1$(1)$ $m_t=c_t\log n+o(\log n)$ with $c_t\in[0,1/(\theta-1)]$, for all $t\in[k]$.

item:2$(2)$ $m_t=c_t\log n+o(\log n)$ with $c_t\in(1/(\theta-1),c)$, for some $t\in[k]$.

In case <ref>, we bound the difference of the expected values from above by

n   ^-Y_t-n^-(Y_t+V)+n^-(Y_t+V)_{Y_t+V>log(n/⌈n^⌉)}+n^1-(a/1+a)^m_t+1

Substituting this for the argument of the expected value for each $t\in[k]$ in (<ref>) yields

(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h(1+(n^-))∏_t=1^k(1/1+a(a/1+a)^m_t+(n^-(1-))).
We recall that $a:=W/(\E W(1+\zeta_n))$ and that $\zeta_n:=n^{-\delta\eps}/\E W$. Since $W\in[0,1]$ almost surely and $m_t=\cO(\log n)$,

for some small $\beta>0$. We have by Lemma <ref> that $p_{m_t}\geq (\theta+\xi)^{-m_t}$ for any $\xi>0$. Now we use that in case <ref> $m_t=c_t\log n+o(\log n)$ with $c_t<1/(\theta-1)$. As a result, for $\xi$, $\eps,$ and some $\beta>0$ sufficiently small and since $\log\theta<\theta-1$ for $\theta>1$, we then have $n^{-(1-\eps)}=o( n^{-(c_t+o(1))\log(\theta+\xi)-\beta})=o(p_{m_t}n^{-\beta})$. Together with (<ref>), this implies we can write the argument of the product in (<ref>) as $p_{m_t}(1+o(n^{-\beta}))$ whenever $m_t$ satisfies case <ref>.

In case <ref>, these bounds do not suffice. First of all, we note that  because of the product structure in (<ref>), we can deal with any
terms that satisfy $c_t \in [0,1/(\theta -1)]$ in the same way as in <ref>. Without loss of generality we thus assume that $c_t \in (1/(\theta-1), c)$ for all $t  \in[k]$.	In this case, we use that for any $N>0$,

^-Y_t_{Y_t≤N}   =∫_0^N a^m_t/Γ(m_t)x^m_t-1^-(1+a)x x̣

=(a/1+a)^m_t∫_0^N(1+a)^m_t/Γ(m_t)x^m_t-1^-(1+a)x x̣

where $Y_t'\sim \text{Gamma}(m_t,1+a)$, conditionally on $W$. As $Y_t+\wt V\sim \text{Gamma}(m_t+1,a)$, we also obtain a similar result for the second expected value in (<ref>) with a random variable $Y''_t\sim \text{Gamma}(m_t+1,1+a)$. As in the non-rigorous proof, we can assume that $Y_t'$ and $Y''_t$ are defined on the same probability space and we have that $Y_t' \preceq Y_t''$. Using this in (<ref>), we thus obtain

n   (a/1+a)^m_t[Y_t'≤log(n/⌊n^⌋)-a/1+aY_t”≤log(n/⌈n^⌉)]+n^1-(a/1+a)^m_t+1

≤n(a/1+a)^m_t[1/1+aY'_t≤log(n/⌊n^⌋)+Y'_t≤log(n/⌈n^⌉), Y”_t>log(n/⌈n^⌉)

By omitting the probability from the first term and bounding the other two probabilities from above by $\Pf{Y''_t>\log(n/\lceil n^\eps\rceil)}$, we obtain an upper bound
Again, we substitute this for the argument in the expected value in (<ref>) to obtain for some large constant $C>0$,

(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h(1+(n^-))∏_t=1^k(   (1/1+a(a/1+a)^m_t

+   C(a/1+a)^m_t(Y”_t>log(n/⌈n^⌉)+n^-)).
It thus remains to show that the second expected value in (<ref>) is of sufficiently smaller order compared to the first. We obtain this by using the indicators $\ind_{\{(1+a)<c_t/(1-\mu)\}}$ and $\ind_{\{1+a\geq c_t/(1-\mu)\}}$ to split the expected value in two parts, for some $\mu>0$ small enough such that $c_t/(1-\mu)<\theta/(\theta-1)$ (which is possible since $c_t<c<\theta/(\theta-1)$). For the first indicator, we can bound
(a/1+a)^m_t(Y”_t>log(n/⌈n^⌉)+n^-)_{1+a<c_t/(1-μ)}   ≤(c_t/(1-μ)-1/c_t/(1-μ))^m_t

for some small $\xi>0$ and $n$ sufficiently large. Since the first expected value in (<ref>) equals $p_{m_t}\geq (\theta+\xi/2)^{-m_t}$, where the inequality follows from Lemma <ref>, we thus obtain that

for some small $\beta>0$, since $m_t=c_t\log n+o(\log n)$ with $c_t\in[1/\log \theta,c)$. For the second indicator, we observe that $\{Y''_t>\log(n/\lceil n^\eps\rceil)\}=\{Z_t>(1+a)(1-\eps)\log n(1+o(1))\}$, where $Z_t\sim \text{Gamma}(m_t+1, 1)$. We then have
𝔼   [(a/1+a)^m_tZ_t>(1+a)(1-)logn(1+o(1))_{1+a≥c_t/(1-μ)}]

It thus suffices to show that the probability on the right-hand side is $o(n^{-\beta})$ for some small $\beta>0$. By choosing $\eps\in(0,\mu)$ we can apply a standard large deviation bound. Let $(V_i)_{i\in\N}$ be i.i.d. exponential rate $1$ random variables and let $I(a):=a-1-\log(a)$ be their rate function. Then, as we can think of $Z_t$ as the sum of $V_1,\ldots,V_{m_t+1}$,
ℙ(Z_t≥c_t (1-)/1-μlogn(1+o(1)))   =∑_i=1^m_t+1V_i≥(m_t+1) c_t  (1-)logn(1+o(1))/(1-μ)(m_t+1)

≤exp(-(m_t+1)I(c_t (1-)logn(1+o(1))/(1-μ)(m_t+1))).
In the first step, we express the upper bound within the probability in terms of the mean of the sum of random variables, which equals $m_t+1$. We then use the large deviations bound in the second step, which we can do as the argument of $I$ is strictly greater than $1$ when $n$ is sufficiently large (as $m_t+1\sim c_t\log n$) and $\eps\in(0,\mu)$ is sufficiently small. Since $I((c_t+o(1)) (1-\eps) \log n/((1-\mu)(m_t+1)))=  (1-\eps)/(1-\mu)-1-\log(  (1-\eps)/(1-\mu))+o(1)$, we thus arrive at

ℙ(Z_t≥c_t (1-)/1-μlogn(1+o(1)))   ≤^-c_tlogn( (1-)/(1-μ)-1-log( (1-)/(1-μ))+o(1))

where $c_{t,\mu,\eps}:=c_t(  (1-\eps)/(1-\mu)-1-\log(  (1-\eps)/(1-\mu)))>0$ as $\eps<\mu$ and $x-1-\log x>0$ holds for $x>1$. This yields (<ref>) when using $\ind_{\{1+a\geq c_t/(1-\mu)\}}$ for $\mu$ and $\eps$ sufficiently small as well. Together with (<ref>), this yields the desired result.

Combined with the analysis in case <ref>, and the fact that
(1+ζ_n/1-2ζ_n)^∑_h=1^k m_h(1+(n^-))=1+o(n^-β),
for some small $\beta>0$, by the choice of $\zeta_n$, and the fact that $m_t=\cO(\log n)$ for all $t\in[k]$, it follows that (<ref>) is at most $(o(n^{-\beta})\prod_{t=1}^k p_{m_t})$ for some small $\beta>0$ in both cases <ref> and <ref>. Finally, using this in (<ref>) yields
1/(n)_k∑_n^≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all  ℓ∈[k]≤∏_t=1^k (p_m_t(1+o(n^-β)))+o(n^-γ).
As we can choose $\gamma$ arbitrarily large (as discussed prior to (<ref>)), this term can incorporated in the $o(n^{-\beta})$ term regardless of the choice of $m_t$, which completes the proof of the upper bound.

Lower bound.
We then focus on proving a similar lower bound. We define the event

E^(2)_n:={∑_ℓ=k+1 ^j W_ℓ∈(W(1-ζ_n)j,W(1+ζ_n)j), for all  n^≤j≤n}.
We again have from Lemma <ref> in the [sec:appendix]Appendix that $\mathbb P((E^{(2)}_n)^c)=o(n^{-\gamma})$ for any $\gamma>0$. We obtain a lower bound for the probability of the event $\{\Zm_n(v_\ell)=m_\ell,\ell\in[k]\}$ by omitting the second term in (<ref>). This yields, together with the rearrangements in (<ref>),
1/(n)_k   ∑_n^≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all  ℓ∈[k]

≥   1/(n)_k∑_n^<j_1≠…≠j_k≤n ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
s≠i_ℓ,t,ℓ∈[m_t],t∈[k]^j_u+1(1-∑_ℓ=1^u W_j_ℓ/∑_ℓ=1^s-1W_ℓ)].
We again start by only considering the ordered indices $n^{\eps}<j_1<\ldots <j_k$ and also omit this sum for now for ease of writing. We also omit the constraint $s\neq i_{\ell,t},\ell\in[m_t],t\in[k]$ in the final product. As this introduces more terms smaller than one, we obtain a lower bound. Then, in the two denominators, we bound the vertex-weights $W_{j_1},\ldots, W_{j_k}$ from above and below by one and zero, respectively, to obtain a lower bound
1/(n)_k ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]𝔼[∏_t=1^k∏_s=1^m_tW_j_t/∑_ℓ=1^i_s,t-1W_ℓ_{ℓ≠j_t,t∈[k]}+k ∏_u=1^k∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_j_ℓ/∑_ℓ=1^s-1W_ℓ_{ℓ≠j_t,t∈[k]})].
As a result, we can now swap the labels of $W_{j_t}$ and $W_t$ for each $t\in[k]$, which again does not change the expected value, but it changes the value of the two denominators to $\sum_{\ell=k+1}^{i_{s,t}}W_\ell+k$ and $\sum_{\ell=k+1}^{i_{s,t}}W_\ell$, respectively. After this we introduce the indicator $\ind_{E^{(2)}_n}$ and use the bounds in $E^{(2)}_n$ on these sums in the expected value to obtain a lower bound. Finally, we note that the (relabelled) weights $W_t,t\in[k],$ are independent of $E^{(2)}_n$ so that we can take the indicator out of the expected value. Combining all of the above steps, we arrive at the lower bound

1/(n)_k     ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]𝔼[∏_t=1^k (W_t/W)^m_t ∏_s=1^m_t1/i_s,t(1+2ζ_n)
×∏_u=1^k∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_ℓ/(s-1)W(1-ζ_n))]ℙ(E^(2)_n).

The $1+2\zeta_n$ in the fraction on the first line arises from the fact that, for $n$ sufficiently large, $(i_{s,t}-1)(1+\zeta_n)+k\leq i_{s,t}(1+2\zeta_n)$. As stated above, $\mathbb P(E^{(2)}_n)=1-o(n^{-\gamma})$ for any $\gamma>0$. Similar to the calculations in (<ref>) and using $\log(1-x)\geq -x-x^2$ for $x$ small, we obtain an almost sure lower bound for the final product for $n$ sufficiently large of the form
∏_s=j_u+1^j_u+1(1-∑_ℓ=1^u W_ℓ/(s-1)W(1-ζ_n))   ≥exp(-1/W(1-ζ_n)∑_ℓ=1^u W_ℓ∑_s=j_u+1^j_u+1 1/s-1

-(1/W(1-ζ_n)∑_ℓ=1^u W_ℓ)^2∑_s=j_u+1^j_u+11/(s-1)^2)

≥(j_u+1/j_u)^-∑_ℓ=1^u W_ℓ/(W(1-ζ_n))(1-𝒪(n^-)).
Using this in (<ref>) yields the lower bound

1/(n)_k  ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k](1+2ζ_n)^-∑_h=1^k m_h 𝔼[∏_t=1^k (W_t/W)^m_t (j_t/n)^a_t∏_s=1^m_ti_s,t^-1 )](1-𝒪(n^-)),
where $\wt a_t:=W_t/(\E W(1-\zeta_n))$. As in the upper bound, we can take the product over $t\in[k]$ out of the expected value by the independence of the vertex-weights. This yields
1/(n)_k  ^*∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k](1-ζ_n/1+2ζ_n)^∑_h=1^k m_h∏_t=1^k 𝔼[ a_t^m_t (j_t/n)^a_t∏_s=1^m_ti_s,t^-1](1-𝒪(n^-)).
As $\zeta_n=n^{-\delta\eps}/\E W$ and $m_h=\cO(\log n)$ for all $h\in[k]$, the fraction and the $1-\cO(n^{-\eps})$ can be combined to yield a $1-o(n^{-\beta})$, for some small $\beta>0$. We now reintroduce the sum over the indices $n^{\eps}\leq j_1<\ldots<j_k\leq n$ and bound the sum over the  indices $i_{s,\ell}$ from below. We note that the expression in the expected value is  decreasing in $i_{s,\ell}$ and we restrict the range of the indices to $j_\ell+\sum_{h=1}^k m_h<i_{1,\ell}<\ldots< i_{m_\ell,\ell}\leq n,\ell \in[k]$, but no longer constrain the indices to be distinct (so that we can drop the $*$ in the sum). In the distinct sums and the suggested lower bound, the number of values the $i_{s,\ell}$ take on equal
∏_ℓ=1^k n-(j_ℓ-1)-∑_h=1^ℓ-1m_tm_h   and   ∏_ℓ=1^k n-(j_ℓ-1)-∑_h=1^k m_hm_ℓ,
respectively. It is straightforward to see that the former allows for more possibilities than the latter, as $\binom{b}{c}> \binom{a}{c}$ when $b> a\geq c$. As we omit the largest values of the expected value (since it decreases in $i_{s,\ell}$ and we omit the largest values of $i_{s,\ell}$), we thus arrive at the lower bound

((n)_k)^-1∑_n^<j_1<…<j_k≤n-∑_h=1^k m_h ∑_j_ℓ+∑_h=1^k m_h<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k] ∏_t=1^k𝔼[a_t^m_t (j_t/n)^a_t∏_s=1^m_t1/i_s,t](1-o(n^-β)),
where we also restrict the range of indices in the upper bound of the outer sum, as otherwise there would be a contribution of zero from these values of $j_1,\ldots,j_k$. We now use similar techniques compared to the upper bound of the proof to switch from summation to integration. First, we observe that we can switch the inner summation and the product over $t$. Second, we restrict the upper bound on the outer sum to $n-1-2\sum_{h=1}^k m_h$. This will prove useful later. Combined, this yields

((n)_k)^-1∑_n^<j_1<…<j_k≤n-1-2∑_h=1^k m_h∏_t=1^k ∑_j_ℓ+∑_h=1^k m_h<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]𝔼[a_t^m_t (j_t/n)^a_t∏_s=1^m_t1/i_s,t](1-o(n^-β)).
Then, we take the inner summation in the expected value and, for now, focus on
∑_j_t+∑_h=1^k m_h<i_1,t<…<i_m_ℓ,ℓ≤n
ℓ∈[k] ∏_s=1^m_ti_s,t^-1≥∫_j_t+∑_h=1^k m_h+1^n+1∫_x_1,t+1^n+1⋯∫_x_m_t-1,t+1^n+1∏_s=1^m_tx_s,t^-1 x̣_m_t,t…x̣_1,t.
Since $j_\ell\leq n-1-2\sum_{h=1}^k m_h$ for each $\ell\in[k]$, it follows in particular that $j_\ell+1+\sum_{h=1}^k m_h\leq n$. It thus follows that we can use (<ref>) in Lemma <ref> with $a=j_\ell+1+\sum_{h=1}^k m_h, b=n+1$, and $k=m_{\ell}$ to obtain the lower bound

∏_t=1^k 1/m_t!log(n+1/j_t +∑_h=1^k m_h+m_t)^m_t≥∏_t=1^k 1/m_t!(log(n/j_t +2∑_h=1^k m_h))^m_t.
Substituting this in (<ref>) yields the lower bound
1/(n)_k∑_n^<j_1<…<j_k≤n-1-2∑_h=1^k m_h ∏_t=1^k 𝔼[ (j_t/n)^a_ta_t^m_t/m_t!(log(n/j_t +2∑_h=1^k m_h))^m_t ](1-o(n^-β)).
Note that, due to the independence of the vertex-weights $W_1,\ldots, W_k$, and hence of $\wt a_1, \ldots, \wt a_k$, we can interchange the product and the sum with the expected value. To simplify the summation over $j_1,\ldots,j_k$, we write the summand as
∏_t=1^k(j_t+2∑_h=1^k m_h)^a_tn^-a_t/m_t!(log(n/j_t +2∑_h=1^k m_h))^m_t(1-2∑_h=1^k m_h/j_t +2∑_h=1^k m_h)^a_t.
Using that $m_t<c \log n,j_t\geq n^{\eps}$ and almost surely, $x^{\wt a_t}\geq x^{1/(\E W(1-\zeta_n))}$ for $x\in[0,1]$, we obtain the lower bound
∏_t=1^k (j_t+2∑_h=1^k m_h)^a_tn^-a_t/m_t!(log(n/j_t +2∑_h=1^k m_h))^m_t(1-o(n^-β)).
We can then shift the bounds on the range of the sum to $n^{\eps}+2\sum_{h=1}^k m_h$ and $n-1$. As $j_k=n$ yields a contribution of zero to the sum, we can increase the upper range on the summation from $n-1$ to $n$. We thus obtain the lower bound
1/(n)_k∑_n^+2∑_h=1^k m_h<j_1<…<j_k≤n∏_t=1^k (j_t/n)^a_t1/m_t!(log(n/j_t))^m_t (1-o(n^-β)).
We can now use a similar approach as in (<ref>) through (<ref>). By considering all permutations of the indices $j_1, \ldots, j_k$, we obtain
1/(n)_k   ∑_n^≤j_1≠…≠j_k≤n𝔼[_n(j_t)=m_t for all  t∈[k]]

≥1-o(n^-β)/(n)_k𝔼[∑_n^+2∑_h=1^k m_h<j_1≠…≠j_k≤n∏_t=1^k (j_t/n)^a_t1/m_t!(a_tlog(n/j_t))^m_t].
We now aim to again exchange the order of summation and the product in the expected value at the expense of some additional terms. To this end, we allow the indices $j_1, \ldots, j_k$ to take on the same values, but also subtract the largest terms from the sum to still obtain a lower bound. We are thus required to determine which terms are the largest. The following holds for any $t\in[k]$:  $j_t\mapsto (j_t/n)^{\wt a_t}(\wt a_t\log(n/j_t))^{m_t}/m_t!$ is increasing on $[1,n\exp(-m_t/\wt a_t))$ and decreasing on $(n\exp(-m_t/\wt a_t), n]$, with maximum value $\e^{-m_t}m_t^{m_t}/m_t!$. As such, we again distinguish the two cases <ref> and <ref> as in the upper bound (i.e. $m_t=c_t\log n+o(\log n)$ with either $c_t\leq 1/(\theta-1)$ for all $t \in [k]$ or $c_t>1/(\theta-1)$ for some $t \in [k]$). In case <ref>, we know that $n\exp(-m_t/\wt a_t)\leq n^{1-c_t(\theta-1)(1+o(1))}=o(1)$, so that $(j_t/n)^{\wt a_t}(\wt a_t\log(n/j_t))^{m_t}/m_t!$ is maximised for the smallest value of $j_t$. Omitting these terms thus yields a lower bound. In case <ref>, this is not the case, and hence we omit the largest terms at $n\exp(-m_t/\wt a_t)$.

Let us deal with case <ref> first. Since the sums contain
(n-⌈n^+∑_h=1^k m_h⌉+1)_k
many terms, we bound these sums from below by
∑_n^+∑_h=1^k m_h≤j_1≤n   ⋯∑_n^+∑_h=1^k m_h≤j_k≤n∏_t=1^k (j_t/n)^a_t/m_t!(a_tlog(n/j_t))^m_t

- ((n-⌈n^-∑_h=1^k m_h⌉+1)^k-1) ∏_t=1^k^-m_tm_t^m_t/m_t!

=   ∏_t=1^k (∑_n^+∑_h=1^k m_h≤j≤n(j/n)^a_t/m_t!(a_t log(n/j))^m_t)-(n^k-1),
where the last line follows from the fact that $\e^{-x} x^x/\Gamma(x+1)\leq 1$ for all $x>0$. We now identify the argument of the sum as $\Pf{P(\wt a_t,j)=m_t}$, where $P(\wt a_t)\sim \text{Poi}(\wt a_t \log(n/j))$. Again using the Poisson-gamma duality, we can rewrite this sum as
∑_n^+∑_h=1^k m_h≤j≤n   Y_t≤log(n/j), Y_t+V>log(n/j)

=∑_n^+∑_h=1^k m_h≤j≤n(Y_t≤log(n/j)-Y_t+V≤log(n/j)),
where $Y_t\sim \text{Gamma}(m_t, \wt a_t)$ and $V_t\sim \text{Exp}(\wt a_t)$ and both random variables are independent, conditionally on $W_t$. With a similar approach as in (<ref>) and (<ref>), we can bound this sum from below by
with $f(n):=\lceil n^\eps +\sum_{h=1}^k m_h\rceil$, $\wt f(n):=f(n)-1$. As $f(n)\sim \wt f(n)\sim n^\eps$, the desired lower bound follows in an analogous way to the approach used in the upper bound in (<ref>) through the paragraph following (<ref>).

In case <ref>, we can as in the upper bound assume without loss of generality that the condition on $c_t$ holds for all $t \in [k]$. Then, the largest values of $\Pf{P(\wt a_t,j)=m_t}$ are attained for $j_t$ as small as possible. So, by omitting these small $j_t$, we obtain the lower bound
∑_n^+∑_h=1^k m_h≤j_1≤n   ∑_n^+1+∑_h=1^k m_h≤j_1≤n⋯∑_n^+(k-1)+∑_h=1^k m_h≤j_k≤n∏_t=1^k P(a_t,j_t)=m_t

=∏_t=1^k (∑_n^+(t-1)+∑_ℓ=1^k m_ℓ≤j≤nP(a_t,j)=m_t).
As in case <ref>, we can write each sum as a difference of expected values. Then, following the same steps as in (<ref>) through (<ref>), we obtain the desired matching lower bound in case <ref> for $\eps,\beta>0$ sufficiently small. The only difference is that we cannot bound the  conditional probability in the second line (<ref>) from above by one. Instead, the lower bound we obtain is
n(a/1+a)^m_t[   1/1+aY'_t≤log(n/⌊n^+(t-1)+∑_ℓ=1^k m_ℓ⌋)

-Y”_t≥log(n/⌈n^+(t-1)+∑_ℓ=1^k m_ℓ⌉)-n^-a/1+a]

≥n[   1/1+a(a/1+a)^m_t(Y'_t≤log(n/⌊n^+(t-1)+∑_ℓ=1^k m_ℓ⌋)-(n^-))

From here on out, the same approach used to bound (<ref>) from above can be used to yield the lower bound
1/(n)_k∑_n^≤j_1≠…≠j_k≤n_n(j_ℓ)=m_ℓ for all  ℓ∈[k]≥∏_t=1^k p_m_t(1-o(n^-β)).
Combined with the upper bound, this yields the desired result and concludes the proof.

We now discuss the necessary changes to the proof for it to hold for the model with random out-degree, as introduced in Remark <ref>$(ii)$, as well. The main difference between these two models is the fact that the events $\{n\to i\}$ and $\{n\to j\}$ are no longer disjoint, where $u\to v$ denotes that vertex $u$ connects to vertex $v$ with an edge directed towards $v$. As a result, the probability, conditional on the vertex-weights, that vertex $n$ does not connect to vertices $j_1,\ldots, j_k\in[n-1]$ now equals

∏_ℓ=1^k (1-W_j_ℓ/S_n-1)    instead of    (1-∑_ℓ=1^k W_j_ℓ/S_n-1).
Moreover, as a new vertex can connect to multiple vertices at once, it is no longer necessary to restrict ourselves to indices $j_\ell<i_{1,\ell}<\ldots< i_{m_\ell,\ell}\leq n,\ell\in[k]$ with $i_{s,\ell}\neq i_{t,j}$ for any $\ell,j\in[k],s\in[m_\ell],t\in[m_j]$. Instead, when $\ell\neq j$, $i_{s,\ell}= i_{t,j}$ is allowed for any $s\in[m_\ell],t\in[m_j]$. That is, the steps at which two vertices increase their degree by one no longer need to be disjoint.

In the proof of the upper bound, this changes the right-hand side of (<ref>) into
1/(n)_k∑_n^≤j_1<…<j_k≤n ∑_j_ℓ<i_1,ℓ<…<i_m_ℓ,ℓ≤n,
ℓ∈[k]𝔼[   ∏_t=1^k∏_s=1^m_tW_j_t/∑_ℓ=1^i_s,t-1W_ℓ
where we change the last term in the expected value due to (<ref>) and omit the $*$ in the inner sum due to the degree increments no longer being disjoint. We can then again use the event $E_n^{(1)}$ to bound the denominators with deterministic quantities. Then, the exact same steps to obtain the upper bound as in (<ref>) can be performed. Most importantly, this yields that the difference in the upper bound due to (<ref>) is no longer present. Furthermore, as we omit the constraint of disjoint indices $i_{s,t}$ in (<ref>), we obtain the exact same upper bound as we would here. As a result, the remaining steps of the proof of the upper bound carry through as well.

The same is true for the lower bound. In fact, in the proof of the lower bound of Lemma <ref> we argue why we can omit the constraint of disjoint indices $i_{s,t}$ in a certain way and still obtain a lower bound in (<ref>), which is no longer necessary here. Hence, we obtain (<ref>) without the factor two in front of $\sum_{h=1}^k m_h$. This change carries through all the steps, so that we arrive at the same desired lower bound. Together with the upper bound, this establishes the desired result.

§.§ Proof of Lemma <ref>

We aim to bound

1/(n)_k∑_j∈I_n()_n(j_ℓ)=m_ℓ for all  ℓ∈[k],
where we recall that $I_n(\eps)$ from (<ref>). This is the equivalent of the steps following (<ref>) in the non-rigorous proof in Section <ref>. We first assume that $m_\ell=c_\ell \log n+o(\log n)$ for some $c_\ell\in[0,1/\log \theta)$ for all $\ell\in[k]$. We define
I_n(,i):={j∈I_n(): |{ℓ∈[k]: j_ℓ<n^}|=i},    i∈[k],
that is, $I_n(\eps,i)$ denotes the set of indices $\textbf{j}=(j_1,\ldots, j_k)$ such that exactly $i$ of the indices are smaller than $n^{\eps}$, and note that $I_n(\eps)=I_n(\eps,1)\cup\cdots\cup I_n(\eps,k)$. We then write
1/(n)_k∑_j∈I_n()_n(j_ℓ)=m_ℓ for all ℓ∈[k]=∑_i=1^k 1/(n)_k∑_j∈I_n(,i)_n(j_ℓ)=m_ℓ for all ℓ∈[k],
and bound the probability on the right-hand side from above by omitting all events $\{\Zm_n(j_\ell)=m_\ell\}$ whenever $j_\ell<n^{\eps}$. This leaves us with

∑_i=1^k-1 1/(n)_kn^i∑_S⊆[k]
|S|=k-i  ^*∑_n^≤j_ℓ≤n
ℓ∈S_n(j_ℓ)=m_ℓ for all ℓ∈S+n^k/(n)_k,
where we recall that the $*$ on the inner summation denotes that we only consider distinct values of $j_\ell,\ell\in S$. We isolate the case $i=k$ here as in this case no indices are larger than $n^{\eps}$ and we hence bound the probability from above by one, whereas $i=k$ would yield a contribution of zero in the triple sum. The inner sum can then be dealt with in the same manner as in the derivation of the upper bound in the proof of Lemma <ref>, to yield an upper bound
∑_i=1^k-1 n^-i (1-)∑_S⊆[k]
|S|=k-i∏_ℓ∈SW/W+W(W/W+W)^m_ℓ(1+o(n^-β))+2n^-k (1-),
for some $\beta>0$. It thus remains to show that for any $m_\ell=c_\ell \log n+o(\log n)$ with $c_\ell\in[0,1/\log \theta)$ we can take $\eps$ and a $\beta>0$ sufficiently small, such that
n^- (1-)=o(W/W+W(W/W+W)^m_ℓn^-β).
By Lemma <ref>, we have for any $\xi>0$ and $n$ sufficiently large, that

W/W+W(W/W+W)^m_ℓ≥(θ+ξ)^- m_ℓ=n^- c_ℓlog(θ+ξ)+o(1),
and $n^{- (1-\eps)}=o(n^{-\eta-c_\ell \log(\theta+\xi)+o(1)})$ when we choose $\eta,\xi,$ and $\eps$ sufficiently small, since $c_\ell \log \theta <1$ for any $\ell\in[k]$. As a result,
1/(n)_k∑_j∈I_n()_n(j_ℓ)=m_ℓ for all ℓ∈[k]=o(∏_ℓ=1^kW/W+W(W/W+W)^m_ℓn^-η).
We now assume (as before in the proof of Lemma <ref> without loss of generality) that $m_\ell=c_\ell \log n+o(\log n)$ with $c_\ell\in[1/\log \theta,\theta/(\theta-1))$ for all $\ell\in[k]$. In this case, the crude bound used above no longer suffices. Now, the aim is to combine the above with a similar approach as at the start of the proof of <cit.> and also use condition <ref> in Assumption <ref>. First, we consider the set of indices $I_n(\eps,k)$. To make use of the negative quadrant dependence of the degrees $(\zni)_{\inn}$  (see Remark <ref> and <cit.>), we create an upper bound by considering the event $\{\Zm_n(j_\ell)\geq m_\ell\text{ for all }\ell\in[k]\}$. Then, using the tail distribution and the negative quadrant dependency of the degrees under the conditional probability measure $\mathbb P_W$ yields
1/(n)_k∑_j∈I_n(,k)_n(j_ℓ)=m_ℓ for all ℓ∈[k]≤1/(n)_k∑_1≤j_1≠…≠j_k<n^∏_ℓ=1^k_n(j_ℓ)≥m_ℓ.
We then allow the indices $j_1,\ldots, j_k$ to take any value between $1$ and $n^{\eps}$, to obtain the upper bound
1/(n)_k∏_ℓ=1^k ( ∑_i<n^ ≥m_ℓ).
As in the proof of <cit.>, we apply a Chernoff bound to the conditional probability measure $\mathbb P_W$ to obtain
1/(n)_k𝔼[∏_ℓ=1^k ( ∑_i<n^ ≥m_ℓ)]≤1/(n)_k𝔼[∏_ℓ=1^k ( ∑_i<n^exp(m_ℓ(1-u_i,ℓ+logu_i,ℓ)))],

This is the equivalent of (<ref>) in the non-rigorous proof in Section <ref>. We then introduce the constants $\delta\in(0,1/2),C>kc_\theta^{-1} \theta \log(\theta)/(\theta-1)$, and $\alpha>0$ (with $c_\theta:=1/(2\theta^2)$). Also, we define the sequences $\zeta'_n:=(C\log n )^{-\delta/(1-2\delta)}/ \E W$, $f(n):=\lceil \log n/\log\log\log n\rceil$, and $g(n):=\lceil \log\log n\rceil$, $n\in\N$. We then define the events
E^(3)_n   :={∑_ℓ=1^j W_ℓ≥jW(1-ζ'_n), for all  (Clogn)^1/(1-2δ)≤j≤n},

E^(4)_n   :={S_⌈αlogn⌉≥clogn},

E^(5)_n   :={S_f(n)≥g(n)}.
The event $E^{(3)}_n$ is similar to the event $E^{(1)}_n$ introduced in (<ref>), but considers a larger range of indices $j$. The particular choice of the lower bound on the indices $j$ follows from the fact that we want as much control over the partial sums of the vertex-weights as possible, but need to ensure that $\mathbb P((E^{(3)}_n)^c)$ decays sufficiently fast. It follows that for all three events, the probability of their complement is $o(n^{-\gamma})$ for any $\gamma>0$ (in the case of $E^{(3)}_n$ and $E^{(4)}_n$ when we choose $C$ and $\alpha $ sufficiently large, respectively) by Lemma <ref> in the [sec:appendix]Appendix.

We can use these events in the expected value to arrive at the upper bound

1/(n)_k∏_ℓ=1^k ( ∑_i<n^exp(m_ℓ(1-u_i,ℓ+logu_i,ℓ)))_E^(3)_n∩E^(4)_n∩E^(5)_n+ℙ((E^(3)_n∩E^(4)_n∩E^(5)_n)^c).
By the proof of Corollary <ref> in the [sec:appendix]Appendix and since $m_\ell=c_\ell \log n+o(\log n)$ with $c_\ell>0$, we can bound $u_{i,\ell}$ from above uniformly in $i\in[n^\eps]$ and for any $\ell\in[k]$ by $(1+o(1))/(c_\ell\E W)$. Recalling that $\E W=\theta-1$ and that $c_\ell\geq 1/\log \theta>1/(\theta-1)$ (as $\theta>1$), we find that $u_{i,\ell}<1$ for all $i\in[n]$ and $\ell\in[k]$ as well. Since $x\mapsto 1-x+\log x$ is increasing on $(0,1)$ we can thus use this upper bound in the first term of (<ref>) to bound it from above by

1/(n)_k   ∏_ℓ=1^k ( ∑_i<n^exp(c_ℓlogn(1-1/c_ℓW+log(1/c_ℓW))(1+o(1))))

≤exp(logn(1+o(1))∑_ℓ=1^k (- (1-)+c_ℓ(1-1/c_ℓW+log(1/c_ℓW)))),
which is the equivalent of (<ref>) in the non-rigorous proof in Section <ref>. We then require that

exp(logn(1+o(1))∑_ℓ=1^k (- (1-)+c_ℓ(1-1/c_ℓW+log(1/c_ℓW))))=o(1/n^β∏_ℓ=1^k p_m_ℓ),
for some $\beta>0$. As, by Lemma <ref>, $p_{m_\ell}\geq (\theta+\xi)^{-m_\ell}=\exp(-\log n(1+o(1))c_\ell\log(\theta+\xi))$ for any $\xi>0$ and $n$ sufficiently large, it suffices to show that

∑_ℓ=1^k (- (1-)+c_ℓ(1-1/c_ℓW+log(1/c_ℓW)))<-∑_ℓ=1^k c_ℓlog(θ+ξ)-β,
when $\xi,\beta,$ and $\eps$ are sufficiently small. We show that this strict inequality can be achieved for each term individually, by arguing that we can choose $\eps\in(0,1)$ small enough such that
(1-)>c_ℓ(1-1/c_ℓ(θ-1)+log(θ+ξ/c_ℓ(θ-1))),    ℓ∈[k],
where we note that we have written $\E W$ as $\theta-1$. The right-hand side is increasing in $c_\ell$ when $c_\ell\in[1/\log\theta,\theta/(\theta-1))$, so that all $k$ inequalities are satisfied when we solve
with $\wt c:=\max_{\ell\in[k]}c_\ell$. We now show that the right-hand side is strictly smaller than one when $\xi$ is sufficiently small. We write
c(1-1/c(θ-1)+log(θ+ξ/c(θ-1)))   =c(1-1/c(θ-1)+log(θ/c(θ-1)))+clog(1+ξ/θ)

where the final upper bound follows from the fact that $\log(1+x)\leq x$ for $x>-1$ and $\wt c<\theta/(\theta-1)$. We denote the first term on the right-hand side by $\kappa=\kappa(\wt c,\theta)$. As $\kappa$ is increasing in $\wt c$ when $\wt c< \theta/(\theta-1)$ (which is the case when $c_\ell<\theta/(\theta-1)$ for all $\ell\in[k]$), we have $\kappa<1$, as $\wt c<\theta/(\theta-1)$. Thus, setting $\xi<(1-\kappa)(\theta-1)/2$ we achieve the desired result. Now, taking $\eps\in(0,1-(\kappa+\xi/(\theta-1)))$, we arrive at (<ref>) for some small $\eta>0$. Recalling that we can bound the second term in (<ref>) by $o(n^{-\gamma})$ for any $\gamma>0$ and that $p_{m_\ell}\geq n^{-\nu}$ for some $\nu>0$ uniformly in $m_\ell<c\log n$, we obtain

1/(n)_k∑_j∈I_n(,k)_n(j_ℓ)=m_ℓ for all ℓ∈[k]=o(n^-η∏_ℓ=1^k p_m_ℓ),
for some small $\eta>0$.

We now consider the remaining sets $I_n(\eps,1),\ldots, I_n(\eps,k-1)$ and aim to bound
1/(n)_k∑_i=1^k-1∑_j ∈I_n(,i)_n(j_ℓ)≥m_ℓ for all ℓ∈[k].
Again, using the negative quadrant dependence and introducing the events $E^{(1)}_n,E^{(3)}_n,E^{(4)}_n$, and $E^{(5)}_n$ yields the upper bound
1/(n)_k∑_i=1^k-1∑_j ∈I_n(,i)_E^(1)_n∩E^(3)_n∩E^(4)_n∩E^(5)_n∏_ℓ=1^k _n(j_ℓ)≥m_ℓ+(E^(1)_n∩E^(3)_n∩E^(4)_n∩E^(5)_n)^c.
The aim is to treat the probabilities of indices which are at most $n^{\eps}$ in the same way as when dealing with the indices in $I_n(\eps,k)$ to reach a bound as in (<ref>), for which we use the events $E^{(i)}_n, i=3,4,5$. For the indices which are larger than $n^{\eps}$ such an upper bound will not suffice. Instead, we aim to bound $\Pf{\Zm_n(j_\ell)\geq m_\ell}$ when $n^{\eps}\leq j_\ell\leq n$ in a similar way as we bounded $\Pf{\Zm_n(j_\ell)=m_\ell}$ from above in the proof of Lemma <ref>, for which we use the event  $E^{(1)}_n$.

First, we split the summation over $I_n(\eps,i)$ over all possible configurations of indices with are at most and at least $n^{\eps}$, similar to (<ref>). That is,
1/(n)_k   ∑_i=1^k-1∑_j ∈I_n(,i)_E^(1)_n∩E^(3)_n∩E^(4)_n∩E^(5)_n∏_ℓ=1^k _n(j_ℓ)≥m_ℓ

=   1/(n)_k∑_i=1^k-1∑_S⊆[k]
|S|=i ^*∑_1≤j_ℓ<n^
ℓ∈S ^*∑_n^≤j_ℓ≤n
ℓ∈[k]\S𝔼[_E^(1)_n∩E^(3)_n∩E^(4)_n∩E^(5)_n∏_ℓ∈S _n(j_ℓ)≥m_ℓ∏_ℓ∈[k]\S_n(j_ℓ)≥m_ℓ].
Using the events $E^{(i)}_n, i=3,4,5$, we can follow similar steps as above to bound the sum over the indices $j_\ell$ and the product of probabilities $\Pf{\Zm_n(j_\ell)\geq m_\ell}$ for $\ell\in S$ from above by the deterministic upper bound
exp(logn(1+o(1))∑_ℓ∈S (- (1-)+c_ℓ(1-1/c_ℓW+log(1/c_ℓW))))=:n^C(S)(1+o(1)),
which yields

|S|=in^C(S)(1+o(1)) ^*∑_n^≤j_ℓ≤n
We now proceed to bound each individual probability $\Pf{\Zm_n(j_\ell)\geq m_\ell}$ when $\ell \in [k]\backslash S$. This follows a similar approach to the upper bound of $\Pf{\Zm_n(j_\ell)=m_\ell}$ in the proof of Lemma <ref> (as well as the non-rigorous proof provided in Section <ref>), with a couple of modifications. Introducing indices $j_\ell<i_1<\ldots <i_{m_\ell}\leq n$, which denote the steps at which vertex $j_\ell$ increases its degree, we can write
_n(j_ℓ)≥m_ℓ=∑_j_ℓ<i_1<…<i_m_ℓ≤n∏_t=1^m_ℓ W_j_ℓ/∑_r=1^i_t-1W_r∏_s=j_ℓ+1
s≠i_t,t∈[m_ℓ]^i_m_ℓ-1(1-W_j_ℓ/∑_r=1^s-1 W_r).
The second product, in comparison to dealing with the event $\{\Zm_n(j_\ell)=m_\ell\}$, goes up to $i_{m_\ell}-1$ instead of $n$. This is due to the fact that we now only need to control the connections vertex $j$ does and does not make up to its $m_\ell^{\text{th}}$ connection. Using the same idea as in (<ref>) and using the event $E^{(1)}_n$, we obtain the upper bound
∑_j_ℓ<i_1<…<i_m_ℓ≤n   ∏_t=1^m_ℓ W_j_ℓ/(i_t-1)W(1-ζ_n)-1∏_s=j_ℓ+1^i_m_ℓ-1(1-W_j_ℓ/sW(1+ζ_n))

≤    ∑_j_ℓ<i_1<…<i_m_ℓ≤n∏_t=1^m_ℓ W_j_ℓ/i_tW(1-2ζ_n)∏_s=j_ℓ+1^i_m_ℓ-1(1-W_j_ℓ/sW(1+ζ_n)).
The last step follows from the fact that $(i_t-1)(1-\zeta_n)\E W-1\geq i_t(1-2\zeta_n)\E W$ for $n$ sufficiently large. Using this in the expected value of (<ref>) yields
ℓ∈[k]\S∏_ℓ∈[k]\S(∑_j_ℓ<i_1<…<i_m_ℓ≤n∏_t=1^m_ℓ W_j_ℓ/i_tW(1-2ζ_n)∏_s=j_ℓ+1^i_m_ℓ-1(1-W_j_ℓ/sW(1+ζ_n))).
We can now relabel the vertex-weights $W_{j_\ell}$ as $W_\ell$, $\ell\in [k]\backslash S$. This does not change the expected value and is possible since the indices $j_\ell$ are distinct for all $\ell\in [k]\backslash S$. Directly after this, we omit the requirement that the indices $j_\ell$ are distinct, which is now of no consequence as the weights have been relabelled already. We hence arrive at the upper bound

∏_ℓ∈[k]\S𝔼[∑_n^≤j_ℓ≤n ∑_j_ℓ<i_1<…<i_m_ℓ≤n∏_t=1^m_ℓ W_ℓ/i_tW(1-2ζ_n)∏_s=j_ℓ+1^i_m_ℓ-1(1-W_ℓ/sW(1+ζ_n))],
where the product can be taken out of the expected value due to the independence of the vertex-weights $W_1,\ldots W_\ell$. As a result, we can deal with each of expected values individually. Following the same approach as in (<ref>) and setting $a_\ell:=W_\ell/(\E W(1+\zeta_n))$, we obtain the upper bound

𝔼[   ∑_n^≤j_ℓ≤n ∑_j_ℓ<i_1<…<i_m_ℓ≤n∏_t=1^m_ℓ W_ℓ/i_tW(1-2ζ_n)(i_m_ℓ/j_ℓ)^-a_ℓ](1+𝒪(n^-))

=   𝔼[a_ℓ^m_ℓ∑_n^≤j_ℓ≤n ∑_j_ℓ<i_1<…<i_m_ℓ≤n∏_t=1^m_ℓ i_t^-1(i_m_ℓ/j_ℓ)^-a_ℓ](1+ζ_n/1-2ζ_n)^m_ℓ(1+𝒪(n^-)).
Let us first take out the term $(a_\ell j_\ell)^{ a_\ell}$ from the inner sums. We then observe that the summand of the inner sum over the indices $i_1,\ldots, i_{m_\ell}$ is decreasing, so that we can bound it from above almost surely by the multiple integrals
∫_j_ℓ^n ∫_x_1^n ⋯∫_x_m_ℓ-1^n ∏_t=1^m_ℓ-1x_t^-1 x_m_ℓ^-(1+a_ℓ) x̣_m_ℓ…x̣_1=a_ℓ^-m_ℓj_ℓ^-a_ℓ(1-(n/j_ℓ)^-a_ℓ∑_s=0^m_ℓ-1a_ℓ^s(log(n/j_ℓ))^s/s!).
The equality follows from (<ref>) in Lemma <ref> with $a=j_\ell, b=n, c=a_\ell$, and $k=m_{\ell}$.	Again reintroducing the term $a_\ell^{m_\ell}j^{a_\ell}$ in the expected value in (<ref>), we arrive at
where $P(a_\ell)\sim \text{Poi}(a_\ell \log(n/j_\ell))$, conditionally on $W_\ell$. With a similar duality between Poisson and gamma random variables, we obtain, as in (<ref>),
where $Y_\ell\sim \text{Gamma}(m_\ell,a_\ell)$, conditionally on $W_\ell$. Then, by the choice of $\zeta_n$, it follows that $((1+\zeta_n)/(1-2\zeta_n))^{m_\ell}=1+\mathcal O\big(n^{-\delta\eps}\log n \big)$. Using both these results in (<ref>), we arrive at

𝔼[∑_n^≤j_ℓ≤nY_ℓ≤log(n/j_ℓ)](1+𝒪( n^-δlogn )).
As the conditional probability is decreasing in $j_\ell$, we can bound the sum from above by an integral almost surely to obtain, as in (<ref>) and (<ref>),
∫_⌊n^⌋^n Y_ℓ≤log(n/x) x̣ ≤n^-Y_ℓ_{Y_ℓ≤log(n/⌊n^⌋)}≤n(a_ℓ/1+a_ℓ)^m_ℓ.
Combining this almost sure upper bound with (<ref>) in (<ref>), we arrive at

n^k-|S|∏_ℓ∈[k]\S (a_ℓ/1+a_ℓ)^m_ℓ(1+𝒪 (n^-δlogn)).
Finally, with the same steps as in (<ref>), we obtain
n^k-|S|∏_ℓ∈[k]\S (W/W+W)^m_ℓ(1+o(n^-β)),
for some small $\beta>0$. Using this bound in (<ref>) yields, for some constant $K>0$, the upper bound
By Remark <ref>, the tail probability $p_{\geq m_\ell}=\mathcal O(p_{m_\ell})$ and by (<ref>) we have
$n^{C(S)(1+o(1))}=o\big(n^{-\eta(S)}\prod_{\ell\in S}p_{m_\ell}\big)$ for some $\eta(S)>0$. Combined, this yields
1/(n)_k∑_i=1^k-1 ∑_j∈I_n(,i)_E^(3)_n_E_n^(1)∏_ℓ=1^k _n(j_ℓ)≥m_ℓ   ≤K∑_i=1^k-1∑_S⊆[k]

=o(n^-η∏_ℓ=1^k p_m_ℓ),
η:=min_ S⊆[k]
which is strictly positive when $\eps$ and $\xi$ are sufficiently small, similar to what is discussed above. Combining this with the fact that $\P{\big(E^{(1)}_n\cap E^{(3)}_n\cap E^{(4)}_n\cap E^{(5)}_n\big)^c}=o\big(n^{-\beta}\prod_{\ell=1}^k p_{m_\ell}\big)$ uniformly in $m_1,\ldots, m_k< c\log n$ for some $\beta>0$ by Lemma <ref>, and the result in (<ref>), we finally conclude,

1/(n)_k∑_j∈I_n()_n(j_ℓ)=m_ℓ for all ℓ∈[k]=   1/(n)_k∑_j∈I_n(,k)_n(j_ℓ)=m_ℓ for all ℓ∈[k]

+1/(n)_k∑_i=1^k-1∑_j∈I_n(,i)_n(j_ℓ)=m_ℓ for all ℓ∈[k]

=   o(n^-β∏_ℓ=1^k p_m_ℓ),
for some $\beta>0$ in the case that $m_\ell=c_\ell \log n+o(\log n)$ with $c_\ell\in[1/\log \theta, \theta/(\theta-1))$ for all $\ell\in[k]$ as well.

When the $m_\ell$ do not all behave the same, that is, for some $\ell\in[k]$ $c_\ell\in[0,1/\log \theta)$ and for some $c_\ell\in[1/\log \theta, \theta/(\theta-1))$, we can use a combination of the approaches outlined for either of the cases, which concludes the proof.

We now discuss the required adaptations so that the proof holds for the model with random out-degree as well. This follows from the fact that Lemma <ref> holds for this model, together with the fact that the degrees are still negatively quadrant dependent when the out-degree is random. As a result, all probabilities related to the degrees of multiple vertices can either be dealt with using Lemma <ref> or can be split as a product of probabilities of individual vertices. From the perspective of the in-degree of an individual vertex $i\in[n]$, the model with out-degree one and the model with random out-degree are equivalent, as in every step the in-degree of vertex $i$ increases by one with the same probability. Hence, the proof follows through in exactly the same way and Lemma <ref> holds for the model with random out-degree as well.

§.§ Proof of Proposition <ref>

We finally prove Proposition <ref>, using Lemmas <ref> and <ref>. We remark that the proof does not use that the out-degree is deterministic but uses (<ref>) only, so that the proof and hence (<ref>) hold for both the model with fixed and random out-degree.

As discussed before, (<ref>) directly follows from (<ref>) combined with Lemmas <ref> and <ref>. Using (<ref>), we then prove (<ref>). For ease of writing, we recall that
p_k:=θ-1/θ-1+W(W/θ-1+W)^k,  and     p_≥k:=(W/θ-1+W)^k.
We start by assuming that $m_\ell=c_\ell \log n+o(\log n)$ with $c_\ell\in(0,c)$ for each $\ell\in[k]$. We discuss how to adjust the proof when $m_\ell=o(\log n)$ for some or all $\ell\in[k]$ at the end.

For each $\ell\in [k]$ take an $\eta_\ell\in (0,c-c_\ell)$ so that $\lceil (1+\eta_\ell)m_\ell\rceil <c\log n$. Then, we use the upper bound

ℙ(   _n(v_ℓ)≥m_ℓ for all ℓ∈[k])

≤    ∑_j_1=m_1^⌊(1+η_1)m_1⌋⋯∑_j_k=m_k^⌊(1+η_k)m_k⌋_n(v_ℓ)=j_ℓ for all ℓ∈[k]

+∑_i=1^k _n(v_i)≥⌈(1+η_i)m_i⌉, _n(v_ℓ)≥m_ℓ for all ℓ≠i.
We first discuss the first term on the right-hand side. As (<ref>) holds uniformly in $m_1,\ldots, m_k$ $<c\log n$, we find

∑_j_1=m_1^⌊(1+η_1)m_1⌋⋯ ∑_j_k=m_k^⌊(1+η_k)m_k⌋_n(v_ℓ)=j_ℓ for all ℓ∈[k]   =∑_j_1=m_1^⌊(1+η_1)m_1⌋⋯ ∑_j_k=m_k^⌊(1+η_k)m_k⌋∏_ℓ=1^kp_j_ℓ(1+o(n^-β))

=∏_ℓ=1^k (p_≥m_ℓ-p_≥⌈(1+η_ℓ)m_ℓ⌉)(1+o(n^-β))

≤∏_ℓ=1^k p_≥m_ℓ(1+o(n^-β)).
To finish the upper bound, it remains to show that the term on the second line of (<ref>) can be incorporated in the $o\big(n^{-\beta}\big)$ term, and it suffices to show this can be done for each term in the sum, independent of the value of $i$. Using the negative quadrant dependence of the degrees under the conditional probability measure $\mathbb P_W$ (see Remark <ref> and <cit.>), we find

ℙ(_n(v_i)   ≥⌈(1+η_i)m_i⌉, _n(v_ℓ)≥m_ℓ for all  ℓ∈[k]\{i})

=   1/(n)_k∑_1≤j_1≠…≠j_k≤n𝔼[_n(j_i)≥⌈(1+η_i)m_i⌉∏_ℓ∈[k]\{i}_n(j_ℓ)≥m_ℓ]

=   1/(n)_k∑_j∈I_n()𝔼[_n(j_i)≥⌈(1+η_i)m_i⌉∏_ℓ∈[k]\{i}_n(j_ℓ)≥m_ℓ]

The first term in the last step can be included in the little $o$ term in (<ref>) (even when considering $m_i$ rather than $\lceil (1+\eta_i)m_i\rceil$ in the probability), as follows from computations similar to the ones in (<ref>) through (<ref>), combined with Remark <ref> (which states that $p_{\geq k}=\mathcal O(p_k)$). It remains to show that the same holds for the second term in the last step. Again, we use an argument similar to the steps performed in (<ref>) through (<ref>) to arrive at

1/(n)_k   ∑_n^≤j_1≠…≠j_k≤n𝔼[_n(j_i)≥⌈(1+η_i)m_i⌉∏_ℓ∈[k]\{i}_n(j_ℓ)≥m_ℓ]

for some positive constant $K$. By Lemma <ref> we have the inequalities
p_≥⌈(1+η_i)m_i⌉≤θ^-⌈(1+η_i)m_i⌉≤θ^-m_iθ^-η_im_i,  and  p_≥m_i≥(θ+ξ)^-m_i,
for any $\xi>0$. As a result, taking $\xi\in(0,\theta(\theta^{\eta_i}-1))$ and setting $\phi_i:=1-(1+\xi/\theta)\theta^{-\eta_i}>0$, we obtain

As $m_i=c_i\log n(1+o(1))$, it follows that $(1-\phi_i)^{m_i}=n^{-c_i\log (1/(1-\phi_i))(1+o(1))}$, so that
can be incorporated in the little $o$ term in (<ref>) for each $i\in[k]$ when we take a
$\beta'<\beta\wedge \min_{i\in[k]}c_i\log(1/(1-\phi_i))$. This yields

_n(v_ℓ)≥m_ℓ for all  ℓ∈[k]≤∏_ℓ=1^k (W/θ-1+W)^m_ℓ(1+o(n^-β')).
For a lower bound, we can omit the second line of (<ref>) and use (<ref>) to immediately obtain

_n(v_ℓ)≥m_ℓ for all ℓ∈[k]≥    ∑_j_1=m_1^⌊(1+η_1)m_1⌋⋯∑_j_k=m_k^⌊(1+η_k)m_k⌋_n(v_ℓ)=j_ℓ for all ℓ∈[k]

=    ∏_ℓ=1^k (p_≥m_ℓ-p_≥⌈(1+η_ℓ)m_ℓ⌉)(1+o(n^-β)).
Again using (<ref>) yields $p_{\geq m_\ell}-p_{\geq \lceil (1+\eta_\ell)m_\ell\rceil}=p_{\geq m_\ell}\big(1+o\big(n^{-\beta'}\big)\big)$ when we set
$\beta'<\beta\wedge \min_{i\in[k]} c_i\log(1/(1-\phi_i))$. Combined with (<ref>) this yields (<ref>) for the case $m_\ell=c_\ell\log n+o(\log n)$ with $c_\ell\in(0,c)$ for all $\ell\in[k]$.

When $c_\ell=0$ and thus $m_\ell=o(\log n)$ for some (or all) $i\in[k]$, a few minor alterations are required. Most importantly, we substitute the quantity $\lfloor(c/2)\log n\rfloor $ for $\lfloor (1+\eta_\ell)m_\ell\rfloor$ in all the steps. With this, the upper bound in (<ref>) follows directly. Similarly, the first term on the right-hand side of (<ref>) can be included in the little $o$ term in (<ref>), as the computations required (which are similar to those in (<ref>) through (<ref>)) include the case $m_\ell=o(\log n)$. We again use the upper bound in (<ref>) to obtain
1/(n)_k   ∑_n^≤j_1≠…≠j_k≤n𝔼[_n(j_i)≥⌈(c/2)logn⌉∏_ℓ∈[k]\{i}_n(j_ℓ)≥m_ℓ]

By Lemma <ref>, we obtain that the fraction is at most $\theta^{-(c/2)\log n}(\theta+\xi)^{m_i}\leq \theta^{-(c/4)\log n}=n^{-c\log(\theta)/4}$ for all $n$ sufficiently large, when $m_i=o(\log n)$. As a result, this term can be included in the $o(n^{-\beta})$ term in (<ref>) for any $i\in[k]$ such that $m_i=o(\log n)$, which proves the upper bound.

For the lower bound, we again substitute $\lfloor(c/2)\log n\rfloor$ for $\lfloor (1+\eta_i)m_i\rfloor$ when $m_i=o(\log n)$. In (<ref>), this yields a term
Again, the fraction is at most $n^{-\eta}$ for some $\eta>0$, which proves the lower bound and concludes the proof.

§ PROOFS OF THE MAIN THEOREMS

With the tools developed in Section <ref>, in particular Propositions <ref> and <ref> and Lemma <ref>, we now prove the main results formulated in Section <ref>.

First, we prove the main result for high degree vertices when the vertex-weight distribution has an atom at one, as in the <ref> case.

The proof follows the same approach as <cit.>. For an integer subsequence $(n_\ell)_{\ell\in\N}$ such that $\eps_{n_\ell}\to\eps$ as $\ell\to\infty$, it suffices to prove that for any $i<i'\in \Z$,
(X^(n_ℓ)_i,X^(n_ℓ)_i+1,…,X^(n_ℓ)_i'-1,X^(n_ℓ)_≥i')(𝒫^(i),𝒫^(i+1),…,𝒫^(i'-1),𝒫^([i',∞)))    as ℓ→∞holds. We obtain this via the convergence of the factorial moments of $X^{(n_\ell)}_i,\ldots,X^{(n_\ell)}_{i'-1},X^{(n_\ell)}_{\geq i'}$. Recall $r_k$ from (<ref>). By Proposition <ref>, for any non-negative integers $a_i,\ldots,a_{i'}$,
(X^(n_ℓ)_≥i')_a_i'∏_k=i^i'-1(X_k^(n_ℓ))_a_k=   (q_0θ^-i'+_n_ℓ)^a_i'∏_k=i^i'-1(q_0(1-θ^-1)θ^-k+_n_ℓ)^a_k

→    (q_0θ^-i'+)^a_i'∏_k=i^i'-1(q_0(1-θ^-1)θ^-k+)^a_k,
as $\ell\to\infty$. By using the properties of Poisson processes, it follows that the limit equals
due to the particular form of the intensity measure of the Poisson process $\mathcal P$ (which is used in the definition of the Poisson process $\mathcal P^\eps$). The result then follows from <cit.>.

For the results for the <ref> and <ref> cases, as outlined in Theorems <ref> and <ref>, respectively, we combine the asymptotic behaviour of $p_{\geq k}$ in Theorem <ref> with Proposition <ref> and Lemma <ref>.

To establish the convergence in probability, it follows from Lemma <ref> that we need only consider $n\P{\Zm_n(v_1)\geq k_n}$ for some adequate integer-valued $k_n$ such that $k_n<c\log n$ for some $c\in(0,\theta/(\theta-1))$ and where $v_1$ is a vertex selected from $[n]$ uniformly at random. By Proposition <ref>, this quantity equals $np_{\geq k_n}(1+o(1))$. Then, we use Theorem <ref> and Remark <ref> to obtain that, when $W$ satisfies the <ref> case in Assumption <ref>, this quantity is at most
nC  L(k_n)k_n^-(α-1)θ^-k_n,
where $\overline C>1$ is a constant. Now fix an arbitrary $\eta>0$ and set $k_n:=\lfloor \log_\theta n-(\alpha-1)(1-\eta) \log_\theta\log_\theta n\rfloor$. This yields

nC    L(log_θn(1+o(1)))(log_θn)^-(α-1)θ^-⌊log_θn-(α-1)(1-η) log_θlog_θn⌋(1+o(1))

≤C_2 L(log_θn)(log_θn)^-(α-1)(log_θn)^(α-1)(1-η)

Here, $\overline C_2>0$ is a suitable constant and we use that $k_n=\log_\theta n(1+o(1))$ in the first step. Furthermore, we use <cit.>, which states that for a slowly-varying function $\overline L$, $\overline L(\lambda x)/\overline L(x)$ converges to one uniformly in $\lambda$ on any interval $[a,b]$ such that $0<a\leq b<\infty$. As a result, $\overline L(\log_\theta n(1+o(1)))\leq c\overline  L(\log_\theta n)$ for some constant $c>1$ and $n$ sufficiently large. Finally, we use <cit.> to obtain that for any $\eta>0$, the final line of (<ref>) tends to zero with $n$. This shows that for any $\eta>0$, with high probability,
holds, due to the first result in Lemma <ref>. A similar approach, when setting $k_n:=\lfloor \log_\theta n-(\alpha-1)(1+\eta)\log_\theta \log_\theta n\rfloor$, yields
so that for any $\eta>0$, with high probability,
holds. Together, these two bounds prove the desired result.

The proof of this theorem follows a similar approach to the proof of Theorem <ref>. That is, we again apply the results from Theorem <ref> together with the fact that
for some adequate integer-valued $k_n$ such that $k_n<c\log n$ for some $c\in(0,\theta/(\theta-1))$, as follows from Proposition <ref> and Lemma <ref>. In the <ref>-<ref> sub-case, we know that

where we recall that $\gamma=1/(\tau+1)$. To prove the desired results, we first set $k_n=\lfloor \log_\theta n-(1+\eta)C_{\theta,\tau,c_1}(\log_\theta n)^{1-\gamma}\rfloor $ for any $\eta>0$, where we recall $C_{\theta,\tau,c_1}$ from (<ref>). Using this in (<ref>) then yields
np_≥k_n   = n/θ^k_n^-log(θ) C_θ,τ,c_1k_n^1-γ(1+o(1))≥^ηlog(θ) C_θ,τ,c_1(log_θn)^1-γ(1+o(1)),
where we use that $k_n^{1-\gamma}=(\log_\theta n)^{1-\gamma}(1+o(1))$ in the last step.	Hence, $n\P{\Zm_n(v_1)\geq k_n}$ diverges. We thus conclude from Lemma <ref> that
holds with high probability. A similar approach, setting
$k_n:=\lceil  \log_\theta n-(1-\eta)C_{\theta,\tau,c_1}(\log_\theta n)^{1-\gamma}\rceil$ and combining this with the first result of Lemma <ref> yields
holds with high probability. Together, these two bounds prove (<ref>).

To prove (<ref>) we apply the same methodology but use the asymptotic expression of $p_k$ (and $p_{\geq k}$ by adjusting constants), as in (<ref>). We recall the constants $C_1,C_2,C_3$ from (<ref>) and set $k_n=:\lceil \log_\theta n-C_1(\log_\theta \log_\theta n)^\tau+C_2(\log_\theta \log_\theta n)^{\tau-1}\log_\theta\log_\theta \log_\theta n+(C_3+\eta)(\log_\theta\log_\theta n)^{\tau-1}\rceil$, for any $\eta>0$. Then, (<ref>) yields
np_≥k_n= n/θ^k_n exp(-(logk_n/c_1)^τ(1+τ(τ-1)loglogk_n/logk_n-K_τ,c_1,θ/logk_n(1+o(1)))).
Using Taylor expansions, we obtain
-(logk_n/c_1)^τ=   -(loglog_θn/c_1)^τ+o(1)=-log(θ) C_1(log_θlog_θn)^τ+o(1),

τ(τ-1)/c_1^τ(logk_n)^τ-1loglogk_n=   τ(τ-1)/c_1^τ(loglog_θn)^τ-1logloglog_θn+o(1)

=   log(θ)C_2(log_θlog_θn)^τ-1log_θlog_θlog_θn

+ (log_θ(logθ))(logθ)^ττ(τ-1)/c_1^τ(log_θlog_θn)^τ-1+o(1),

-K_τ,c_1,θ/c_1^τ(logk_n)^τ-1=   -K_τ,c_1,θ/c_1^τ(loglog_θn)^τ-1+o(1)

=   -(logθ)^τ-1K_τ,c_1,θ/c_1^τ( log_θlog_θn)^τ-1+o(1),
where we recall $K_{\tau,c_1,\theta}$ from (<ref>) in Theorem <ref>. As a result,
n   exp(-(logk_n/c_1)^τ+τ(τ-1)/c_1^τ(logk_n)^τ-1loglogk_n-K_τ,c_1,θ/c_1^τ(logk_n)^τ-1(1+o(1)))θ^-k_n

= nexp(-log(θ) C_1(log_θlog_θn)^τ+log(θ)C_2 (log_θlog_θn)^τ-1log_θlog_θlog_θn

+log( θ) C_3 (log_θlog_θn)^τ-1(1+o(1)))θ^-k_n

≤exp(-(η-o(1)) (log_θlog_θn)^τ-1),
where in the last step we use that $k_n\geq \log_\theta n-C_1(\log_\theta \log_\theta n)^\tau+C_2(\log_\theta \log_\theta n)^{\tau-1}\log_\theta\log_\theta \log_\theta n+(C_3+\eta)(\log_\theta\log_\theta n)^{\tau-1}$. As the right-hand side tends to zero with $n$, Lemma <ref> yields for any fixed $\eta>0$, with high probability,
With a similar approach, setting
we can obtain that for any fixed $\eta>0$, with high probability,
Together these two bounds yield (<ref>), which concludes the proof.

We first prove the asymptotic distribution of the maximum degree, whose proof follows the same approach as the proof of <cit.>. We need to consider two cases: $i_n=\mathcal O(1)$ and $i_n\to\infty$ such that $i_n+\log_\theta n <(\theta/(\theta-1))\log n$ and $\liminf_{n\to\infty}i_n >-\infty$. For the former case, as $\exp(-q_0\theta^{-i_n+\eps_n})=\mathcal O(1)$, it suffices to prove
max_≥⌊log_θn⌋+i_n-(1-exp(-q_0θ^-i_n+_n))→0    as n→∞.
By the definition of $X^{(n)}_{\geq i}$ in (<ref>), this is equivalent to

X^(n)_≥i_n=0-exp(-q_0θ^-i_n+_n)→0    as n→∞.
This follows from Theorem <ref> and the subsubsequence principle. That is, if we assume the convergence in (<ref>) does not hold, then there exists a subsequence $(n_\ell)_{\ell\in\N}$ and a $\delta>0$ such that

X^(n_ℓ)_≥i_n_ℓ=0-exp(-q_0θ^-i_n_ℓ+_n_ℓ)>δ  ∀ ℓ∈.
However, as $\eps_{n_\ell}$ is bounded, there exists a subsubsequence $\eps_{n_{\ell_k}}$ such that $\eps_{n_{\ell_k}}\to\eps$ for some $\eps\in[0,1]$. Then, by Theorem <ref>, the statement in (<ref>) is false, from which the result follows.

In the latter case, we need only consider $\E{X^{(n)}_{\geq i_n}}$ and $\E{\big(X^{(n)}_{\geq i_n}\big)_2}$, as by <cit.>,

By Proposition <ref>, we have that
X^(n)_≥i_n=q_0θ^-i_n+_n(1+o(1)),    (X^(n)_≥i_n)_2=(q_0θ^-i_n+_n)^2(1+o(1)).
Hence, as $i_n\to\infty$ and $\eps_n$ is bounded,
X^(n)_≥i_n   =(1-exp(-q_0θ^-i_n+_n))(1+o(1)),
X^(n)_≥i_n-1/2 (X^(n)_≥i_n)_2   =(1-exp(-q_0θ^-i_n+_n))(1+o(1)).
Combining this with (<ref>) yields the desired result.

Recall $\eps_n:=\log_\theta n-\lfloor \log_\theta n\rfloor$. We now prove the limiting distribution of $|\M_{n_\ell}|$ has the desired distribution, as in (<ref>), when the subsequence $(n_\ell)_{\ell\in\N}$ is such that $\eps_{n_\ell}\to \eps\in[0,1]$, which follows the same approach as <cit.>. Consider the event $\mathcal E_{j,k}:=\{X^{(n_\ell)}_j=k, X^{(n_\ell)}_{\geq j+1}=0\}$ for $j\in\Z$ and $k\in\N$. $\mathcal E_{j,k}$ implies that there are exactly $k$ vertices which attain the maximum degree $\lfloor \log_\theta n\rfloor+j$ in the tree $T_{n_\ell}$. We observe that the events $\mathcal E_{j,k}$ are pairwise disjoint for different values of $j$. As a result, we obtain the following inequalities: For any $M\in\N$,
|_n_ℓ|=k=ℙ(⋃_j∈ℰ_j,k)   ≤ℙ(⋃_j≤-(M+1) ℰ_j,k)+∑_j=-M^M-1ℰ_j,k+ℙ(⋃_j≥Mℰ_j,k)

By Theorem <ref> it thus follows that
lim sup_n_ℓ→∞|_n_ℓ|=k   ≤lim inf_M∈(X_≥-M^=0+∑_j=-M^M-1X_j^=k,X^_≥j=0+X^_≥M>0),

lim inf_n_ℓ→∞|_n_ℓ|=k   ≥lim sup_M∈∑_j=-M^M X^_j=k,X^_≥j+1=0,
where $X_j^\eps\sim \text{Poi}\big(q_0(1-\theta^{-1})\theta^{-j+\eps}\big)$ and $X^\eps_{\geq j}\sim\text{Poi}\big(q_0\theta^{-j+\eps}\big)$ are independent Poisson random variables, for $j\in\Z$. As a result,
X_≥-M^=0   =^-q_0θ^M+,     X^_≥M>0=1-^-q_0θ^-M+,

X^_j=k, X^_≥j+1=0   =X^_j=kX^_≥j+1=0=1/k!(q_0(1-θ^-1)θ^-j+)^k^-q_0θ^-j+.
Hence, we obtain
lim sup_n_ℓ→∞|_n_ℓ|=k   ≤lim inf_M∈(^-q_0θ^M++∑_j=-M^M-11/k!(q_0(1-θ^-1)θ^-j+)^k^-q_0θ^-j++1-^-q_0θ^-M+)

lim inf_n_ℓ→∞|_n_ℓ|=k   ≥lim sup_M∈∑_j=-M^M1/k!(q_0(1-θ^-1)θ^-j+)^k^-q_0θ^-j+

It is then readily checked that the limit is indeed finite and that summing over all $k\in\N$ yields one, which concludes the proof.

The proof follows the same argument as the proof of <cit.>, which is based on <cit.>. Let $1\leq a\leq b$ be integers. Then, by Proposition <ref> and since $i_n=o(\log n)$,
It then remains to show that the right-hand side is in fact $o(\theta^{i_nb})$. We note that $i_n=o(\log r_{\log_\theta n}\wedge \log n)$, so that we can write the right-hand side as
𝒪((r_log_θn)^1-i_nalogθ/logr_log_θn∨n^-β-i_nalogθ/logn)=𝒪((r_log_θn)^1-o(1)∨n^-β-o(1)) =o(θ^i_nb),
by the constraints on $i_n$, from which the result follows.

§ TECHNICAL DETAILS OF EXAMPLES

In this section we discuss some technical details of the examples discussed in Section <ref>. In particular, for each example we provide a precise asymptotic expression of $p_k$ and $p_{\geq k}$ as well as a key element that leads to the results in Section <ref>. That is, for each of the examples we state and prove the analogue of Proposition <ref>. The three theorems presented in each of the examples in Section <ref> mimic three of the theorems presented in Section <ref>. That is, Theorems <ref> and <ref> are the analogue of Theorems <ref>, Theorems <ref> and <ref> are the analogue of Theorem <ref>, and Theorems <ref> and <ref> are the analogue of Theorem <ref>. As a result, their proofs are very similar to the proofs of Theorems <ref>, <ref>, and <ref>,  so we omit proving the theorems stated in Section <ref>.

§.§ Example <ref>, beta distribution

Let $W$ be beta distributed, i.e. its distribution function satisfies (<ref>) for some $\alpha,\beta>0$. We prove a result on (the tail of) the limiting degree distribution and provide additional building blocks required to prove the results in Example <ref>.

Let the distribution of $W$ satisfy (<ref>) for some $\alpha,\beta>0$ and recall $p_k,p_{\geq k}$ from (<ref>). Then,

p_k   = Γ(α+β)/Γ(α)(1-θ^-1)^1-βk^-βθ^-k(1+𝒪(1/k)),

p_≥k   =Γ(α+β)/Γ(α) (1-θ^-1)^-β k^-βθ^-k(1+𝒪(1/k)).

Note that this lemma improves on the bounds in (<ref>) by providing a precise multiplicative constant, rather than two slowly-varying functions that are (possibly) of different order.

By the distribution of $W$, we immediately obtain that
p_k   =∫_0^1 (θ-1)x^k (θ-1+x)^-(k+1)Γ(α+β)/Γ(α)Γ(β)x^α-1(1-x)^β-1 x̣

=(θ-1)^-kΓ(α+β)/Γ(α)Γ(β)∫_0^1 x^k+α-1(1-x)^β-1(1+x/(θ-1))^-(k+1) x̣,