# Degree limit theorems for P.A random graphs with edge-steps

Caio Alves1 1 Institute of Mathematics, University of Leipzig – Augustusplatz
10, 04109 Leipzig
e-mail<EMAIL_ADDRESS>,  Rodrigo Ribeiro2 2 PUC Chile, Av.
Vicuña Mackenna 4860, Macul, La Florida, Región Metropolitana, Chile.
e-mail<EMAIL_ADDRESS>and  Daniel Valesin3 3 Department of
Mathematics,Johann Bernoulli Institute. University of Groningen Nijenborgh 9,
9747AG Groningen The Netherlands
e-mail<EMAIL_ADDRESS>
(Date:
1 Institute of Mathematics, University of Leipzig
2 Facultad de Matemáticas, PUC Chile, Pontificia Universidad Católica de
Chile.
3 Department of Mathematics,Johann Bernoulli Institute. University of
Groningen. )

###### Abstract.

In this work we investigate a random graph model that combines preferential
attachment and edge insertion between previously existing vertices. The
probabilities of adding either a new vertex or a new connection between
previously added vertices are time dependent and given by a function $f$
called the edge-step function. We prove convergence theorems and a CLT for the
properly scaled maximum degree, as well as the degree of any given vertex. Our
results state that under a summability condition, the maximum degree grows
linearly in time and sub-linearly if this condition is dropped. Our condition
for linearity is sharp when $f$ is a regularly varying function at infinity.
Moreover, as a byproduct of our analysis, we prove that there exists true
competition for the leadership only during a finite number of steps, i.e.,
after a certain point a single vertex becomes the one with maximum degree and
maintains this predominance forever. These results also relate to Pólya urns
with immigration. We also explore our knowledge about the maximum degree in
order to understand infectious process over the graphs generated by this
model. We show that for some choices of the parameters the graphs are highly
susceptible to the spread of infections, which requires only $4$ steps to
infect a positive fraction of the whole graph.

###### Key words and phrases:

preferential attachment, random graphs, Póya urns, maximum degree, Karamata’s
theory, regular varying function, CLT, LIL, concentration bounds

###### 2010 Mathematics Subject Classification:

Primary 05C82; Secondary 60K40, 68R10

##  1\. Introduction

The random graph theory started with work of P. Erdős and A. Rényi [12] in the
1960’s. The original model generates homogeneous graphs, i..e, graphs whose
vertices are statistically indistinguishable. However, in the late 90’s, the
capacity of analyzing large amount of data brought to light many
characteristics of concrete networks, which were not captured by the graphs
generated by the ER-model. The empirical works of S. H. Strogatz and D. J.
Watts in [19] and of A-L. Barabási and R. Álbert in [4] showed that real-life
networks are not homogeneous. Their works coined the concepts of scale-free
(graphs with degree distribution following power-laws), small-worlds (small
diameter graphs), hubs (the existence of very high degree vertices) and boost
the investigation of non-homogeneous random graph models.

Since then, many non-homogeneous random graph models have been proposed, many
of them are generalizations of the Barabási-Álbert model, which proposed the
preferential attachment rule as mechanism for breaking vertices homogeneity
present in ER-model and variants. The works on the area have been devoted to
understand the degree distribution [6], the asymptotic behavior of the maximum
degree [16, 15], the diameter order [21] and other graph observables. We refer
the reader to the book of R. van der Hofstad [20] and of R. Durrett [10] for a
wide and rigorous introduction to many important random graph models.

Furthermore, since non-homogeneous graphs represent well real-life phenomena,
they also become the natural environment to consider some kind of random
process, for instance, infectious process like bootstrap percolation. See the
recent works of M. Amin Abdullah and N.Fountoulakis [3] for example of
infectious process on graphs generated by the preferential attachment
mechanism and how the spread relates to the degree distribution and maximum
degree.

It is also noteworthy that the degree analysis on such class of evolving graph
models is closely related to generalizations of the classical bin-and-ball
model proposed by G. Póya and F. Eggenberger in [11] , since the evolution of
the degree does not require any information of the graph’s geometry, thus they
may be seen as a kind of Póya-Eggenberguer urn scheme. See Section 2, where we
discuss how the graph model investigated here relates to recent works on Póya-
Eggenberguer urn models.

The first part of this work is devoted to investigate (non)-asymptotic
behavior of the maximum degree of a random graph model. In the second part we
investigate how the maximum degree impacts on the geometry of the graph. More
precisely, we study a bootstrap percolation model over the random graphs. In
order to proper state and discuss our results, we will define formally our
random graph model.

###  1.1. The model

The model depends on a real non-negative function $f$, called edge-step
function, with domain given by the semi-line $[1,\infty)$ such that
$||f||_{\infty}\leq 1$. Without loss of generality, we will start the process
from an initial graph $G_{1}$ which is the graph with one vertex and one loop.
As the process evolves, one of the two graph stochastic operations below may
be performed on the present graph $G$:

  * •

Vertex-step \- Add a new vertex $v$ and add an edge $\\{u,v\\}$ by choosing
$u\in G$ with probability proportional to its degree. More formally,
conditionally on $G$, the probability of attaching $v$ to $u\in G$ is given by

$P\left(v\rightarrow u\middle|G\right)=\frac{\mathrm{degree}(u)}{\sum_{w\in
G}\mathrm{degree}(w)}.$ (1)

  * •

Edge-step \- Add a new edge $\\{u_{1},u_{2}\\}$ by independently choosing
vertices $u_{1},u_{2}\in G$ according to the same rule described in the
vertex-step. We note that both loops and parallel edges are allowed.

We let $\\{Z_{t}\\}_{t\geq 1}$ be independent sequence of random variables
such that $Z_{t}\stackrel{{\scriptstyle\tiny d}}{{=}}\mathrm{Ber}(f(t))$. We
then define a markovian random graph process $\\{G_{t}(f)\\}_{t\geq 1}$ as
follows: begin with initial state $G_{1}$. Given $G_{t}(f)$, obtain
$G_{t+1}(f)$ by either performing a vertex-step on $G_{t}(f)$ when $Z_{t}=1$
or performing an edge-step on $G_{t}(f)$ when $Z_{t}=0$.

###  1.2. Regularity conditions

Again, in order state and discuss properly our results we will need t
introduce some regularity conditions for the functions $f$. Some of theses
conditions have the objective of preventing pathological examples, for
instance if one drop monotonicity is possible to construct $f$ such that the
sequence of graphs $\\{G_{t}(f)\\}_{t\in\mathbb{N}}$ has two sub sequences of
graphs: one similar to the BA random tree and the other one a quasi-complete
graph, see the discussion in Section 8 of [diameter].

Some of our results will require information about the asymptotic behavior of
$f$ and for this reason a wide class of functions will play important role:
the regularly varying functions. We say that a positive function $f$ is a
regularly varying function (r.v.f for short) at infinity with index of regular
variation $-\gamma$, for some $\gamma>0$, if

$\lim_{t\to\infty}\frac{f(at)}{f(t)}=a^{-\gamma},$

for all $a>0$. The special case $\gamma=0$ is called slowly varying function.
Below we define the conditions over $f$ that will be useful to our purposes.
For $p\in[0,1]$, we define two conditions

$f\equiv p;$ (Consp) $f\text{ decreases to }p.$ (Dp)

The two summability conditions bellow will be important to us

$\sum_{s=1}^{\infty}f(s)=\infty.$ (V∞)

The above condition relates to expected number of vertices. Since at each step
$s$ we add a vertex with probability $f(s)$, the above condition tells us that
the process keeps introducing new vertices into the graph.

$\sum_{s=1}^{\infty}\frac{f(s)}{s}<\infty.$ (S)

Whenever (S) does not hold for a specific $f$, we say that $f$ satisfies (S)c.
For any $\gamma\in[0,1]$, we let ${\rm RES}(-\gamma)$ be the following class
of functions

$\begin{split}\mathrm{RES}(-\gamma):=\left\\{f:[1,\infty]\longrightarrow[0,1]\;\middle|\;f\text{
satisfies (D)}_{0}\text{ and is r.v.f with index
}-\gamma\right\\}.\end{split}$ (RES)

###  1.3. Main results

In this paper we investigate the evolution of degree of a fixed vertex and of
the maximum degree. We prove non-asymptotic estimates and limit theorems:
almost surely convergence and CLT. We also study the implications of the
emergence of vertices with extremely high degree in the geometry of the graphs
and in the spread of infectious over them.

####  1.3.1. Limit Theorems for the Maximum Degree

Beyond the degree distribution, the maximum degree has been studied in the
context of non-homogeneous random graphs. In [15], Y. Malyshkin and E.
Paquette prove almost surely convergence of a evolving tree model which
combines the PA-rule (1) with local choice. Their result shows that by some
choices of the parameter the maximum degree is linear in $t$. This contrasts
with the results of T. Móri, [16], for the affine version of the BA-model,
which shows that scaled by $t^{1/(2+\beta)}$, where $\beta$ is the
attractiveness constant, the maximum degree converges to a strictly positive
random variable $\mu$.

In our settings, the right order of the maximum degree depends on $f$ and it
is related to the summability condition (S). Our results state that (S) is a
sharp condition for linearity, i.e., the maximum degree is of linear order if
and only if $f$ satisfies (S). The dependence of $f$ is expressed in the
normalizing factor $\phi$ defined below:

$\phi(t)=\phi(t,f):=\prod_{s=1}^{t-1}\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right).$
(2)

Then, our limit theorems regarding the max. degree are the following ones

######  Theorem 1.1 (Convergence of the Maximum degree).

Let $f$ be an edge-step function such that either $f$ belongs to
$\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$, or $f$ is identically equal to
$p\in(0,1]$. Then for every $q\geq 1$, there exists a finite random variable
$\mu$ such that

$\lim_{t\to\infty}\frac{{\rm
maxdegree}\\{G_{t}(f)\\}}{\phi(t)}=\mu,\quad\mathbb{P}\text{ -a.s. and in
}L_{q}(\mathbb{P}).$ (3)

Furthermore, $\mu$ is $\mathbb{P}$-a.s. strictly positive.

The limit distribution $\mu$ assumes a specific form: it is the supremum of a
sequence of distributions $\zeta_{i}$, where $\zeta_{i}$ is the limit of the
properly scaled degree of the $i$-th vertex added by the process.

Our next result states that condition (S) is a sharp condition in order to
obtain a maximum degree which grows linearly in time:

######  Corollary 1.2 (Sharp condition for linear max. degree).

Let $f$ be an edge-step function in ${\rm RES}(-\gamma)$, with
$\gamma\in[0,1)$. Then, there exists a strictly positive random variable $\nu$
such that

$\lim_{t\to\infty}\frac{{\rm
maxdegree}\\{G_{t}(f)\\}}{t}=\nu,\quad\mathbb{P}\text{ -a.s}$

if and only if $f$ satisfies condition (S).

Finally, we also prove a Central Limit Theorem for the maximum degree when $f$
is a decreasing regularly varying function at infinity, here we use the
notation $X_{n}\implies X$ for convergence in distribution.

######  Theorem 1.3 (CLT for the maximum degree).

Let $f$ be an edge-step function such that either $f$ belongs to
$\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$ or $f$ is constant and equal to
$p\in(0,1]$. Denoting by $\mathcal{N}$ a normal random variable, independent
from $\mu$, with expectation $0$ and variance $1$, we have

  * (a)

if (S)c holds, then

$\sqrt{\phi(s)}\left(\frac{{\rm
maxdegree}\\{G_{t}(f)\\}}{\phi(t)}-\mu\right)\implies\sqrt{\mu}\mathcal{N};$
(4)

  * (b)

if (S) holds, then, denoting

$\xi(\infty)=\lim_{s\to\infty}\phi(s)s^{-1},$

we have

$\sqrt{\phi(s)}\left(\frac{{\rm
maxdegree}\\{G_{t}(f)\\}}{\phi(t)}-\mu\right)\implies\sqrt{\mu\left(1-\frac{\xi(\infty)}{2}\mu\right)}\mathcal{N}.$
(5)

We note that (114) also applies when the hypotheses of (113) are assumed,
since in that case $\xi(\infty)=0$. We chose to state the Theorem above
separating in the different cases in order to highlight the effect that the
convergence of $\sum_{s\geq 1}f(s)/s$ has on the result.

####  1.3.2. The Persistent Leadership

As part of our analysis, we investigate the competition for degree. Our result
shows that true competition holds only for a finite number of steps and
eventually a fixed vertex takes the leadership over becoming the only one with
maximum degree.

######  Theorem 1.4 (The Persistent Leadership).

Consider a edge-step function $f$ such that either $f$ belongs to
$\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$ or $f$ is constant and equal to
$p\in(0,1]$. Denote by $U_{max}(s,N)$ the event where at time $s$ there exists
a unique vertex with maximum degree and all other vertices have degree smaller
than the maximum minus $N\in\mathbb{N}$. Then $U_{max}(s,N)$ occurs for all
but a finite number of integers $s$ almost surely.

Besides being a key step in the proof of Theorem 1.3, the above theorem is
interesting by itself, since it also states that once a vertex becomes the
leader, it becomes greater than its adversaries “by far”, i.e., the difference
between the leader’s degree and the second place is greater than large
constants after certain point.

####  1.3.3. Application: Bootstrap Percolation

As an application of our results regarding the degree, we analyze the
Bootstrap Percolation model over the graphs generated by $f\in{\rm
RES}(-\gamma)$, with $\gamma\in[0,1)$ and under condition (S). Our estimates
allow us to construct structures on the graph $G_{t}(f)$ that make it highly
susceptible to the spread of infections.

More rigorously, given a finite graph $G=(V(G),E)$, a number $a\in[0,|V(G)|]$,
and an integer $r\geq 2$, we define the bootstrap percolation measure
$\mathbb{Q}_{G,a,r}$ on $G$ with threshold $r$ and rate of infection $a$ in
the following manner:

  * •

Each vertex $v\in V(G)$ is  _infected_ at round $0$ independently of the
others with probability $a|V(G)|^{-1}$. The collection of all infected
vertices at round $0$ is denoted by $\mathcal{I}_{0}$.

  * •

At round $s\in N$, every vertex sending at least $r$ edges to some vertex( or
vertices) in $\mathcal{I}_{s-1}$ becomes infected.

  * •

We let $\mathcal{I}_{\infty}$ be the set of all infected vertices when the
process stabilizes, that is,

$\mathcal{I}_{\infty}=\cup_{s\geq 0}\mathcal{I}_{s}.$

In [3] the authors study the bootstrap percolation process on the preferential
attachment random graph where each vertex has $m\in\mathbb{N}$ outgoing edges
with end vertices chosen according to an affine preferential attachment rule,
that is, the PA rule in (1) but with a $\delta>-m$ summed in both the
numerator and denominator. There they prove the existence of a  _critical
function_ $a_{t}^{c}:\mathbb{N}\to\mathbb{R}_{+}$ such that the bootstrap
percolation process on this random graph at time $t$ with threshold $r\leq m$
and rate $a_{t}\gg a_{t}^{c}$ infects the whole graph with high probability,
but the same process with rate $a_{t}^{\prime}\ll a_{t}^{c}$ dies out without
before infecting a positive proportion of the graph, also with high
probability.

In our context it is not possible for the infection to spread to the whole
graph due to the existence of many vertices with degree smaller than $r$ at
all times. We therefore turn the problem into asking if $\mathcal{I}_{\infty}$
eventually encompasses a set with positive density in the vertex set. In this
sense, we show in our next result that the bootstrap percolation is always
supercritical for the graph $G_{t}(f)$, with $f$ under (S), i.e., every
unbounded rate sequence gives rise to set of infected vertices with positive
density:

######  Theorem 1.5 (The outbreak phenomenon).

Let $f$ be an edge-step function in ${\rm RES}(-\gamma)$, with
$\gamma\in[0,1)$, and satisfying summability condition (S). Then, for any
sequence $(a_{t})_{t\in\mathbb{N}}$ increasing to infinity and all $t$
sufficiently large, there exists a collection of graphs $\mathcal{G}_{t}$ and
a $f$ dependent constant $C>0$ such that,

$\mathbb{P}\left(G_{t}(f)\in\mathcal{G}_{t}\right)=1-o(1)$ (6)

and for all $G\in\mathcal{G}_{t}$ the bootstrap percolation process on $G$
with parameters $a_{t}$ and $r\geq 2$ satisfies

$\mathbb{Q}_{G,a_{t},r}\left(|\mathcal{I}_{\infty}|\geq
C|V(G)|\right)=1-o(1).$ (7)

The above theorem illustrates how interconnected $G_{t}(f)$ is. From the
definition of the bootstrap percolation on $G_{t}(f)$ follows that the initial
infected set $\mathcal{I}_{0}$ is essentially $a_{t}$. Thus, by Theorem 1.5
one can choose $a_{t}$ of order arbitrarily smaller than the expected number
of vertices in $G_{t}(f)$, as long as it increases to infinity, even so the
infection manages to spread to a positive fraction of the whole graph, with
high probability.

###  1.4. Notation and conventions

####  1.4.1. Graph theory

We will use integer letters like $i$ and $j$ to denote the $i$-th and $j$-th
vertices added by the process. And will denote their degrees in $G_{t}(f)$ by

$d_{t}(i):=\text{ degree at time }t\text{ of vertex }i.$

It will be important to understand the evolution of increment process, so we
define the following notation

$\Delta x_{t}:=x_{t+1}-x_{t}.$

For $r\in\mathbb{R}$, we also let $V_{r}(f)$ denote the number of vertices of
the process up to time $\lfloor r\rfloor$, that is,

$V_{r}(f):=\left|V\left(G_{\lfloor r\rfloor}(f)\right)\right|.$

Note that $V_{r}(f)$ is the sum of $\lfloor r\rfloor$ independent random
variables.

####  1.4.2. Special functions and asymptotics

We define the functions $F:\mathbb{R}\to\mathbb{R}$ and
$F^{-1}:\mathbb{R}\to\mathbb{R}$ by

$F(r):=\sum_{1\leq s\leq r}f(s);\quad\quad
F^{-1}(r):=\inf_{s\in\mathbb{R}}\\{F(s)\geq r\\}.$ (8)

Notice that $\mathbb{E}[V_{r}(f)]=F(r)$, and since we are assuming $f(s)$ to
be strictly positive for all $s$, and since $\|f\|_{\infty}\leq 1$, we have
that

$r\leq F(F^{-1}(r))\leq r+1,\quad\text{ and }\quad r\leq F^{-1}(F(r))\leq
r+1.$ (9)

We will make use of the Bachman-Landau notation $o/O/\omega$, which in general
assumes some asymptotic in time $t$. When the asymptotic is on another
parameter we will indicate it on the sub index, for instance $o_{n}(1)$.

We will write $a_{t}\sim b_{t}$ if $a_{t}/b_{t}$ converges to $1$ as $t$ goes
to infinity. The arrows $a_{t}\downarrow a$ and $a_{t}\searrow a$ will mean
that $(a_{t})_{t}$ decreases to $a$ as $t$ goes to infinity.

####  1.4.3. General notation

Throughout the text $\mathcal{F}_{0}\subset\mathcal{F}_{1}\subset\cdots$ will
stand for the natural filtration, i.e., $\mathcal{F}_{t}$ contains all the
information about the process up to time $t$.

###  1.5. Organization of the paper

In Section 2, we discuss the main ideas behind the proof of the CLT for the
maximum degree and how the analysis of the degree of a vertex relates to new
kinds of Póya-Eggenberguer urn models. In Section 3 we prove useful non-
asymptotic bounds for the degree of a vertex and the maximum degree, as well.
We then move to Section 4, where we prove convergence theorems for the scaled
degree and maximum degree. We also prove some results for the limit
distribution. Section 5 is crucial for the proof of the CLT for the maximum
degree. In this section we study how evolves the competition for degree. We
prove that only one vertex becomes the one with maximum degree. In Section 6
we prove CLT using the results developed in the previous section. Finally, in
Section 7 we investigate the bootstrap percolation process over the random
graphs.

##  2\. Generalized Pólya Urn Models and Technical Ideas

In order to prove convergence theorems for the properly scaled maximum degree
an intermediate step is to prove convergence theorems for the degree of a
fixed vertex. In this intermediate step the convergence of the scaled degree
comes from martingale results, i.e., we prove that degree properly scaled is a
martingale. The convergence in $L_{q}$ is proven by looking to a family of
martingales involving the degree of a vertex which gives moments bounds. The
proofs of this intermediate steps follow the arguments present in [16],
however, the presence of the edge-step and the degree of generality we work on
let our expressions more involved, preventing a straightforward application of
the results of T. Móri. The convergence of the maximum degree properly scaled
is then obtained using the moment bounds and the fact that being the maximum
of martingales, it is a submartingale.

The proof for the Central Limit Theorem for the normalized maximum degree is
more involved in our settings. Again an intermediate step is to prove CLT for
the properly scaled degree of a fixed vertex. And again, the edge step makes
the computations complicated and a particular analysis is required. Once we
have the CLT for the degree of a fixed vertex, the key step is to prove the
persistent leadership, i.e., after a certain random time (which is not a
stopping time) the maximum degree behaves like the degree of a single vertex
and then on this event the analysis done for the degree of a vertex may be
generalized to the maximum degree.

The proof of the persistent leadership makes clear the difference between the
model with edge-step functions and the other preferential attachment ones in
which a single vertex of degree one is added every step. In the latter case
the persistent leadership may be obtained applying classical results from the
Póya-Eggenberger theory. Suppose one desires to keep track on the evolution of
the degree of a fixed vertex $j$. Then, its possible to ignore the graph
geometry entirely and see the degree from a balls-and-bins perspective: see
the degree of $j$ as the red balls and the degree of the remaining vertices as
the blue ones. Or, if one just wants to compare the degree of fixed vertices,
consider the evolution of the degrees only at times one of them has been
chosen (observe that in this case only and only can be chosen) then we obtain
a Póya urn scheme and by classical results it follows that the proportion of
red/blue balls converges to an absolute continuous distribution, thus they
cannot be equal.

In our case, the urn schemes that emerge are somewhat related to the recent
work of E. Pekös, A. Röllin and N. Ross in [17] which accommodates the
possibility of immigration (as they have called) at random times, i.e., at
random times we simply add some number of blue balls to the urn. More
precisely, the balls-and-bins approach for the degree of a fixed vertex yields
to the following balls and bills model. We begin with a bin containing $r$ red
balls and $b$ blue balls. Then, the process evolves from time $t$ to $t+1$ in
the following way:

  * •

Immigration step: Perform a regular Pólya-Eggenberger urn step and add a new
blue ball;

  * •

Non-immigration step: Perform two regular Pólya-Eggenberger urn steps
independently.

Then, with probability $f(t+1)$ we perform an immigration step and with
probability $1-f(t+1)$ we perform a non-immigration step. This way, the
proportion of red balls is the degree of $j$ divided by the total number of
edges. But different from [17], in our case the time increment between the
addition of a foreign blue ball and another one is not identically
distributed.

Just to point out, our results show that for $f$ under condition (S) the
proportion of red balls converges (a.s. and in $L_{q}$) to a strictly positive
random variable $\zeta_{j}$. We also prove that there is no dominance, i.e.,
the probability of $\zeta_{j}$ being equal $1$ is zero. On the other hand, if
$f$ does not satisfy (S), there is dominance of the blue ones. Thus, in this
case the question is the right order of magnitude of number of red balls.

Thus, in order to prove the persistent leadership (Theorem 1.4), which is
crucial for the CLT for maximum degree, we first prove Lemma 5.1 which is a
Law of the Iterated Logarithm for the process

$|d_{t}(i)-d_{t}(j)|$

seen in certain random times. The idea is that if, let’s say $i$, has degree
much larger than $j$, then is hard for $j$ to catch up $i$ before $i$
increases its degree again. This “much larger” has to be precisely
$\omega(\sqrt{t})$. We prove such LIL using Freedman’s results for bounded
increment (sub,super)-martingales. The application of such results requires
bounds over the conditional expectation and variance of our process, which may
be cumbersome due to the presence of the edge-step rule. Finally, using the
LIL and the idea that is too expensive to catch up an adversary whenever its
degree is already too large we prove Lemma 5.2 which states that

$\lim_{t\to\infty}|d_{t}(i)-d_{t}(j)|=\infty,\;\mathbb{P}-\text{a.s.}$

And this Lemma is crucial to prove that eventually there exists only one
vertex having the maximum degree.

Finally, since our analysis require information on the asymptotic behavior of
$f$, part of our results relies on theorems of the Karamata’s Theory.

##  3\. Bounds for the degrees

In this section we prove useful bounds for the degree of a fixed vertex. Since
the $i$-th is added at a random time, it will be needed to control this random
time. We define the variable $\tau(i)$

$\tau(i):=\inf\\{s\geq 1:V_{s}(f)=i\\},$ (10)

i.e., $\tau(i)$ is the time the $i$-th vertex was added by the process. Recall
that the increment of the degree of a vertex at each step may be one or two.
In the first case we may either add a new vertex to the graph and connect it
to $i$, or we may add a new edge and choose $i$ to be one of its endvertices.
In the later case, we add a new edge to the graph and choose $i$ twice, adding
a loop to it. This yields the formula, on the event where $s>\tau_{i}$,

$\begin{split}\mathbb{E}\left[\Delta
d_{s}(i)\middle|\mathcal{F}_{s}\right]&=f(s+1)\frac{d_{s}(i)}{2s}+2\left(1-f(s+1)\right)\frac{d_{s}(i)}{2s}\left(1-\frac{d_{s}(i)}{2s}\right)+2\left(1-f(s+1)\right)\Bigg{(}\frac{d_{s}(i)}{2s}\Bigg{)}^{2}\\\
&=\left(\frac{1}{s}-\frac{f(s+1)}{2s}\right)d_{s}(i),\end{split}$

which in turn implies

$\begin{split}\mathbb{E}\left[d_{s+1}(i)\mathds{1}\\{\tau(i)=t_{i}\\}\middle|\mathcal{F}_{s}\right]&=\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right)d_{s}(i)\mathds{1}\\{\tau(i)=t_{i}\\}.\end{split}$
(11)

We let $d_{s}(i)\equiv 0$ in the event where $s<\tau_{i}$. We then have that

$X_{s}=X_{s,i,t_{i}}:=\frac{d_{s}(i)}{\phi(s)}\mathds{1}\\{\tau(i)=t_{i}\\}$
(12)

is a martingale for $s\geq t_{i}$ with expectation
$\phi(t_{i})^{-1}\cdot\mathbb{P}[\tau(i)=t_{i}]$. We now apply Freedman’s
inequality (Theorem A.2) to a related martingale in order to obtain an upper
bound for the degree that holds with very high probability.

######  Lemma 3.1.

Let $f$ be an edge-step function such that $f(t)\searrow 0$ as $t$ goes to
infinity. Then there exists a $f$-dependent constant $C_{f}>0$ such that, for
every $\alpha>1$,

$\mathbb{P}\left(\exists s\in\mathbb{N}\text{ such that
}d_{s}(i)\geq\alpha\frac{\phi(s)}{\phi(t_{i})}\middle|\tau(i)=t_{i}\right)\leq\exp\\{-C_{f}\cdot\alpha\\}.$
(13)

###### Proof.

As stated before, we use Freedman’s inequality. Given some real number
$\lambda>\phi(t_{i})^{-1}$, we define the stopping time

$\eta=\eta(\lambda):=\inf_{s\in\mathbb{N}}\\{X_{s}\geq\lambda\\}.$

Consider the measure $\mathbb{P}_{i,t_{i}}$, the probabilty measure associated
with the process conditioned on the event $\\{\tau(i)=t_{i}\\}$, and let
$\mathbb{E}_{i,t_{i}}$ be the associate expectation. Under this measure we
will bound the increment and the sum of the conditional expectation of the
squares of the increments of $X_{s\wedge\eta}$, which continues to be a
martingale under $\mathbb{P}_{i,t_{i}}$. We have, by (11), on the event
$\\{\tau(i)=t_{i}\\}$,

$\begin{split}\left|\Delta
X_{s\wedge\eta}\right|&=\mathds{1}\\{\lambda>s\\}\left|\frac{d_{s+1}(i)}{\phi(s+1)}-\frac{d_{s}(i)}{\phi(s)}\right|\\\
&=\frac{\mathds{1}\\{\lambda>s\\}}{\phi(s+1)\phi(s)}\left|\phi(s)d_{s+1}(i)-\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right)\phi(s)d_{s}(i)\right|\\\
&=\mathds{1}\\{\lambda>s\\}\left|\frac{\Delta
d_{s}(i)}{\phi(s+1)}-\frac{(2-f(s+1))d_{s}(i)}{2s\phi(s+1)}\right|.\end{split}$

Since $d_{s}(i)\leq s$ and $\Delta d_{s}(i)\leq 2$, the above equation implies
that, almost surely,

$\left|\Delta X_{s\wedge\eta}\right|\leq\frac{3}{\phi(t_{i})}.$ (14)

Furthermore, since for any $a,b\in\mathbb{R}$ it holds that $(a+b)^{2}\leq
2a^{2}+2b^{2}$, and since

$\Delta d_{s}(i)\leq 2\cdot\mathds{1}\\{\text{the degree of }i\text{ is
increases at time }s\\},$

we have

$\begin{split}\mathbb{E}_{i,t_{i}}\left[\Delta
X_{s\wedge\eta}^{2}\middle|\mathcal{F}_{s}\right]&\leq\mathds{1}\\{\lambda>s\\}\cdot\mathbb{E}_{i,t_{i}}\left[\frac{8\Delta
d_{s}(i)}{\phi(s+1)^{2}}+\frac{d_{s}(i)^{2}}{s^{2}\phi(s+1)^{2}}\middle|\mathcal{F}_{s}\right]\\\
&\stackrel{{\scriptstyle\eqref{eq:inccondexp2}}}{{\leq}}\mathds{1}\\{\lambda>s\\}\cdot\left(\frac{8d_{s}(i)}{s\phi(s+1)^{2}}+\frac{d_{s}(i)^{2}}{s^{2}\phi(s+1)^{2}}\right)\\\
&\leq\frac{9\lambda}{s\phi(s+1)}.\end{split}$ (15)

Consider the function $\xi:\mathbb{N}\to\mathbb{R}$ is defined by

$\xi(s):=\frac{\phi(s)}{s}=\prod_{r=1}^{s-1}\frac{r}{r+1}\prod_{r=1}^{s-1}\left(1+\frac{1}{r}-\frac{f(r+1)}{2r}\right)=\prod_{r=1}^{s-1}\left(1-\frac{f(r+1)}{2(r+1)}\right).$
(16)

We may write $\xi$ as

$\xi(s)=\exp\left\\{\sum_{r=1}^{s-1}\log\left(1-\frac{f(r+1)}{2(r+1)}\right)\right\\}=\exp\left\\{\sum_{r=1}^{s-1}\left(-\frac{f(r+1)}{2(r+1)}+O(r^{-2})\right)\right\\}.$
(17)

Therefore $\xi$ is a slowly varying function as long as $f(t)$ goes to zero as
$t$ goes to infinity, since for any $a\in\mathbb{R}_{+}$,

$\begin{split}\frac{\xi(as)}{\xi(s)}&=\exp\left\\{\sum_{r=\lceil
as\rceil}^{s-1}\left(\frac{f(r+1)}{2(r+1)}+O(r^{-2})\right)\right\\}\\\
&\leq\exp\left\\{C\cdot as^{-1}+\frac{\inf_{r\geq as}f(r)}{2}\left(\log s-\log
as\right)\right\\}\\\ &\leq C\exp\left\\{-\frac{\inf_{r\geq
as}f(r)}{2}\left(\log a\right)\right\\}\\\
&\xrightarrow{s\to\infty}1.\end{split}$ (18)

This fact together with Karamata’s Theorem (B.3) (Proposition $1.5.8$ of [5])
implies

$\begin{split}\sum_{s=1}^{t-1}\mathbb{E}_{i,t_{i}}\left[\Delta
X_{s\wedge\eta}^{2}\middle|\mathcal{F}_{s}\right]\leq\sum_{s\geq
t_{i}}\mathbb{E}_{i,t_{i}}\left[\Delta
X_{s\wedge\eta}^{2}\middle|\mathcal{F}_{s}\right]\leq C\sum_{s\geq
t_{i}}\frac{\lambda}{s^{2}\xi(s)}\leq
C\frac{\lambda}{t_{i}\xi(t_{i})}=C\frac{\lambda}{\phi(t_{i})},\end{split}$
(19)

where the constant above is $f$-dependent. Since $s\wedge\eta$ is a finite
stopping time, by the Optional Stopping Theorem we have
$\mathbb{E}[X_{s\wedge\eta}]=\mathbb{E}[X_{t_{i}}]=\phi(t_{i})^{-1}$. Applying
Freedman’s inequality and using the above bound together with (14), we obtain,
for any $A>0$,

$\mathbb{P}_{i,t_{i}}\left(X_{s\wedge\eta}-\frac{1}{\phi(t_{i})}\geq
A\right)\leq\exp\left\\{\frac{-A^{2}}{\frac{C\lambda}{\phi(t_{i})}+\frac{2A}{\phi(t_{i})}}\right\\}\leq\exp\left\\{\frac{-A^{2}\phi(t_{i})}{C\lambda+2A}\right\\}.$
(20)

Letting now $A=\lambda-\phi(t_{i})^{-1}$, recalling that
$\lambda>\phi(t_{i})^{-1}$, we obtain, setting $\alpha=\lambda\phi(t_{i})$,

$\begin{split}\mathbb{P}_{i,t_{i}}\left(\exists s\in\mathbb{N}\text{ such that
}d_{s}(i)\geq\alpha\frac{\phi(s)}{\phi(t_{i})}\right)&\leq\mathbb{P}_{i,t_{i}}\left(\eta<\infty\right)\\\
&=\lim_{s\to\infty}\mathbb{P}_{i,t_{i}}\left(\eta\leq s\right)\\\
&=\lim_{s\to\infty}\mathbb{P}_{i,t_{i}}\left(X_{s\wedge\eta}\geq\frac{\alpha}{\phi(t_{i})}\right)\\\
&\leq\exp\left\\{-C\alpha\right\\},\end{split}$ (21)

finishing the proof of the result.

∎

We now work in the direction of obtaining an analogous bound to the above
result without the dependence on $t_{i}$. The idea is elementary: the variable
$\tau(i)$ concentrates strongly around its mean, so paying a small price we
may ignore all possible times $t_{i}$ that are far away from said mean. Our
next result uses this fact in order to obtain a lower bound for $\tau_{i}$
with high probability.

######  Lemma 3.2.

Consider $f$ either in $\mathrm{RES}(\gamma)$ with $\gamma\in[0,1)$ or
identically equal to $p\in(0,1]$. Then there exists a constants $C_{f}>0$ such
that for $i\in\mathbb{N}$

$\mathbb{P}\left(\tau(i)\leq\frac{F^{-1}(i)}{2}\right)\leq
C_{f}^{-1}\exp\left\\{-C_{f}\cdot i\right\\}.$ (22)

###### Proof.

If $f\equiv p$, then the result follows by an elementary Bernstein bound.
Assume then that $f\in\mathrm{RES}(\gamma)$. By Corollary B.2, we know that
$f(t)=\ell(t)t^{-\gamma}$ with $\ell$ being a slowly varying function. Theorem
B.3 implies that as $r\to\infty$, using the monotonicity of $f$ to approximate
the integral by the sum,

$F(r/2)=\sum_{s=1}^{\lfloor
r/2\rfloor}f(s)=\frac{1}{2}\sum_{s=1}^{r}\ell(s)t^{-\gamma}\sim\frac{1}{1-\gamma}\ell(r/2)\frac{r^{1-\gamma}}{2^{1-\gamma}}\sim\frac{F(r)}{2^{1-\gamma}},$
(23)

where we also used the fact that $\ell$ is slowly varying to obtain
$\ell(r/2)\sim\ell(r)$. Letting

$i_{*}=\frac{F^{-1}(i)}{2}$

and recalling that $V_{r}(f)$ is a sum of independent random variables, we may
use the above equation, (9), and an elementary Chernoff bound to obtain

$\begin{split}\mathbb{P}\left(\tau(i)\leq\frac{F^{-1}(i)}{2}\right)&=\mathbb{P}\left(V_{i_{*}}(f)\geq
i\right)\\\
&=\mathbb{P}\left(V_{i_{*}}(f)\geq\left(1+\left(iF\left(\frac{F^{-1}(i)}{2}\right)^{-1}-1\right)\right)\mathbb{E}\left[V_{i_{*}}(f)\right]\right)\\\
&\leq\exp\left\\{-\frac{1}{3}\left(iF\left(\frac{F^{-1}(i)}{2}\right)^{-1}-1\right)F\left(\frac{F^{-1}(i)}{2}\right)\right\\}\\\
&\leq\exp\left\\{-\frac{1}{3}\left((3/2)^{1-\gamma}-1\right)\frac{i}{2^{1-\gamma}}\right\\},\end{split}$
(24)

for sufficiently large $i$. By adjusting the constant we can then show (22)
for every $i\geq 1$. ∎

We can now prove the next result:

######  Theorem 3.3.

Consider $f$ either in $\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$ or
identically equal to $p\in(0,1]$. Then there exists a constant $C_{f}>0$ such
that, for every $\alpha>1$,

$\mathbb{P}\left(\exists s\in\mathbb{N}\text{ such that
}d_{s}(i)\geq\alpha\frac{\phi(s)}{\phi\left(F^{-1}(i)\right)}\right)\leq
C_{f}^{-1}\left(\exp\left\\{-C_{f}\cdot
i\right\\}+\exp\left\\{-C_{f}\cdot\alpha\right\\}\right).$ (25)

###### Proof.

We first assume that $f\in\mathrm{RES}(\gamma)$.

$\frac{\phi\left(\frac{F^{-1}(i)}{2}\right)}{\phi\left(F^{-1}(i)\right)}=\prod_{s=\frac{F^{-1}(i)}{2}}^{F^{-1}(i)-1}\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right)^{-1}\geq
Ce^{-\log 2}>0$ (26)

uniformly in $i$. By monotonicity and the union bound we obtain

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}\left(\exists
s\in\mathbb{N}\text{ such that
}d_{s}(i)\geq\alpha\frac{\phi(s)}{\phi\left(F^{-1}(i)\right)}\right)$\mbox{}\hfil\phantom{********}\\\
&\leq\mathbb{P}\left(\tau(i)\leq\frac{F^{-1}(i)}{2}\right)\\\
&\quad+\mathbb{P}\left(\exists s\in\mathbb{N}\text{ such that
}d_{s}(i)\geq\alpha\frac{\phi\left(\frac{F^{-1}(i)}{2}\right)}{\phi\left(F^{-1}(i)\right)}\frac{\phi(s)}{\phi\left(\frac{F^{-1}(i)}{2}\right)}\middle|\tau(i)=\frac{F^{-1}(i)}{2}\right),\end{split}$
(27)

The result for $f\in\mathrm{RES}(\gamma)$ then follows after using lemmas 3.1
and 3.2, taking the smallest among the constants there defined and absorbing
into it the lower bound in (26). For $f\equiv p$, Theorem $3$ of [1] already
implies the result. ∎

######  Remark 3.4.

We note that the bound in (25) is sharp in the sense that the order of
$\mathbb{E}[d_{s}(i)]$ is already $\phi(s)/\phi(F^{-1}(i))$.

We end the section with results on lower bounds for the degree. This type of
result cannot be as strong as the upper bounds discussed above, since we may
pay a relatively small price in order to make a vertex $i$ behave like it was
born much after its mean appearance time $\mathbb{E}[\tau(i)]$. We can however
obtain stronger results when dealing with the _total degree of a collection of
vertices_. This in turn gives us good lower bounds for the degree of some
random vertex, by the pigeonhole Principle. This is the subject of our next
result.

######  Theorem 3.5.

Let $f$ be an edge-step function such that either $f(t)$ goes to zero as $t$
goes to infinity or $f(t)\equiv p\in(0,1]$. Then, for every $N\in\mathbb{N}$,
there exists $C_{f}>0$ depending on $f$ only such that

$\begin{split}\mathbb{P}\left(\forall t\in\mathbb{N},\exists
i\in\\{1,2,\cdots,N\\}\text{ such that
}d_{t}(i)\geq\frac{\phi(t)}{\phi(N)}\right)&\geq
1-\exp\\{-C_{f}N\\}.\end{split}$ (28)

Furthermore, there exists almost surely a random integer $N_{0}\geq 0$ such
that for every $t\geq N_{0}$, there exists at least one vertex $i$ in
$G_{t}(f)$ such that

$d_{t}(i)\geq\frac{\phi(t)}{\phi(N_{0})}.$ (29)

###### Proof.

Fix $N\in\mathbb{N}$ and denote by $\\{\tilde{X}_{N,s}\\}_{s\geq N}$ the
process

$\tilde{X}_{N,s}:=\frac{\sum_{i=1}^{N}d_{s}(i)\mathds{1}\\{\tau(i)\leq
N\\}}{\phi(s)},$ (30)

i.e., $\tilde{X}_{N,s}$ denotes the sum of the degree of all vertices added by
the process up to time $N$ normalized by $\phi(s)$. By an argument analogous
to the one following equation (11), it follows that
$\\{\tilde{X}_{N,s}\\}_{s\geq N}$ is a positive martingale such that

$\mathbb{E}\tilde{X}_{N,s}=\tilde{X}_{N,N}\equiv\frac{2N}{\phi(N)},$ (31)

since at time $N$ the sum of the degree of all vertices added up to this time
equals twice the number of edges, which is $N$. Moreover, since we can update
the degree of at most two vertices by an amount of at most $2$, it follows
that $\\{\tilde{X}_{N,s}\\}_{s\geq N}$ also has bounded increments. More
precisely, proceeding as in equation (3) we obtain

$\left|\Delta\tilde{X}_{N,s}\right|\leq\frac{3}{\phi(s+1)}.$ (32)

If $f(t)$ goes to zero as $t$ goes to infinity, then, by a similar argument as
in (19), using the fact that $\xi^{-2}$ is also a slowly varying function, we
obtain

$\sum_{s=N}^{t}\left|\Delta\tilde{X}_{N,s}\right|^{2}\leq
C\sum_{s=N}^{t}s^{-2}\xi(s)^{-2}\leq\frac{C}{N\xi(N)^{2}}=\frac{C}{\phi(N)\xi(N)}.$
(33)

If $f(t)\equiv p\in(0,1]$, then, by (17),

$\xi(s)=\exp\left\\{\sum_{r=1}^{s-1}\left(-\frac{f(r+1)}{2(r+1)}+O(r^{-2})\right)\right\\}\geq
Cs^{-p/2}.$

Therefore, in this case,

$\sum_{s=N}^{t}\left|\Delta\tilde{X}_{N,s}\right|^{2}\leq
C\sum_{s=N}^{t}s^{-2+p}\leq\frac{C}{N^{1-p}}.$ (34)

Now we proceed as in the proof of the upper bound, this time stopping our
martingale when it becomes unexpectedly small. For this, let $\eta$ be the
stopping time below

$\eta:=\inf_{s\geq N}\left\\{\tilde{X}_{N,s}\leq\frac{N}{\phi(N)}\right\\}.$
(35)

Again by the Optional Stopping Theorem, it follows that
$\\{\tilde{X}_{N,s\wedge\eta}\\}_{s\geq N}$ is a martingale having the same
expected value as $\\{\tilde{X}_{N,s}\\}_{s\geq N}$. Thus, by Azuma’s
inequality, we obtain

  1. (i)

if $\lim_{t\to\infty}f(t)=0$,

$\mathbb{P}\left(\tilde{X}_{N,s\wedge\eta}\leq\frac{2N}{\phi(N)}-\frac{N}{\phi(N)}\right)\leq\exp\left\\{-C\frac{N^{2}}{\phi(N)^{2}}\phi(N)\xi(N)\right\\}\leq\exp\left\\{-CN\right\\};$
(36)

  2. (ii)

if $f(t)\equiv p$,

$\mathbb{P}\left(\tilde{X}_{N,s\wedge\eta}\leq\frac{2N}{\phi(N)}-\frac{N}{\phi(N)}\right)\leq\exp\left\\{-C\frac{N^{2}}{(N^{1-p/2})^{2}}N^{1-p}\right\\}\leq\exp\left\\{-CN\right\\}.$
(37)

Using the above inequalities, the definition of $\eta$, and arguing as in
(21), we obtain

$\begin{split}\mathbb{P}\left(\exists t\geq
N,\;\tilde{X}_{N,t}\leq\frac{N}{\phi(N)}\right)=\mathbb{P}\left(\eta<\infty\right)\leq\exp\left\\{-CN\right\\}.\end{split}$
(38)

By the pigeonhole Principle the above inequality implies (28) since

$\tilde{X}_{N,t}>\frac{N}{\phi(N)}\iff\sum_{i=1}^{N}d_{t}(i)\mathds{1}\\{\tau(i)\leq
N\\}>\frac{N\phi(t)}{\phi(N)},$ (39)

implying the existence of at least one vertex with degree $\phi(t)/\phi(N)$
among the $N$ first vertices. The remainder of the Theorem follows from (38)
together with the first Borel-Cantelli Lemma. ∎

##  4\. Convergence of the normalized degree

In Section 3 it was important to define the process $d_{s}(i)\phi(s)^{-1}$,
which is a martingale when the appropriate measure is considered. We did so in
order to apply martingale concentration inequalities, but there is still a lot
of information that can be extracted from this process. In this section we
focus on moment bounds and convergence theorems for this martingale. We will
again use the measure $\mathbb{P}_{i,t_{i}}$. The ideas in this section were
inspired by [16].

Given $i,t_{i},k\in\mathbb{N}$, define the process

$Y_{k,s}(i)=Y_{k,s}(i,t_{i}):=\binom{d_{s}(i)+k-1}{k}\mathds{1}\\{\tau_{i}=t_{i}\\}.$
(40)

The properties of the binomial coefficients then imply, on the event
$\\{\tau_{i}=t_{i}\\}$,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle
Y_{s+1,k}(i)$\mbox{}\hfil\phantom{**}\\\ &=\binom{d_{s}(i)+\Delta
d_{s}(i)+k-1}{k}\\\ &=\binom{d_{s}(i)+k-1}{k}\mathds{1}\\{\Delta
d_{s}(i)=0\\}+\binom{d_{s}(i)+1+k-1}{k}\mathds{1}\\{\Delta d_{s}(i)=1\\}\\\
&\quad+\binom{d_{s}(i)+2+k-1}{k}\mathds{1}\\{\Delta d_{s}(i)=2\\}\\\ \\\
&=\binom{d_{s}(i)+k-1}{k}\mathds{1}\\{\Delta d_{s}(i)=0\\}\\\
&\quad+\left(\binom{d_{s}(i)+k-1}{k}+\binom{d_{s}(i)+k-1}{k-1}\right)\mathds{1}\\{\Delta
d_{s}(i)=1\\}\\\
&\quad+\left(\binom{d_{s}(i)+k-1}{k}+2\binom{d_{s}(i)+k-1}{k-1}+\binom{d_{s}(i)+k-1}{k-2}\right)\mathds{1}\\{\Delta
d_{s}(i)=2\\}\\\ \\\ &=Y_{s,k}(i)\left(1+\frac{k}{d_{s}(i)}\mathds{1}\\{\Delta
d_{s}(i)=1\\}+\left(\frac{2k}{d_{s}(i)}+\frac{k(k-1)}{d_{s}(i)(d_{s}(i)+1)}\right)\mathds{1}\\{\Delta
d_{s}(i)=2\\}\right)\\\ &=Y_{s,k}(i)\left(1+\frac{k}{d_{s}(i)}\Delta
d_{s}(i)+\frac{k(k-1)}{d_{s}(i)(d_{s}(i)+1)}\mathds{1}\\{\Delta
d_{s}(i)=2\\}\right).\end{split}$ (41)

Using the process’ definition and (3), we then obtain

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{E}_{i,t_{i}}\left[Y_{s+1,k}(i)\middle|\mathcal{F}_{s}\right]$\mbox{}\hfil\phantom{**}\\\
&=Y_{s,k}(i)\Bigg{(}1+\frac{k}{d_{s}(i)}\frac{d_{s}(i)}{s}\left(1-\frac{f(s+1)}{2}\right)+\frac{k(k-1)}{d_{s}(i)(d_{s}(i)+1)}(1-f(s+1))\frac{d_{s}(i)^{2}}{4s^{2}}\Bigg{)}\\\
&\leq
Y_{s,k}(i)\Bigg{(}1+\frac{k}{s}\left(1-\frac{f(s+1)}{2}\right)+\frac{k(k-1)}{4s^{2}}(1-f(s+1))\left(1-\frac{1}{d_{s}(i)+1}\right)\Bigg{)}.\end{split}$
(42)

Defining then

$\phi_{k}(t):=\prod_{s=1}^{t-1}\Bigg{(}1+\frac{k}{s}\left(1-\frac{f(s+1)}{2}\right)+\frac{k(k-1)}{4s^{2}}(1-f(s+1))\Bigg{)},$
(43)

we obtain that $\\{Y_{t,k}(i)\phi_{k}(t)^{-1}\\}_{t\geq t_{i}}$ is a positive
supermartingale and therefore it converges $\mathbb{P}_{i,t_{i}}$-a.s.

The following relation between the normalization factor $\phi_{k}$ and $\phi$
will be important: there exists $C\equiv C_{k,f}>0$ independent from $i$ and
$t_{i}$ such that

$\begin{split}\phi_{k}(t)&\leq
C\prod_{s=1}^{t-1}\Bigg{(}1+\frac{1}{s}\left(1-\frac{f(s+1)}{2}\right)\Bigg{)}^{k}=C\phi(t)^{k},\\\
C^{-1}\phi(t)^{k}&\leq\phi_{k}(t).\end{split}$ (44)

This is an important ingredient in the proof of our next result.

######  Proposition 4.1.

Let $f$ be any edge-step function such that (V)∞ holds. Then there exists a
non-negative random variable $\tilde{\zeta}_{i,t_{i}}$ in the same probability
space as the process $\\{G_{t}(f)\\}_{t\geq 1}$ such that, for any $q\geq 1$,

$\lim_{t\to\infty}\frac{d_{t}(i)}{\phi(t)}=\tilde{\zeta}_{i,t_{i}},\;\;\mathbb{P}_{i,t_{i}}\text{-a.s.
and in }L_{q}(\mathbb{P}_{i,t_{i}}).$ (45)

Furthermore, defining the mixture

$\zeta_{i}=\sum_{n=1}^{\infty}\mathds{1}\\{\tau_{i}=n\\}\tilde{\zeta}_{i,n},$
(46)

where $\tilde{\zeta}_{i,n}$ is arbitrarily defined outside of
$\\{\tau_{i}=n\\}$, we obtain

$\lim_{t\to\infty}\frac{d_{t}(i)}{\phi(t)}=\zeta_{i},\;\;\mathbb{P}\text{-a.s.
and in }L_{q}(\mathbb{P}).$ (47)

###### Proof.

Since $d_{t}(i)\phi(t)^{-1}$ is a positive martingale with respect to
$\mathbb{P}_{i,t_{i}}$, it converges $\mathbb{P}_{i,t_{i}}$-a.s. to a finite
random variable, which we can denote by $\tilde{\zeta}_{i,t_{i}}$.
Furthermore, since $Y_{t,k}\phi_{k}(t)^{-1}$ is bounded in
$L_{1}(\mathbb{P}_{i,t_{i}})$, we have by (44), for any $k\in\mathbb{N}$ and
uniformly in $i$ and$~{}t_{i}$,

$\mathbb{E}_{i,t_{i}}\left[d_{s}(i)^{k}\phi(s)^{-k}\right]\leq
Ck!\mathbb{E}_{i,t_{i}}\left[Y_{s,k}\phi_{k}(s)^{-1}\right]<C.$ (48)

This implies the $L_{q}$ convergence in (45). Since
$\sum_{s=1}^{\infty}f(s)=\infty$, we have $\mathbb{P}(\tau_{i}=\infty)=0$, and
therefore, almost surely,

$\lim_{t\to\infty}\frac{d_{t}(i)}{\phi(t)}=\lim_{t\to\infty}\sum_{n=1}^{\infty}\mathds{1}\\{\tau_{i}=n\\}\frac{d_{t}(i)}{\phi(t)}=\lim_{t\to\infty}\sum_{n=1}^{\infty}\mathds{1}\\{\tau_{i}=n\\}\tilde{\zeta}_{i,n}=\zeta_{i},\;\;\mathbb{P}\text{-a.s.}$

Recalling that we define $d_{t}(i)\equiv 0$ for $t<\tau_{i}$, we obtain

$\begin{split}\mathbb{E}\left[\frac{d_{t+1}(i)}{\phi(t+1)}\middle|\mathcal{F}_{t}\right]&=\mathbb{E}\left[\sum_{n=1}^{\infty}\mathds{1}\\{\tau_{i}=n\\}\frac{d_{t+1}(i)}{\phi(t+1)}\middle|\mathcal{F}_{t}\right]\\\
&=\sum_{n=1}^{t}\mathds{1}\\{\tau_{i}=n\\}\frac{d_{t}(i)}{\phi(t)}+\frac{1}{\phi(t+1)}\mathbb{P}\left(\tau_{i}=t+1\middle|\mathcal{F}_{t}\right)\\\
&=\sum_{n=1}^{\infty}\mathds{1}\\{\tau_{i}=n\\}\frac{d_{t}(i)}{\phi(t)}+\frac{1}{\phi(t+1)}\mathbb{P}\left(\tau_{i}=t+1\middle|\mathcal{F}_{t}\right),\end{split}$
(49)

implying that $\\{d_{t}(i)\phi(t)^{-1}\\}_{t\geq 1}$ is a submartingale. Now,
the uniformity of the constant in (48) over $t_{i}$ gives us, for $k\geq 1$,

$\begin{split}\mathbb{E}\left[\frac{d_{t}(i)^{k}}{\phi(t)^{k}}\right]=\mathbb{E}\left[\sum_{n=1}^{\infty}\mathds{1}\\{\tau_{i}=n\\}\frac{d_{t}(i)^{k}}{\phi(t)^{k}}\right]=\sum_{n=1}^{\infty}\mathbb{P}\left(\tau_{i}=n\right)\mathbb{E}_{i,n}\left[\frac{d_{t}(i)^{k}}{\phi(t)^{k}}\right]<C,\end{split}$
(50)

yielding that $\\{d_{t}(i)\phi(t)^{-1}\\}_{t\geq 1}$ is bounded in $L_{k}$ for
any $k\in\mathbb{N}$, which implies $L_{q}(\mathbb{P})$ convergence for any
$q\geq 1$, finishing the proof of the result. ∎

The next natural step is to see whether the process $\\{d_{t}(i)\\}_{t\geq 1}$
goes to infinity at $\phi(t)$ speed, which means proving that $\zeta_{i}$ is
strictly positive almost surely. Moreover, this result by itself will be
necessary for the proof of Central Limit Theorem for the maximum degree. Then,
we the next result we prove tat $\phi(t)$ is the right order for the degree.

######  Proposition 4.2.

Let $i$ be the $i$-th vertex added by the process and $\zeta_{i}$ as in
Proposition 4.1. Then $\zeta_{i}$ is strictly positive $\mathbb{P}$-almost
surely.

###### Proof.

As we have seen in Proposition 4.1, $\zeta_{i}$ may be written as

$\zeta_{i}=\sum_{n=i}^{\infty}\tilde{\zeta}_{i,n}\mathbb{1}\\{\tau(i)=n\\}$
(51)

and it is enough to proof that each $\tilde{\zeta}_{i,n}$ is strictly positive
$\mathbb{P}_{i,n}$-a.s. This means, we can focus on the process conditioned
that $i$ has been added at time $n$. Since $n$ is going to be fixed throughout
this proof, we will simply write $\\{X_{s}\\}_{s\geq n}$ for
$\\{X_{s,i,n}\\}_{s\geq n}$ and simply $\mathbb{P}$ for the conditioned
measure $\mathbb{P}_{i,n}$. Following this convention, we denote by $g_{s}$
and $g$ the Laplace transform of $X_{s}$ and $\zeta_{i,n}$ respectively. It
will be useful to recall a fact from real analysis that there exist a positive
$c$, which we may assume smaller than one, such that, for all $x\in[0,c]$,

$e^{-x}\leq 1-x+\frac{x^{2}}{2}.$ (52)

For each $s\in\mathbb{N}$, put $\lambda_{s}:=c\phi(s)/2$. We will follow the
argument given in [nadia18] in the context of Generalized Polya Urns. The
proof will follow from the relation below

$g_{t}(\lambda_{s})\leq
g_{t-r}\left(\lambda_{s}-\lambda_{s}^{2}\sum_{u=t-r+1}^{t}\frac{1}{\phi(u)^{2}}\right),$
(53)

which we prove holds for all $s$, $t>s$ and $0\leq r\leq t-s$. In order to
prove it, we make an induction argument on $r$.

Base case $r=1$. Fix $\lambda\in[0,c\phi(s)/2]$ (it is necessary in our case
to take half of the interval taken in [18], since the degree’s increment can
be $2$) and recall that

$X_{t+1}=\frac{\phi(t)}{\phi(t+1)}X_{t}+\frac{\Delta d_{t}(i)}{\phi(t+1)}.$
(54)

Using (52) and Equation (11), we have that

$\begin{split}\mathbb{E}\left[\exp\left\\{-\frac{\lambda\Delta
d_{t}(i)}{\phi(t+1)}\right\\}\;\middle|\;\mathcal{F}_{t}\right]&\leq\mathbb{E}\left[1-\frac{\lambda\Delta
d_{t}(i)}{\phi(t+1)}+\frac{\lambda^{2}\Delta^{2}d_{t}(i)}{2\phi(t+1)^{2}}\;\middle|\;\mathcal{F}_{t}\right]\\\
&=1-\frac{\lambda}{\phi(t+1)}\cdot\frac{(2-f(t))d_{t}(i)}{2t}\\\
&\quad+\frac{\lambda^{2}}{2\phi(t+1)^{2}}\left[\frac{(2-f(t))d_{t}(i)}{2t}+\frac{2(1-f(t))d^{2}_{t}(i)}{4t^{2}}\right]\\\
&\leq
1-\frac{\lambda}{\phi(t+1)}\cdot\frac{(2-f(t))d_{t}(i)}{2t}+\frac{\lambda^{2}}{2\phi(t+1)^{2}}\frac{2(2-f(t))d_{t}(i)}{2t}\end{split}$
(55)

It will be useful to recall that

$\phi(t+1)=\phi(t)\left(1+\frac{2-f(t)}{2t}\right).$ (56)

Using (55) and that $\log(1+x)\leq x$, we obtain that

$\begin{split}\mathbb{E}\left[e^{-\lambda
X_{t+1}}\;\middle|\;\mathcal{F}_{t}\right]\leq\phantom{***********************************************}\\\
\exp\left\\{-\frac{\lambda\phi(t)}{\phi(t+1)}X_{t}+\log\left(1-\frac{\lambda}{\phi(t+1)}\cdot\frac{(2-f(t))d_{t}(i)}{2t}+\frac{\lambda^{2}}{2\phi(t+1)^{2}}\frac{2(2-f(t))d_{t}(i)}{2t}\right)\right\\}\\\
\leq\exp\left\\{-\frac{\lambda\phi(t)}{\phi(t+1)}X_{t}-\frac{\lambda\phi(t)}{\phi(t+1)}\cdot\frac{(2-f(t))X_{t}}{2t}+\frac{\lambda^{2}\phi(t)}{2\phi(t+1)^{2}}\frac{2(2-f(t))X_{t}}{2t}\right\\}\\\
\leq\exp\left\\{-\lambda
X_{t}+\frac{\lambda^{2}}{2\phi(t+1)^{2}}X_{t}\right\\}.\end{split}$ (57)

Taking the expected value both sides, leads to

$g_{t+1}(\lambda)\leq
g_{t}\left(\lambda-\frac{\lambda^{2}}{2\phi(t+1)^{2}}\right),$ (58)

for all $\lambda\in[0,c\phi(s)/2]$, which proves the base case of our
induction.

Inductive step. From here the proof is similar to that given in [18] setting
$\sigma_{t}=1$ and $\tau_{t}=\phi(t)$. Our inductive hypothesis, tells us that

$g_{t}(\lambda_{s})\leq
g_{t-r}\left(\lambda_{s}-\lambda_{s}^{2}\sum_{u=t-r+1}^{t}\frac{1}{\phi(u)^{2}}\right)$
(59)

holds for $0\leq r\leq t-s-1$. Now, observe that

$\lambda_{s}-\lambda_{s}^{2}\sum_{u=t-r+1}^{t}\frac{1}{\phi(u)^{2}}\leq\lambda_{s},$

thus, combining the above inequality with (58) and recalling that $g_{t}$ is
decreasing, we have that

$\begin{split}g_{t-r}\left(\lambda_{s}-\lambda_{s}^{2}\sum_{u=t-r+1}^{t}\frac{1}{\phi(u)^{2}}\right)&\leq
g_{t-r-1}\left(\lambda_{s}-\lambda_{s}^{2}\sum_{u=t-r+1}^{t}\frac{1}{\phi(u)^{2}}-\left(\lambda_{s}-\lambda_{s}^{2}\sum_{u=t-r+1}^{t}\frac{1}{\phi(u)^{2}}\right)^{2}\frac{1}{\phi(t-r)^{2}}\right)\\\
&\leq
g_{t-r-1}\left(\lambda_{s}-\lambda_{s}^{2}\sum_{u=t-r}^{t}\frac{1}{\phi(u)^{2}}\right),\end{split}$
(60)

which proves the induction. Taking $r=t-s$ on (58) and noticing that

$\lambda_{s}-\lambda_{s}^{2}\sum_{u=s+1}^{t}\frac{1}{\phi^{2}(u)}\geq\lambda_{s}-\lambda^{2}_{s}\int_{\phi(s)}^{\infty}\frac{\mathrm{d}x}{x^{2}}=\lambda_{s}\left(1-c/2\right)\geq
0$ (61)

we obtain that

$g_{t}(\lambda_{s})\leq
g_{s}((1-c/2)\lambda_{s})=\mathbb{E}\left[e^{-(1-c/2)c\phi(s)X_{s}/2}\right]=\mathbb{E}\left[e^{-(1-c/2)cd_{s}(i)/2}\right].$
(62)

Taking the limit on $t$, the Dominated Convergence Theorem gives us that

$g(\lambda_{s})\leq\mathbb{E}\left[e^{-(1-c/2)cd_{s}(i)/2}\right].$

Finally, another application of the Dominated Convergence Theorem combined
with the fact that $\\{d_{s}(i)\\}_{s\geq n}$ goes to infinity
$\mathbb{P}_{i,n}$-a.s. as $s$ goes to infinity yields $g(\lambda_{s})\to 0$
as $s$ goes to infinity. The Proposition follows by the fact that

$\mathbb{P}_{i,n}(\zeta_{i,n}=0)\leq g(\lambda),$ (63)

for any $\lambda>0$. ∎

The family of supermartingale $\\{Y_{t,k}(i)\\}_{t\geq i}$ defined in (40)
allows us to obtain upper bounds for all the moments of the limit random
variables $\zeta_{i}$.

######  Lemma 4.3 (Moment bounds for the limit distribution).

Assume $f$ either belongs to $\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$ or
is identically equal to $p\in(0,1]$. Then given $k\in\mathbb{N}$, there exists
constants $C,C^{\prime}>0$ independent from $i$ such that

$\mathbb{E}\left[\zeta_{i}^{k}\right]\leq C^{-1}\left(\exp\left\\{-C\cdot
i\right\\}+\frac{1}{\phi(F^{-1}(i))^{k}}\right)\leq C^{\prime}\cdot
i^{-\frac{k}{2}}.$ (64)

###### Proof.

Since $\\{d_{s}(i)\\}_{s\geq n}$ goes to infinity, we have that, on
$\\{\tau_{i}=t_{i}\\}$,

$Y_{s,k}(i)=\binom{d_{s}(i)+k-1}{k}=\frac{(d_{s}(i)+k-1)\dots(d_{s}(i)+1)d_{s}(i)}{k!}\xrightarrow{s\to\infty}\frac{\tilde{\zeta}_{i,t_{i}}^{k}}{k!}\quad\mathbb{P}\text{-a.s.}.$

Now, since $\\{Y_{t,k}(i)\phi_{k}(t)^{-1}\\}_{t\geq t_{i}}$ is a positive
supermartingale in $\mathbb{P}_{i,t_{i}}$, we have, by (44),

$\mathbb{E}_{i,t_{i}}\left[\tilde{\zeta}_{i,t_{i}}^{k}\right]\leq
k!\frac{C}{\phi(t_{i})^{k}}.$

By definition of $\zeta_{i}$, we then obtain

$\mathbb{E}\left[\zeta_{i}^{k}\right]=\sum_{n=1}^{\infty}\mathbb{P}\left(\tau_{i}=n\right)\mathbb{E}_{i,t_{i}}\left[\tilde{\zeta}_{i,t_{i}}^{k}\right]\leq
C\mathbb{P}\left(\tau_{i}\leq
F^{-1}(i)/2\right)+\frac{C}{\phi(F^{-1}(i)/2)^{k}},$

By Lemma 3.2 and Equation (26), the right hand side of the above equation is
bounded from above by

$C\cdot C_{f}^{-1}\exp\left\\{-C_{f}\cdot
i\right\\}+\frac{C}{\phi(F^{-1}(i))^{k}}.$

To prove the second inequality in (64), we note that, since
$\|f\|_{\infty}\leq 1$, for $s\in\mathbb{N}$,

$\begin{split}\phi(s)=\prod_{n=1}^{t-1}\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right)\geq
C\sqrt{s}.\end{split}$ (65)

If $f\equiv p>0$, then $F^{-1}(i)=i/p$ and the result follows. Assume now that
$f\in\mathrm{RES}(\gamma)$. By the monotonicity of $F$, Theorem B.3 and
Equation (9), we have for sufficiently large $s$, using the representation
$f(t)=t^{-\gamma}\ell(t)$ with $\ell:\mathbb{N}\to\mathbb{R}$ being a slowly
varying function,

$\begin{split}F(s)&\leq 2\frac{s^{1-\gamma}}{1-\gamma}\ell(s)\\\ s&\leq
F^{-1}\big{(}i^{1-2^{-1}\gamma}\big{)}\\\ s^{\frac{1}{1-2^{-1}\gamma}}&\leq
F^{-1}(s),\end{split}$ (66)

where in the second inequality we used the fact that, if $\gamma=0$, then
$f\equiv\ell$ converges to $0$. These inequalities then imply

$\phi\left(F^{-1}(i)\right)^{k}\geq Ci^{\frac{k}{2-\gamma}},$

which finishes the proof of the lemma. ∎

###  4.1. Convergence of the scaled maximum degree

In this part we are going to extend the convergence result proven for a fixed
vertex $i$ to the maximum degree process. We begin by introducing new notation
and recalling others. Given $s,t\in\mathbb{N}$, with $s\leq t$, we define the
variables

$\displaystyle X_{s,i}$ $\displaystyle:=\frac{d_{s}(i)}{\phi(s)},\quad
M[s,i]:=\max_{1\leq k\leq i}\\{X_{s,k}\\},\quad M_{s}:=\max_{k\geq
1}\\{X_{s,k}\\},$ (67) $\displaystyle\mu(i)$ $\displaystyle:=\max_{1\leq k\leq
i}\\{\zeta_{k}\\},\quad\mu:=\sup_{k\geq 1}\\{\zeta_{k}\\}.$

Now we have all the tools needed for proof Theorem 1.1.

###### Proof of Theorem 1.1.

Equation (49) yields that $\\{X_{s,i}\\}_{s\geq 1}$ is a submartingale, and
for $q\geq 1$ the fucntion that maps $x\in\mathbb{R}$ to $x^{q}$ is convex.
Jensen’s inequality then implies, together with Lemma 4.3,

$\mathbb{E}\left[M_{s}^{q}\right]\leq\sum_{j=1}^{\infty}\mathbb{E}\left[X_{s,j}^{q}\right]\leq\sum_{j=1}^{\infty}\mathbb{E}\left[\zeta_{j}^{q}\right]\leq
C\sum_{j=1}^{\infty}j^{-\frac{q}{2}}<\infty,$

for $q>2$. But $M_{s}=M[s,s]$, since $X_{s,k}=0$ for $k>s$. Being the maximum
of submartingales implies that $\\{M_{s}\\}_{s\geq 1}$ is itself a
submartingale, and the above inequality shows that it is $L_{q}$-bounded for
any $q>2$. This implies that it converges almost surely and in $L_{q}$ to some
finite random variable. Again with $q>2$, we have that

$\mathbb{E}\left[(M_{s}-M[s,i])^{q}\right]\leq\sum_{j=i+1}^{\infty}\mathbb{E}\left[X_{s,j}^{q}\right]\xrightarrow{i\to\infty}0.$

But by Proposition 4.1, $M[s,i]$ converges to $\mu(i)$ $\mathbb{P}$-a.s. and
in $L_{q}$ as $s\to\infty$ and therefore the limit of the LHS is equal to

$\lim_{i\to\infty}\mathbb{E}\left[\left(\lim_{s\to\infty}M_{s}-\mu(i)\right)^{q}\right]=0,$

and $\lim_{i}\mu(i)=\mu$ a.s. and in $L_{q}$ by monotone convergence. This
implies (3). And finally, the fact that $\mu>0,\mathbb{P}$-a.s. then comes as
consequence of Proposition 4.2. ∎

Now, the sharpness of the condition (S) when $f$ belongs to RES$(-\gamma)$,
with $\gamma\in[0,1)$, comes naturally from our results.

###### Proof of Corollary 1.2.

By Theorem 1.1, under RES$(-\gamma)$, with $\gamma\in[0,1)$ the maximum degree
scaled by $\phi$ converges to a finite and positive limit. On the other hand,
by Equation (16), it follows that $\phi(t)=\Theta(t)$ if, and only if,
condition (S) is satisfied. ∎

##  5\. The Persistent Leadership

This section is devoted to the proof of Theorem 1.4, which states that
eventually only one vertex becomes the one with maximum degree and stay in
this position forever. The key step is to prove that for any pair of vertices
$i$ and $j$ we have that $\zeta_{i}\neq\zeta_{j}$ almost surely. As discussed
in Section 2, in the case of the BA-model and its affine version the absence
of the edge-step rule implies $\zeta_{i}\neq\zeta_{j}$ in a straightforward
way, since for this class of models a natural Póya urn scheme emerges from the
degree process when we look to the degrees of $i$ and $j$ only at the random
times one of them has increased. Thus, from Polya urn results follows that
each $\zeta_{i}$ is a continuous random variable.

Since in our settings, we cannot rely on direct Polya Urn results, we prove
this key step dealing directly with the process $\\{D_{s}\\}_{s\geq\tau_{j}}$
defined as

$D_{s}:=|d_{s}(i)-d_{s}(j)|.$ (68)

In particular, we prove that $D_{s}$ goes to infinity almost surely. In order
to do so, it will be useful to look to $\\{D_{s}\\}_{s\geq\tau_{j}}$ only at
the times at least one of the vertices has been chosen. Thus, we introduce the
following sequence of stopping times:

$\begin{split}\sigma_{0}&:=\tau_{j}\\\
\sigma_{k}&:=\inf_{s\geq\sigma_{k-1}}\\{\Delta d_{s}(i)>0\text{ or }\Delta
d_{s}(j)>0\\},\end{split}$ (69)

which are finite since both degrees go to infinity. We also let
$\\{\tilde{D}_{k}\\}_{k\geq 0}$ to be

$\tilde{D}_{k}:=D_{\sigma_{k}}.$ (70)

Our proves then require an intermediate result, which needs extra notation to
be stated properly. We say a finite (multi)graph $\tilde{G}$ is
$(i,j,t_{i},t_{j},f)$-admissible whenever

$\mathbb{P}(\tau_{i}=t_{i},\tau_{j}=t_{j},G_{t_{j}}(f)=\tilde{G})>0.$

We denote by $\mathbb{P}_{\tilde{G}}$ the probability measure $\mathbb{P}$
conditioned on the event

$\\{\tau_{i}=t_{i},\tau_{j}=t_{j},G_{t_{j}}(f)=\tilde{G}\\}.$

######  Lemma 5.1 (Law of Iterated Logarithm for $\tilde{D}_{k}$).

Assume $f$ either belongs to $\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$ or
is identically equal to $p\in(0,1]$. Let $i,j\in\mathbb{N}$ denote two
distinct vertices that were added to the graph at times $i$ and $j$
respectively. Then, there exist a strictly positive random variable
$\bar{\delta}$ such that

$\begin{split}\limsup_{k\to\infty}\frac{\tilde{D}_{k}-\sum_{n=0}^{k-1}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{n}\middle|\mathcal{F}_{\sigma_{n}}\right]}{\sqrt{\bar{\delta}k\log\log\left(\bar{\delta}k\right)}}&\geq
1,\;\mathbb{P}_{\tilde{G}}\text{-a.s.,}\end{split}$ (71)

for any admissible graph $\tilde{G}$.

The reason why we need such lemma is the following: once one of the degrees is
sufficiently larger than the other it hard for the smallest one to catch up
its adversary. Thus, we may bootstrap the above lemma by proving that actually
the whole process $\\{D_{s}\\}_{s\geq\tau_{j}}$ goes to infinity.

###### Proof of Lemma 5.1.

We will apply Theorem $6.3$ of [13] which gives LIL for submartingales
satisfying certain conditions. Thus, the proof consist of showing that the
stopped process $\\{\tilde{D}_{k}\\}_{k}$ is a submartingale and proving
estimates for the variance of its increments.

We begin by showing that $\\{\tilde{D}_{k}\\}_{k}\geq 1$ is a submartingale.
Note that, by the same reasoning as in (12), the process

$\left\\{\frac{d_{s}(i)-d_{s}(j)}{\phi(s)}\right\\}_{s\geq t_{j}}$ (72)

is a martingale in $\mathbb{P}_{\tilde{G}}$. Therefore, by Jensen’s
inequality,

$\begin{split}\mathbb{E}_{\tilde{G}}\left[\left|\frac{d_{s+1}(i)-d_{s+1}(j)}{\phi(s+1)}\right|\;\middle|\;\mathcal{F}_{s}\right]&\geq\left|\frac{d_{s}(i)-d_{s}(j)}{\phi(s)}\right|,\end{split}$
(73)

and we obtain

$\begin{split}\mathbb{E}_{\tilde{G}}\left[\left|d_{s+1}(i)-d_{s+1}(j)\right|\middle|\mathcal{F}_{s}\right]\geq\left|d_{s}(i)-d_{s}(j)\right|\frac{\phi(s+1)}{\phi(s)}\geq\left|d_{s}(i)-d_{s}(j)\right|.\end{split}$
(74)

Now, since

$\left|d_{s\wedge\sigma_{k+1}}(i)-d_{s\wedge\sigma_{k+1}}(j)\right|\leq
k+1+d_{t_{j}}(i)+1,$

the process
$\\{\left|d_{s\wedge\sigma_{k+1}}(i)-d_{s\wedge\sigma_{k+1}}(j)\right|\\}_{s}$
is uniformly integrable in $\mathbb{P}_{\tilde{G}}$ and the submartingale
optional stopping theorem (see Theorem $5.7.4$ of [9]) shows that
$\\{\tilde{D}_{k}\\}_{k\geq 1}$ is a submartingale.

We will need lower bounds on the conditional variance of
$\Delta\tilde{D}_{k}$. We begin by noting that

$\begin{split}\mathrm{Var}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]&=\mathbb{E}_{\tilde{G}}\left[\left(\Delta\tilde{D}_{k}-\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]\right)^{2}\middle|\mathcal{F}_{\sigma_{k}}\right]\\\
&\geq\left(1-\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]\right)^{2}\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=1\middle|\mathcal{F}_{\sigma_{k}}\right]\\\
&\quad+\left(-1-\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]\right)^{2}\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=-1\middle|\mathcal{F}_{\sigma_{k}}\right]\\\
&\geq\frac{4\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=1\middle|\mathcal{F}_{\sigma_{k}}\right]\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=-1\middle|\mathcal{F}_{\sigma_{k}}\right]}{\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=1\middle|\mathcal{F}_{\sigma_{k}}\right]+\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=-1\middle|\mathcal{F}_{\sigma_{k}}\right]}\\\
&\geq
2\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=1\middle|\mathcal{F}_{\sigma_{k}}\right]\mathbb{P}_{\tilde{G}}\left[\Delta\tilde{D}_{k}=-1\middle|\mathcal{F}_{\sigma_{k}}\right],\end{split}$
(75)

where we have used that $(1-x)^{2}a+(1+x)^{2}b\geq 4ab/(a+b)$ for all values
of $x$. Assume $\tilde{D}_{k}\neq 0$. In order for $\Delta\tilde{D}_{k}$ to be
$1$, resp. $-1$, the vertex with highest, resp. lower degree must receive a
connection at time $\sigma_{k+1}$. We have, by the definition of the process,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}_{\tilde{G}}\left(\Delta
d_{s}(i)+\Delta d_{s}(j)\geq
1\middle|\mathcal{F}_{s}\right)$\mbox{}\hfil\quad\\\
&=f(s+1)\frac{d_{s}(i)+d_{s}(j)}{2s}+2\left(1-f(s+1)\right)\frac{d_{s}(i)+d_{s}(j)}{2s}\left(1-\frac{d_{s}(i)+d_{s}(j)}{2s}\right)\\\
&\quad+\left(1-f(s+1)\right)\Bigg{(}\frac{d_{s}(i)+d_{s}(j)}{2s}\Bigg{)}^{2}\\\
&=\frac{d_{s}(i)+d_{s}(j)}{s}\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{s}(i)+d_{s}(j)}{4s}\right).\end{split}$
(76)

At the same time,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}_{\tilde{G}}\left(\Delta
d_{s}(i)=1,\Delta
d_{s}(j)=0\middle|\mathcal{F}_{s}\right)$\mbox{}\hfil\quad\\\
&=f(s+1)\frac{d_{s}(i)}{2s}+2\left(1-f(s+1)\right)\frac{d_{s}(i)}{2s}\left(1-\frac{d_{s}(i)+d_{s}(j)}{2s}\right)\\\
&=\frac{d_{s}(i)}{s}\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{s}(i)+d_{s}(j)}{2s}\right).\end{split}$
(77)

Now, by the two above equations, in the event where $\sigma_{k}\leq s$ we have

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}_{\tilde{G}}\left(\Delta
d_{s}(i)=1,\Delta
d_{s}(j)=0\middle|\mathcal{F}_{\sigma_{k}},\sigma_{k+1}=s+1\right)$\mbox{}\hfil\quad\\\
&=\frac{\mathbb{E}_{\tilde{G}}\left[\mathbb{P}_{\tilde{G}}\left(\Delta
d_{s}(i)=1,\Delta
d_{s}(j)=0,\sigma_{k+1}=s+1\middle|\mathcal{F}_{s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}{\mathbb{E}_{\tilde{G}}\left[\mathbb{P}_{\tilde{G}}\left(\sigma_{k+1}=s+1\middle|\mathcal{F}_{s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}\\\
&=\frac{\mathbb{E}_{\tilde{G}}\left[\mathds{1}\\{\sigma_{k+1}>s\\}\mathbb{P}_{\tilde{G}}\left(\Delta
d_{s}(i)=1,\Delta
d_{s}(j)=0\middle|\mathcal{F}_{s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}{\mathbb{E}_{\tilde{G}}\left[\mathds{1}\\{\sigma_{k+1}>s\\}\mathbb{P}_{\tilde{G}}\left(\Delta
d_{s}(i)+\Delta d_{s}(j)\geq
1\middle|\mathcal{F}_{s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}\\\
&=\frac{\mathbb{E}_{\tilde{G}}\left[\mathds{1}\\{\sigma_{k+1}>s\\}\frac{d_{s}(i)}{s}\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{s}(i)+d_{s}(j)}{2s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}{\mathbb{E}_{\tilde{G}}\left[\mathds{1}\\{\sigma_{k+1}>s\\}\frac{d_{s}(i)+d_{s}(j)}{s}\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{s}(i)+d_{s}(j)}{4s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}\\\
&=\frac{\mathbb{E}_{\tilde{G}}\left[\mathds{1}\\{\sigma_{k+1}>s\\}\frac{d_{\sigma_{k}}(i)}{s}\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{2s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}{\mathbb{E}_{\tilde{G}}\left[\mathds{1}\\{\sigma_{k+1}>s\\}\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{s}\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{4s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}\\\
&=\frac{d_{\sigma_{k}}(i)}{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}\cdot\frac{\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{2s}\right)}{\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{4s}\right)}.\end{split}$
(78)

Denote by $\xi(\infty)$ the limit of $\xi(s)$ as $s$ tends to infinity. It
exists by Equation (16), and is only nonzero if $\sum_{s\geq 1}f(s)/s=\infty$.
In the event where $\sigma_{k}\leq s$, we have

$\begin{split}(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{2s}&\leq(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{2\sigma_{k}}\\\
&=(1-f(s+1))\frac{(d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j))}{\phi(\sigma_{k})}\frac{\xi(\sigma_{k})}{2}.\end{split}$
(79)

In the case where $f\equiv p$ and the case that $\xi(\infty)=0$ we have that
the above RHS converges to zero as $k$ goes to infinity, since in both cases
$\phi(s)=o(s)$. For the case in which $\xi(\infty)>0$ and $f\searrow 0$, since

$d_{s}(i)+d_{s}(j)\leq 2s-d_{s}(j+1),$

we have,

$\zeta_{i}+\zeta_{j}=\lim_{s\to\infty}\frac{d_{s}(i)+d_{s}(j)}{\phi(s)}\leq\lim_{s\to\infty}\frac{2(2s-d_{s}(j+1))}{2s\xi(s)}=\frac{2}{\xi(\infty)}-\zeta_{j+1}<\frac{2}{\xi(\infty)}.$
(80)

Proposition 4.2 yields that the RHS of (79) is strictly less the $1$ almost
surely. Furthermore,

$\begin{split}\lim_{k\to\infty}\frac{d_{\sigma_{k}}(i)}{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}=\frac{\zeta_{i}}{\zeta_{i}+\zeta_{j}},\end{split}$
(81)

and since $\zeta_{i}$ and $\zeta_{j}$ are strictly positive and finite almost
surely, the RHS of the above equation is also strictly positive. By
integrating over the possible values of $\sigma_{k+1}$, we obtain from the
above equations that there exists an a.s. positive random variable
$\bar{\delta}_{1}$ such that, uniformly over $k$,

$\begin{split}\mathbb{P}_{\tilde{G}}\left(\Delta
d_{\sigma_{k+1}-1}(i)=1,\Delta
d_{\sigma_{k+1}-1}(j)=0\middle|\mathcal{F}_{\sigma_{k}}\right)&\geq\bar{\delta}_{1}.\end{split}$
(82)

This is possible since, by the above discussion, for each $k$ the LHS of the
above inequality is bounded from below by a $k$-dependent random variable
whose limit in $k$ is strictly positive $\mathbb{P}_{\tilde{G}}$-a.s. Notice
that analogous inequalities are valid for $d_{s}(j)$ in place of $d_{s}(i)$.

Equation $(\ref{eq:degreediv5})$ then implies that there exists an a.s.
positive random variable $\bar{\delta}_{2}$ such that when $\tilde{D}_{k}\neq
0$, uniformly over $k$,

$\begin{split}\mathrm{Var}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]&\geq
2\bar{\delta}_{2}.\end{split}$ (83)

By the Azuma-Höffeding inequality we obtain

$\begin{split}\mathbb{P}_{\tilde{G}}\left(\sum_{k=1}^{N}\left(\mathds{1}\\{\tilde{D}_{k}\neq
0\\}-\mathbb{P}_{\tilde{G}}\left(\tilde{D}_{k}\neq
0\middle|\mathcal{F}_{\sigma_{k-1}}\right)\right)\leq-N^{3/4}\right)&\leq\exp\left\\{-4^{-1}N^{3/2}\cdot
N^{-1}\right\\}\\\ &\leq\exp\left\\{-4^{-1}N^{1/2}\right\\}.\end{split}$ (84)

Together with Equation (82) this implies, almost surely, the existence of a
finite random $N_{0}\in\mathbb{N}$ such that, for $N\geq N_{0}$,

$\begin{split}\sum_{k=1}^{N}\mathds{1}\\{\tilde{D}_{k}\neq
0\\}&\geq\sum_{k=1}^{N}\mathbb{P}_{\tilde{G}}\left(\tilde{D}_{k}\neq
0\middle|\mathcal{F}_{\sigma_{k-1}}\right)-N^{3/4}\\\
&\geq\sum_{k=1}^{N}\mathbb{P}_{\tilde{G}}\left(\Delta\tilde{D}_{k-1}=1\middle|\mathcal{F}_{\sigma_{k-1}}\right)-N^{3/4}\\\
&\geq N(\bar{\delta}_{1}-N^{-1/4}).\end{split}$ (85)

Equation (83), which holds on $\tilde{D}_{k}\neq 0$, then yields, for $N$
larger than $N_{0}$,

$\begin{split}\sum_{k=1}^{N}\mathrm{Var}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]\geq
2\bar{\delta}_{2}\sum_{k=1}^{N}\mathds{1}\\{\tilde{D}_{k}\neq 0\\}\geq
N\bar{\delta}_{1}\bar{\delta}_{2}.\end{split}$ (86)

From now on, we denote $\bar{\delta}:=\delta_{1}\bar{\delta}_{2}$. Consider
now the Doob decomposition of the submartingale $\\{\tilde{D}_{k}\\}_{k\geq
0}$,

$\begin{split}\tilde{D}_{k}=\tilde{D}_{0}+\sum_{n=0}^{k-1}\left(\tilde{D}_{n+1}-\mathbb{E}_{\tilde{G}}\left[\tilde{D}_{n+1}\middle|\mathcal{F}_{\sigma_{n}}\right]\right)+\sum_{n=0}^{k-1}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{n}\middle|\mathcal{F}_{\sigma_{n}}\right].\end{split}$
(87)

Then

$\begin{split}S_{k}:=\tilde{D}_{k}-\sum_{n=0}^{k-1}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{n}\middle|\mathcal{F}_{\sigma_{n}}\right]\end{split}$
(88)

is a mean zero martingale, and the predictable process being subtracted from
$\tilde{D}_{k}$ above is always nonnegative, since $\tilde{D}_{k}$ is a
submartingale. Furthermore,

$\begin{split}\Delta\left(\tilde{D}_{k}-\sum_{n=0}^{k-1}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{n}\middle|\mathcal{F}_{\sigma_{n}}\right]\right)=\Delta\tilde{D}_{k}-\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right],\end{split}$
(89)

and therefore the conditional second moment of the increment of $S_{k}$ equals
the conditional variance of $\Delta\tilde{D}_{k}$. We can finally apply
Theorem $6.3$ of [13] to $S_{n}$ with
$V_{k}:=\mathrm{Var}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]$
and $T_{n}=\sum_{k=1}^{n}V_{k}$, which gives the LIL for the martingale
component of the submartingale $\\{\tilde{D}_{k}\\}_{k\in\mathbb{N}}$. The
result extends to $\\{\tilde{D}_{k}\\}_{k\in\mathbb{N}}$ itself since its
predictable component is positive. ∎

We will need another lemma before proving Theorem 1.4.

######  Lemma 5.2.

Assume $f$ either belongs to $\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$ or
is identically equal to $p\in(0,1]$. Let $i,j\in\mathbb{N}$ denote two
distinct vertices that were added to the graph at times $i$ and $j$
respectively. Then,

$\lim_{s\to\infty}\left|d_{s}(i)-d_{s}(j)\right|=\infty,\;\mathbb{P}\text{-a.s.}$
(90)

###### Proof.

The proof strategy we adopt here will be to bootstrap the LIL proved in Lemma
5.1, i.e., we use that at some random times the difference between the degrees
of $i$ and $j$ are large enough in order to show that this fact is
“irreversible. Thus, by Lemma 5.1 we know that there exists a.s. an increasing
random sequence $(\mathcal{T}_{m})_{m\geq 1}$ of stopping times where

$\begin{split}\tilde{D}_{\mathcal{T}_{m}}\geq\tilde{D}_{\mathcal{T}_{m}}-\sum_{n=0}^{{\mathcal{T}_{m}}-1}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{n}\middle|\mathcal{F}_{\sigma_{n}}\right]\geq\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}.\end{split}$
(91)

Given such a $\mathcal{T}_{m}$ and some number $\varepsilon>0$, consider the
stopping time

$\eta_{1}:=\inf\left\\{s\geq\mathcal{T}_{m};\tilde{D}_{s}<(1-\varepsilon)\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}\right\\}.$

Assume, w.l.o.g. that $d_{\mathcal{T}_{m}}(i)>d_{\mathcal{T}_{m}}(j)$. Then,
for $k\geq\mathcal{T}_{m}$, we have by a similar argument as in (78) and by
Equations (3) and (76),

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k\wedge\eta_{1}}\middle|\mathcal{F}_{\sigma_{k}},\sigma_{k+1}=s+1\right]$\mbox{}\hfil\quad\\\
&=\mathds{1}\\{\eta_{1}>k\\}\frac{\mathbb{E}_{\tilde{G}}\left[\mathbb{E}_{\tilde{G}}\left[\Delta(d_{s}(i)-d_{s}(j))\mathds{1}\\{\sigma_{k+1}=s+1\\}\middle|\mathcal{F}_{s}\right]\middle|\mathcal{F}_{\sigma_{k}}\right]}{\mathbb{E}_{\tilde{G}}\left[\mathbb{P}_{\tilde{G}}\left(\sigma_{k+1}=s+1\middle|\mathcal{F}_{s}\right)\middle|\mathcal{F}_{\sigma_{k}}\right]}\\\
&=\mathds{1}\\{\eta_{1}>k\\}\frac{d_{\sigma_{k}}(i)-d_{\sigma_{k}}(j)}{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}\cdot\frac{\left(1-\frac{f(s+1)}{2}\right)}{\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{4s}\right)}.\end{split}$
(92)

If $f\equiv p$, Stirling’s approximation gives

$\phi(t)=\prod_{s=1}^{t-1}\left(\frac{s+1-p/2}{s}\right)=\frac{\Gamma(t+1-p/2)}{\Gamma(t)}=\frac{(1+o(1))}{t^{1-p/2}}.$
(93)

and therefore the fraction

$\frac{\left(1-\frac{f(s+1)}{2}\right)}{\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{d_{\sigma_{k}}(i)+d_{\sigma_{k}}(j)}{4s}\right)}$

converges to $1$ a.s. as $k\to\infty$ since $(d_{s}(i)+d_{s}(i))s^{-1+p/2}$
converges a.s. to a finite random variable as $s$ goes to infinity by
Proposition 4.1. If $f(s)\downarrow 0$, then the right hand side of (76) is
bounded from below by

$\mathds{1}\\{\eta_{1}>k\\}\frac{\tilde{D}_{k}}{k+t_{j}}\cdot\left(1-\frac{f(s+1)}{2}\right),$
(94)

since the total number of connections added to $i$ or $j$ by time $\sigma_{k}$
is at most $k+t_{j}$. Then for $k$ sufficiently large, integrating over the
possible values of $\sigma_{k+1}$, we obtain

$\begin{split}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k\wedge\eta_{1}}\middle|\mathcal{F}_{\sigma_{k}}\right]&\geq\mathds{1}\\{\eta_{1}>k\\}\frac{3\tilde{D}_{k}}{4k}.\end{split}$
(95)

This in turn yields, for large enough $m$,

$\begin{split}\sum_{k=\mathcal{T}_{m}}^{(1+\varepsilon)\mathcal{T}_{m}\wedge\eta_{1}}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k\wedge\eta_{1}}\middle|\mathcal{F}_{\sigma_{k}}\right]&\geq\mathds{1}\\{\eta_{1}>(1+\varepsilon)\mathcal{T}_{m}\\}\varepsilon\mathcal{T}_{m}\frac{3(1-\varepsilon)\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}}{4(1+\varepsilon)\mathcal{T}_{m}}\\\
&\geq\mathds{1}\\{\eta_{1}>(1+\varepsilon)\mathcal{T}_{m}\\}\frac{3}{4}\frac{\varepsilon(1-\varepsilon)}{(1+\varepsilon)}\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}.\end{split}$
(96)

We now use the Azuma-Höffeding inequality for the martingale defined in (88)
between times $\mathcal{T}_{m}$ and $(1+\varepsilon)\mathcal{T}_{m}$ stopped
in $\eta_{1}$. Denote by $A_{\delta}$ the event where $\bar{\delta}>\delta$
for some given $\delta>0$. Since

$\begin{split}\left|\Delta\tilde{D}_{k}-\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{k}\middle|\mathcal{F}_{\sigma_{k}}\right]\right|\leq
4,\end{split}$ (97)

we obtain, using the fact that $m\leq\mathcal{T}_{m}$,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}_{\tilde{G}}\left(\tilde{D}_{(1+\varepsilon)\mathcal{T}_{m}}\wedge\eta_{1}-\sum_{n=\mathcal{T}_{m}}^{(1+\varepsilon)\mathcal{T}_{m}\wedge\eta_{1}-1}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{n}\middle|\mathcal{F}_{\sigma_{n}}\right]-\tilde{D}_{\mathcal{T}_{m}}\leq-\varepsilon\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)},A_{\delta}\right)$\mbox{}\hfil\phantom{****************************}\\\
&\leq\mathbb{E}_{\tilde{G}}\left[\exp\left\\{-\frac{\varepsilon^{2}\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}{16\varepsilon\mathcal{T}_{m}}\right\\}\mathds{1}_{A_{\delta}}\right]\\\
&\leq\exp\left\\{-\frac{\varepsilon^{2}\delta\log\log\left(\delta
m\right)}{16\varepsilon}\right\\},\end{split}$ (98)

yielding

$\begin{split}\mathbb{P}_{\tilde{G}}\left(\eta_{1}\leq(1+\varepsilon)\mathcal{T}_{m},A_{\delta}\right)&\leq\exp\left\\{-\frac{\varepsilon^{2}\delta\log\log\left(\delta
m\right)}{16\varepsilon}\right\\}.\end{split}$ (99)

Replacing $\varepsilon$ by $\varepsilon^{2}$ multiplying the $\log\log$
factor, we have

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{P}_{\tilde{G}}\left(\tilde{D}_{(1+\varepsilon)\mathcal{T}_{m}}-\sum_{n=\mathcal{T}_{m}}^{(1+\varepsilon)\mathcal{T}_{m}-1}\mathbb{E}_{\tilde{G}}\left[\Delta\tilde{D}_{n}\middle|\mathcal{F}_{\sigma_{n}}\right]-\tilde{D}_{\mathcal{T}_{m}}\leq-\varepsilon^{2}\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)},A_{\delta}\right)$\mbox{}\hfil\phantom{********************************}\\\
&\leq\exp\left\\{-\frac{\varepsilon^{4}\delta\log\log\left(\delta
m\right)}{16\varepsilon}\right\\}.\end{split}$ (100)

Now, define the event

$\begin{split}B_{1}(\delta,\varepsilon,m):=A_{\delta}\cap\left\\{\tilde{D}_{(1+\varepsilon)\mathcal{T}_{m}}\geq\left(1+\frac{3}{4}\frac{\varepsilon(1-\varepsilon)}{(1+\varepsilon)}-\varepsilon^{2}\right)\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}\right\\}.\end{split}$
(101)

By equations
$(\ref{eq:degreediv22},\ref{eq:degreediv24b},\ref{eq:degreediv25})$, we obtain

$\begin{split}\mathbb{P}_{\tilde{G}}\left(B_{1}(\delta,\varepsilon,m)^{c}\right)\leq\mathbb{P}_{\tilde{G}}(A_{\delta}^{c})+2\exp\left\\{-\frac{\varepsilon^{3}\delta\log\log\left(\delta
m\right)}{16}\right\\}.\end{split}$ (102)

Now, define

$g_{\varepsilon}:=1+\frac{3}{4}\frac{\varepsilon(1-\varepsilon)}{(1+\varepsilon)}-\varepsilon^{2},$

We repeat the same proof on the event $B_{1}(\delta,\varepsilon,m)$ now for
time steps between $(1+\varepsilon)\mathcal{T}_{m}$ and
$(1+\varepsilon)^{2}\mathcal{T}_{m}$, defining again a stopping time

$\eta_{2}:=\inf\left\\{s\geq(1+\varepsilon)\mathcal{T}_{m};\tilde{D}_{s}<(1-\varepsilon)g_{\varepsilon}\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}\right\\},$

and proving inequalities analogous to
$(\ref{eq:degreediv22}\ref{eq:degreediv24},\ref{eq:degreediv24b})$. In this
way, we can define the event

$\begin{split}B_{2}(\delta,\varepsilon,m):=B_{1}(\delta,\varepsilon,m)\cap\left\\{\tilde{D}_{(1+\varepsilon)^{2}\mathcal{T}_{m}}\geq
g_{\varepsilon}^{2}\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}\right\\}\end{split}$
(103)

and show that

$\begin{split}\mathbb{P}_{\tilde{G}}\left(B_{2}(\delta,\varepsilon,m)^{c}\right)\leq\mathbb{P}_{\tilde{G}}(A_{\delta}^{c})+2\exp\left\\{-\frac{\varepsilon^{3}\delta\log\log\left(\delta
m\right)}{16}\right\\}+\exp\left\\{-\frac{\varepsilon^{3}\delta
g_{\varepsilon}^{2}\log\log\left(\delta
m\right)}{16(1+\varepsilon)}\right\\}.\end{split}$ (104)

We define inductively, for $n\in\mathbb{N}$,

$\begin{split}B_{n+1}(\delta,\varepsilon,m):=B_{n}(\delta,\varepsilon,m)\cap\left\\{\tilde{D}_{(1+\varepsilon)^{n+1}\mathcal{T}_{m}}\geq
g_{\varepsilon}^{n+1}\sqrt{\bar{\delta}\mathcal{T}_{m}\log\log\left(\bar{\delta}\mathcal{T}_{m}\right)}\right\\},\end{split}$
(105)

and prove in the same way that

$\begin{split}\mathbb{P}_{\tilde{G}}\left(B_{n}(\delta,\varepsilon,m)^{c}\right)\leq\mathbb{P}_{\tilde{G}}(A_{\delta}^{c})+2\sum_{k=1}^{n}\exp\left\\{-\frac{\varepsilon^{3}\delta
g_{\varepsilon}^{2(k-1)}\log\log\left(\delta
m\right)}{16(1+\varepsilon)^{k-1}}\right\\}.\end{split}$ (106)

We note that $\\{\tilde{D}_{k}\\}_{k\geq 1}$ is transient on $\bigcap_{n\geq
1}B_{n}(\delta,\varepsilon,m)$. This implies

$\begin{split}\mathbb{P}_{\tilde{G}}\left(\\{\tilde{D}_{k}\\}_{k\geq 1}\text{
is transient}\right)\geq
1-\mathbb{P}_{\tilde{G}}\left(A^{c}_{\delta}\right)-2\sum_{k=1}^{\infty}\exp\left\\{-\frac{\varepsilon^{3}\delta
g_{\varepsilon}^{2(k-1)}\log\log\left(\delta
m\right)}{16(1+\varepsilon)^{k-1}}\right\\}.\end{split}$ (107)

We note however that for $\varepsilon$ sufficiently small,
$g_{\varepsilon}^{2}>(1+\varepsilon)$. Choosing such an $\varepsilon$, we can
then choose $\delta$ arbitrarily small, then $m$ arbitrarily large depending
on $\delta$ in order to make the above right hand side as close as we want to
$1$. This implies the result.

∎

We now have all the tools needed for the proof of the main result of this
section, which states that there exist only one leader, vertex with maximum
degree, and its degree is much larger than the degree of its adversaries. In
general lines, we first prove that the set of candidates for the leadership is
finite almost surely. Then, Lemma 5.2 gives us that only one of then can have
the largest degree.

###### Proof of Theorem 1.4.

If $f\in\mathrm{RES}(-\gamma)$ with $\gamma\in[0,1)$, by Lemma 3.1, the
monotonicity of $\phi$, the fact that $\tau_{i}\geq i$, and Equation (65), we
know that

$\mathbb{P}\left(\exists s\geq
1,\frac{d_{s}(i)}{\phi(s)}\geq\frac{1}{\sqrt{\phi(i)}}\middle|\tau_{i}\right)\leq\exp\left\\{-C\sqrt{\phi(\tau_{i})}\right\\}\leq\exp\left\\{-Ci^{1/4}\right\\}.$
(108)

For $f\equiv p$, Theorem 3.3 and the fact that $F^{-1}(i)=i/p$ imply an
analogous inequality. By the Borel-Cantelli Lemma, there exists a random
integer $M>0$ such that, for every $i\geq M$,

$d_{s}(i)\leq\frac{\phi(s)}{\sqrt{\phi(i)}}.$ (109)

Then, by Theorem 3.5, there exists $N_{0}$ such that, for every $s\geq N_{0}$,

$\max_{i\in V(G_{s}(f))}d_{s}(i)\geq\frac{\phi(s)}{\phi(N_{0})}.$ (110)

But

$\frac{\phi(s)}{\sqrt{\phi(i)}}\geq\frac{\phi(s)}{\phi(N_{0})}\implies\phi(i)\leq\phi(N_{0})^{2}\implies
i\leq\phi(N_{0})^{4},$ (111)

since $\phi(i)\geq\sqrt{i}$ by the definition of $\phi$ and the fact that
$f(s)\leq 1$. Defining the random variable

$i_{0}:=\max\\{i\in\mathbb{N};i\leq\phi(N_{0})^{4}\\},$ (112)

we obtain that only the first $M+i_{0}$ vertices can be a candidate for the
vertex with maximum degree. At the same time, we know by Lemma 5.2 that the
distance between the degrees of any finite number of given vertices goes to
infinity almost surely. This finishes the proof of the result. ∎

##  6\. Central limit theorems

In this section we prove a Central Limit Theorem for the scaled maximum degree
process $\\{M_{t}\\}_{t\geq 1}$. We begin by taking a step back and proving a
CLT for the degree of a fixed vertex. Then, this result combined with Theorem
1.4 allows us to extend the CLT for the degree of a single vertex to the
maximum degree.

######  Theorem 6.1 (CLT for the degree of a vertex).

Let $f$ be a monotone non-increasing edge-step function such that (V)∞ holds.
Denoting by $\mathcal{N}$ a normal random variable, independent from
$\zeta_{i}$, with expectation $0$ and variance $1$, we have

  * •

if (S)c holds and if either (Const)p or (D)0 holds, then

$\sqrt{\phi(s)}\left(\frac{d_{s}(i)}{\phi(s)}-\zeta_{i}\right)\implies\sqrt{\zeta_{i}}\mathcal{N};$
(113)

  * •

if (S) holds, then, denoting

$\xi(\infty)=\lim_{s\to\infty}\phi(s)s^{-1}>0,$

we have

$\sqrt{\phi(s)}\left(\frac{d_{s}(i)}{\phi(s)}-\zeta_{i}\right)\implies\sqrt{\zeta_{i}\left(1-\frac{\xi(\infty)}{2}\zeta_{i}\right)}\mathcal{N}.$
(114)

###### Proof.

In the beginning it will again be important to use the conditioned measure
$\mathbb{P}_{i,t_{i}}$. We will use Corollary $4.2.1$ from [7] (cf. the proof
of Theorem $4.1$ (i) of [16], or Corollary $3.5$ of [14] together with the
discussion after Equation $(3.7)$ in the same book). Start by defining the
martingale difference array $(\kappa_{s}^{n})_{n\in\mathbb{N},s\geq n}$:

$\begin{split}\kappa_{s}^{n}&:=\sqrt{\phi(n)}\left(\frac{d_{s+1}(i)}{\phi(s+1)}-\frac{d_{s}(i)}{\phi(s)}\right)\\\
&=\sqrt{\phi(n)}\left(\frac{\Delta
d_{s}(i)}{\phi(s+1)}-\frac{d_{s}(i)}{s\phi(s+1)}\left(1-\frac{f(s+1)}{2}\right)\right),\end{split}$
(115)

the second equality following by the same reasoning as in (3). We note that,
by Proposition 4.1, $\mathbb{P}_{i,t_{i}}$-a.s.,

$\sum_{s=n}^{\infty}\kappa_{s}^{n}=\sqrt{\phi(n)}\left(\tilde{\zeta}_{i,t_{i}}-\frac{d_{n}(i)}{\phi(n)}\right).$
(116)

We will need to study the quantity

$\sum_{s=n}^{\infty}\mathbb{E}_{i,t_{i}}\left[(\kappa_{s}^{n})^{2}\middle|\mathcal{F}_{s}\right]=\phi(n)\sum_{s=n}^{\infty}\mathbb{E}_{i,t_{i}}\left[\left(\frac{\Delta
d_{s}(i)}{\phi(s+1)}-\frac{d_{s}(i)}{s\phi(s+1)}\left(1-\frac{f(s+1)}{2}\right)\right)^{2}\middle|\mathcal{F}_{s}\right].$

Note that, by the same reasoning as in (3),

$\begin{split}\mathbb{P}_{i,t_{i}}\left(\Delta
d_{s}(i)=1\middle|\mathcal{F}_{s}\right)&=f(s+1)\frac{d_{s}(i)}{2s}+2\left(1-f(s+1)\right)\frac{d_{s}(i)}{2s}\left(1-\frac{d_{s}(i)}{2s}\right)\\\
\mathbb{P}_{i,t_{i}}\left(\Delta
d_{s}(i)=2\middle|\mathcal{F}_{s}\right)&=\left(1-f(s+1)\right)\frac{d_{s}(i)^{2}}{4s^{2}},\end{split}$
(117)

which yields

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{E}_{i,t_{i}}\left[(\Delta
d_{s}(i))^{2}\middle|\mathcal{F}_{s}\right]$\mbox{}\hfil\phantom{****}\\\
&=f(s+1)\frac{d_{s}(i)}{2s}+2\left(1-f(s+1)\right)\frac{d_{s}(i)}{2s}\left(1-\frac{d_{s}(i)}{2s}\right)+4\left(1-f(s+1)\right)\frac{d_{s}(i)^{2}}{4s^{2}}\\\
&=\frac{d_{s}(i)}{s}\left(1-\frac{f(s+1)}{2}\right)+2\left(1-f(s+1)\right)\frac{d_{s}(i)^{2}}{4s^{2}}.\end{split}$
(118)

Using the above equation and (3), we obtain,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{E}_{i,t_{i}}\left[\left(\frac{\Delta
d_{s}(i)}{\phi(s+1)}-\frac{d_{s}(i)}{s\phi(s+1)}\left(1-\frac{f(s+1)}{2}\right)\right)^{2}\middle|\mathcal{F}_{s}\right]$\mbox{}\hfil\\\
&=\mathbb{E}_{i,t_{i}}\left[\frac{(\Delta
d_{s}(i))^{2}}{\phi(s+1)^{2}}-2\frac{d_{s}(i)\Delta
d_{s}(i)}{s\phi(s+1)^{2}}\left(1-\frac{f(s+1)}{2}\right)+\frac{d_{s}(i)^{2}}{s^{2}\phi(s+1)^{2}}\left(1-\frac{f(s+1)}{2}\right)^{2}\middle|\mathcal{F}_{s}\right]\\\
&=\frac{\mathbb{E}_{i,t_{i}}\left[(\Delta
d_{s}(i))^{2}\middle|\mathcal{F}_{s}\right]}{\phi(s+1)^{2}}-2\frac{d_{s}(i)^{2}}{s^{2}\phi(s+1)^{2}}\left(1-\frac{f(s+1)}{2}\right)^{2}+\frac{d_{s}(i)^{2}}{s^{2}\phi(s+1)^{2}}\left(1-\frac{f(s+1)}{2}\right)^{2}\\\
&=\frac{d_{s}(i)}{s\phi(s+1)^{2}}\left(1-\frac{f(s+1)}{2}\right)+\left(1-f(s+1)\right)\frac{d_{s}(i)^{2}}{2s^{2}\phi(s+1)^{2}}-\frac{d_{s}(i)^{2}}{s^{2}\phi(s+1)^{2}}\left(1-\frac{f(s+1)}{2}\right)^{2}.\end{split}$

Using Proposition 4.2, define the variable

$\epsilon_{i,t_{i}}^{\prime}(s):=1-\frac{d_{s}(i)}{\phi(s+1)\tilde{\zeta}_{i,t_{i}}},$

which goes to $0$ as $s$ goes to infinity $\mathbb{P}_{i,t_{i}}$-a.s. by
Proposition 4.1. The above equation then yields

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{E}_{i,t_{i}}\left[\left(\frac{\Delta
d_{s}(i)}{\phi(s+1)}-\frac{d_{s}(i)}{s\phi(s+1)}\left(1-\frac{f(s+1)}{2}\right)\right)^{2}\middle|\mathcal{F}_{s}\right]$\mbox{}\hfil\phantom{***}\\\
&=\frac{\tilde{\zeta}_{i,t_{i}}(1-\epsilon_{i,t_{i}}^{\prime}(s))}{s\phi(s+1)}\left(1-\frac{f(s+1)}{2}\right)+\left(1-f(s+1)\right)\frac{\tilde{\zeta}_{i,t_{i}}^{2}(1-\epsilon_{i,t_{i}}^{\prime}(s))^{2}}{2s^{2}}\\\
&\quad-\frac{\tilde{\zeta}_{i,t_{i}}^{2}(1-\epsilon_{i,t_{i}}^{\prime}(s))^{2}}{s^{2}}\left(1-\frac{f(s+1)}{2}\right)^{2}.\end{split}$
(119)

For $f$ such that $\sum_{s=1}^{\infty}f(s)/s=\infty$, we have that
$\phi(n)/n\to 0$ as $n\to\infty$ and therefore

$\phi(n)\sum_{s=n}^{\infty}\left|\left(1-f(s+1)\right)\frac{\tilde{\zeta}_{i,t_{i}}^{2}(1-\epsilon_{i,t_{i}}^{\prime}(s))^{2}}{2s^{2}}-\frac{\tilde{\zeta}_{i,t_{i}}^{2}(1-\epsilon_{i,t_{i}}^{\prime}(s))^{2}}{s^{2}}\left(1-\frac{f(s+1)}{2}\right)^{2}\right|\xrightarrow{n\to\infty}0.$
(120)

If $f\equiv p$ equations (119) and (93) imply

$\begin{split}\sum_{s=n}^{\infty}\mathbb{E}_{i,t_{i}}\left[(\kappa_{s}^{n})^{2}\middle|\mathcal{F}_{s}\right]&=o_{n}(1)+\phi(n)(1+o_{n}(1))(1-p/2)\tilde{\zeta}_{i,t_{i}}\sum_{s=n}^{\infty}s^{-2+p/2}\\\
&=o_{n}(1)+\tilde{\zeta}_{i,t_{i}}\phi(n)n^{-1+p/2}\\\
&\xrightarrow{n\to\infty}\tilde{\zeta}_{i,t_{i}}.\end{split}$ (121)

If $f(t)\downarrow 0$ but $\sum_{s=1}^{\infty}f(s)/s=\infty$, then, recalling
the definition of the slowly varying function $\xi$ from (16), and using
Theorem B.3, we obtain

$\begin{split}\sum_{s=n}^{\infty}\mathbb{E}_{i,t_{i}}\left[(\kappa_{s}^{n})^{2}\middle|\mathcal{F}_{s}\right]&=o_{n}(1)+\phi(n)(1+o_{n}(1))\tilde{\zeta}_{i,t_{i}}\sum_{s=n}^{\infty}s^{-2}\xi(s)^{-1}\\\
&=o_{n}(1)+(1+o_{n}(1))\tilde{\zeta}_{i,t_{i}}\phi(n)(n\xi(n))^{-1}\\\
&\xrightarrow{n\to\infty}\tilde{\zeta}_{i,t_{i}}.\end{split}$ (122)

Finally, if $\sum_{s=1}^{\infty}f(s)s^{-1}<\infty$, we recall that the limit
of $\phi(s)/s$ as $s$ goes to infinity exists, and again by Theorem B.3,

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\sum_{s=n}^{\infty}\mathbb{E}_{i,t_{i}}\left[(\kappa_{s}^{n})^{2}\middle|\mathcal{F}_{s}\right]$\mbox{}\hfil\\\
&=\phi(n)\tilde{\zeta}_{i,t_{i}}\sum_{s=n}^{\infty}\left((1+o_{n}(1))s^{-2}\xi(s)^{-1}+(1+o_{n}(1))\tilde{\zeta}_{i,t_{i}}2^{-1}s^{-2}-(1+o_{n}(1))\tilde{\zeta}_{i,t_{i}}s^{-2}\right)\\\
&=(1+o_{n}(1))\tilde{\zeta}_{i,t_{i}}\phi(n)(n\xi(n))^{-1}+(1+o_{n}(1))2^{-1}\tilde{\zeta}_{i,t_{i}}^{2}\phi(n)n^{-1}-(1+o_{n}(1))\tilde{\zeta}_{i,t_{i}}^{2}\phi(n)n^{-1}\\\
&\xrightarrow{n\to\infty}\tilde{\zeta}_{i,t_{i}}\left(1-\frac{\xi(\infty)}{2}\tilde{\zeta}_{i,t_{i}}\right).\end{split}$
(123)

We note that in every case, by (115) and the fact that $d_{s}(i)\leq 2s$ and
$\Delta d_{s}(i)\leq 2$,

$\sup_{s\geq
n}|\kappa_{s}^{n}|\leq\sqrt{\phi(n)}\cdot\frac{4}{\phi(n+1)}\xrightarrow{n\to\infty}0,$
(124)

and therefore the following Lindenberg-type condition is satisfied of every
$\varepsilon>0$:

$\sum_{s=n}^{\infty}\mathbb{E}_{i,t_{i}}\left[(\kappa_{s}^{n})^{2}\mathds{1}\\{|\kappa_{s}^{n}|>\varepsilon\\}\middle|\mathcal{F}_{s}\right]\xrightarrow{n\to\infty}0,$
(125)

since the sum is identically equal to $0$ for large enough $n$. Equations
$(\ref{eq:dclt1},\ref{eq:dclt7},\ref{eq:dclt8},\ref{eq:dclt9},\ref{eq:dclt11})$
imply that we are then under the hypotheses of Corollary 4.2.1 of from [7],
which in turn implies, together with the symmetry of the normal distribution,
that $\eqref{eq:degcltsuminfty}$ and (114) hold true in
$\mathbb{P}_{i,t_{i}}$. To end the proof, we assume that we are in the case of
Equation $\eqref{eq:degcltsuminfty}$, the other case being proven in the exact
same manner. Given some number $a\in\mathbb{R}$,

$\begin{split}\mathbb{P}\left(\sqrt{\phi(s)}\left(\frac{d_{s}(i)}{\phi(s)}-\zeta_{i}\right)\leq
a\right)&=\sum_{t_{i}=1}^{\infty}\mathbb{P}(\tau_{i}=t_{i})\mathbb{P}_{i,t_{i}}\left(\sqrt{\phi(s)}\left(\frac{d_{s}(i)}{\phi(s)}-\tilde{\zeta}_{i,t_{i}}\right)\leq
a\right)\\\
&=\sum_{t_{i}=1}^{\infty}\mathbb{P}(\tau_{i}=t_{i})\left[\mathbb{P}_{i,t_{i}}\left(\sqrt{\tilde{\zeta}_{i,t_{i}}}\mathcal{N}\leq
a\right)+o_{s}^{i,t_{i}}(1)\right]\\\
&=\mathbb{P}\left(\sqrt{\zeta_{i}}\mathcal{N}\leq
a\right)+\sum_{t_{i}=1}^{\infty}\mathbb{P}(\tau_{i}=t_{i})o_{s}^{i,t_{i}}(1),\end{split}$
(126)

where $o_{s}^{i,t_{i}}(1)$ is a function of $s$ depending on $i$ and $t_{i}$
that goes to $0$ as $s\to\infty$ and is uniformly bounded by $2$ in the
$\ell_{\infty}$-norm, since it is the difference between two probabilities.
Now, for some $N\in\mathbb{N}$, we have

$\begin{split}\left|\mathbb{P}\left(\sqrt{\phi(s)}\left(\frac{d_{s}(i)}{\phi(s)}-\zeta_{i}\right)\leq
a\right)-\mathbb{P}\left(\sqrt{\zeta_{i}}\mathcal{N}\leq
a\right)\right|\leq\sum_{t_{i}=1}^{N}o_{s}^{i,t_{i}}(1)+2\mathbb{P}(\tau_{i}>N).\end{split}$
(127)

Since $\sum_{s\geq 1}f(s)=\infty$, $\mathbb{P}(\tau_{i}>N)$ goes to $0$ with
$N$. Choosing $N$ large and then choosing $s$ sufficiently large, depending on
$N$, we show that the right hand side of the above equation can be made
arbitrarily small, finishing the proof of the theorem. ∎

We can then prove the maximum degree CLT. But before, we recall some
definitions

$\displaystyle X_{s,i}$ $\displaystyle:=\frac{d_{s}(i)}{\phi(s)},\quad
M[s,i]:=\max_{1\leq k\leq i}\\{X_{s,k}\\},\quad M_{s}:=\max_{k\geq
1}\\{X_{s,k}\\},$ $\displaystyle\mu(i)$ $\displaystyle:=\max_{1\leq k\leq
i}\\{\zeta_{k}\\},\quad\mu:=\sup_{k\geq 1}\\{\zeta_{k}\\}.$

And also recall from the Persistent Leadership Theorem 1.4 the definition of
$U_{max}(s,N)$, which is the event where there exist only one vertex with
maximum degree at time $s$ and all the remaining vertices have degree smaller
than the maximum minus $N$.

###### Proof of Theorem 1.3: CLT for the maximum degree.

The proof is mostly analogous to that of Theorem 6.1. The main issue is that
$M_{s}$ is usually not a martingale, but it does behave like one if we know
that there exists only one vertex with the maximum degree.

We will prove the result for the process $M_{s}\mathds{1}\\{U_{{\rm
max}}(s,3)\\}$, since $M_{s}\mathds{1}\\{U_{{\rm max}}(s,3)^{c}\\}$ _is_ $0$
at all but a finite number of times a.s., this will imply the theorem. Define

$\begin{split}\tilde{\kappa}_{s}^{n}&:=\sqrt{\phi(n)}\left(M_{s+1}\mathds{1}\\{U_{{\rm
max}}(s+1,3)\\}-M_{s}\mathds{1}\\{U_{{\rm max}}(s,3)\\}\right)\end{split}$
(128)

By Theorem 1.1 we have, $\mathbb{P}_{i,t_{i}}$-a.s. for all but finitely many
integers $n$,

$\sum_{s=n}^{\infty}\tilde{\kappa}_{s}^{n}=\sqrt{\phi(n)}\left(\mu-
M_{n}\mathds{1}\\{U_{{\rm max}}(s,3)\\}\right).$ (129)

We have

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle\mathbb{E}\left[(\tilde{\kappa}_{s}^{n})^{2}\middle|\mathcal{F}_{s}\right]$\mbox{}\hfil\quad\\\
&=\phi(n)\mathbb{E}\left[\left(M_{s+1}\mathds{1}\\{U_{{\rm
max}}(s+1,3)\\}-M_{s}\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\right)^{2}\middle|\mathcal{F}_{s}\right]\\\
&=\phi(n)\mathbb{E}\left[\left(M_{s+1}\left(\mathds{1}\\{U_{{\rm
max}}(s+1,3)\\}-\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\right)+\left(M_{s+1}-M_{s}\right)\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\right)^{2}\middle|\mathcal{F}_{s}\right]\\\
&=\phi(n)\mathbb{E}\left[M_{s+1}^{2}\left(\mathds{1}\\{U_{{\rm
max}}(s+1,3)\\}-\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\right)^{2}\middle|\mathcal{F}_{s}\right]\\\
&\quad+2\phi(n)\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\mathbb{E}\left[M_{s+1}\left(M_{s+1}-M_{s}\right)\left(\mathds{1}\\{U_{{\rm
max}}(s+1,3)\\}-\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\right)\middle|\mathcal{F}_{s}\right]\\\
&\quad+\phi(n)\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\mathbb{E}\left[(M_{s+1}-M_{s})^{2}\middle|\mathcal{F}_{s}\right].\end{split}$

Observe that in order for $\mathds{1}\\{U_{{\rm
max}}(s+1,3)\\}-\mathds{1}\\{U_{{\rm max}}(s,3)\\}$ to be different than $0$,
either $U_{{\rm max}}(s,3)$ does not take place, or $U_{{\rm max}}(s,3)$
happens but at time $s+1$ the degree of some vertex gets within distance $3$
of the maximum degree. Since, a vertex can only increase its degree by $1$ or
$2$ at each step, we obtain

$\left|\mathds{1}\\{U_{{\rm max}}(s+1,3)\\}-\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\right|\leq\mathds{1}\left\\{U_{{\rm
max}}(s,5)^{c}\right\\}+\mathds{1}\left\\{U_{{\rm max}}(s,3)^{c}\right\\}.$
(130)

Together we Lemma 1.4, the above equations imply that, almost surely, for
every $n$ and all but a finite number of integers $s\in\mathbb{N}$,

$\begin{split}\mathbb{E}\left[(\tilde{\kappa}_{s}^{n})^{2}\middle|\mathcal{F}_{s}\right]=\phi(n)\mathds{1}\\{U_{{\rm
max}}(s,3)\\}\mathbb{E}\left[(M_{s+1}-M_{s})^{2}\middle|\mathcal{F}_{s}\right].\end{split}$
(131)

In the event $U_{{\rm max}}(s,3)$, there exists at times $s$ and $s+1$ a
unique vertex $\tilde{v}$ with the maximum degree, and the only way for the
maximum degree to increase at time $s+1$ is if the degree of $\tilde{v}$ is
increased. The right hand side of the above equation can then be studied in
the same way as in Theorem 6.1, substituting $\tilde{\zeta}_{i,t_{i}}$ by
$\mu$ and $d_{s}(i)\phi(s)^{-1}$ by $M_{s}$. Equations analogous to
($\ref{eq:dclt8},\ref{eq:dclt9},\ref{eq:dclt10},\ref{eq:dclt11}$) are derived
and the proof of the result follows from Corollary $4.2.1$ from [7]. ∎

##  7\. Application: bootstrap percolation

This section is devoted to understand the evolution of the Bootstrap
Percolation process on $G_{t}(f)$, when $f$ satisfies condition (S) and
belongs to ${\rm RES}(-\gamma)$, with $\gamma\in(0,1)$. We are going to prove
Theorem 1.5, which essentially states that, over the typical graph, the
bootstrap percolation process have the outbreak phenomenon for any initial
amount of infected vertices which grows to infinity and threshold $r\leq 2$,
i.e., even for small initial infected vertices the infectious spreads to a
positive fraction of the whole graph. The reader may recall the definition of
the bootstrap percolation at page 1.3.3.

###### Proof of Theorem1.5.

We begin by recalling some properties of $G_{t}(f)$ and $f$ when $f$ satisfies
the summability condition (S) and belongs to ${\rm RES}(-\gamma)$, for
$\gamma\in[0,1)$. First, from (S) and the fact that $f\in{\rm RES}(-\gamma)$
we have that

$\lim_{t\to\infty}f(t)\log t=0.$

And by the definition of the normalizing factor $\phi$, recall () which
implies that under (S) there exist two $f$-dependent constants $C_{1}$ and
$C_{2}$ such that

$C_{1}t\leq\phi(t)\leq C_{2}t.$ (132)

Moreover, by the Karamata’s Theorem (Theorem B) we have that

$\mathbb{E}V_{t}(f)\sim f(t)t\implies\mathbb{E}V_{t}(f)\leq\frac{5}{4}f(t)t,$
(133)

for large enough $t$. In the light of the above relation, we also point out
that we may suppose that the sequence $\\{a_{t}\\}_{t\in\mathbb{N}}$ is given
in such way that $a_{t}\ll f(t)t$. Otherwise, by the definition of the
Bootstrap percolation process $|\mathcal{I}_{0}|\approx a_{t}\geq cf(t)t$,
i.e., if $a_{t}$ is too large, the initial set of infected vertices already
represents a positive proportion of the total number of vertices, w.h.p., and
we have nothing to prove.

Now, let $g$ and $h$ be the following functions

$\begin{split}g(t):=\frac{1}{f(t)};\;h(t):=\frac{C_{1}}{2r^{2}C_{2}}\cdot\frac{g(t)}{\log(t)}.\end{split}$
(134)

And define an important property we expect the typical graph generated by the
graph process satisfies. Let $\mathcal{P}^{1}_{t}$ be the following class of
(multi)graphs

$\begin{split}\mathcal{P}^{1}_{t}:=\left\\{G=(V,E):|V|\leq\frac{3}{2}f(t)t\text{
and }\exists v^{*}\in V(G),\text{with
}d_{G}v^{*}\geq\frac{C_{1}t}{C_{2}h(a_{t})}\right\\}.\end{split}$ (135)

In words, $\mathcal{P}^{1}_{t}$ is the collection of multigraphs with
$O(f(t)t)$ vertices and containing a vertex $v^{*}$ whose degree is at least
$C_{1}C_{2}^{-1}t/h(a_{t})$, where $C_{1}$ and $C_{2}$ are the $f$-dependent
constants in (132). We say that a multigraph in $\mathcal{P}^{1}_{t}$ has
property $1$ and call the distinguishable vertex $v^{*}$ a star.

In the next lines we are going to prove that w.h.p $G_{t}(f)$ has the property
$1$. Now, by Theorem 3.5, choosing $N=h(a_{t})$, we have that

$\mathbb{P}\left(\exists i\in\\{1,2,\cdots,h(a_{t})\\},\text{ such that
}d_{t}(i)\geq\frac{C_{1}}{C_{2}}\frac{t}{h(a_{t})}\right)\geq
1-\exp\\{-C_{f}h(a_{t})\\}$ (136)

for another $f$-dependent constant $C_{f}$. Since $V_{t}(f)$ is sum of
independent Bernoulli random variables, Chernoff bound yields

$\mathbb{P}\left(V_{t}(f)\geq\frac{3}{2}f(t)t\right)\leq\exp\left\\{-\frac{12\mathbb{E}V_{t}(f)}{25}\right\\},$
(137)

which proves that $G_{t}(f)$ has property $1$ w.h.p.

Now, we require another property of the typical multigraph.

$\begin{split}\mathcal{P}^{2}_{t}:=\left\\{G=(V,E):|V|=O(f(t)t)\text{ and
}\exists H\subset G,\text{connected and with
}d_{G}H\geq\frac{t}{2}\right\\}.\end{split}$ (138)

In words, $\mathcal{P}^{2}_{t}$ represents those (multi)graphs on $O(f(t)t)$
vertices containing a subgraph whose degree is at least a constant times $t$.
We claim that $G_{2t}(f)$ also has property 2 w.h.p. Suppose for a moment that
$G_{t}(f)$ has property $1$ and let $v^{*}$ be its star. Also let $j$ be a
vertex whose degree is at least $g(t)$. Since $f$ is regularly varying
function with index $-\gamma\in(-1,0]$, it follows $g(t)=o(\sqrt{t})$, thus
there exists such $j$ w.h.p.

Now, fix $k\in\\{2,3,\cdots,r+1\\}$ and note that for all times
$s\in[(k-1)t,kt]$ we have

$\begin{split}\mathbb{P}\left(j\leftrightarrow v^{*}\text{at step
}s+1\;\middle|\;G_{s}(f),d_{t}(j)\geq g(t),v^{*}\text{ is a
star}\right)&=(1-f(s+1))\frac{d_{s}(j)d_{s}v^{*}}{2s^{2}}\\\
&\geq\frac{C_{1}}{4(r+1)^{2}C_{2}}\frac{g(t)t}{t^{2}h(a_{t})},\end{split}$
(139)

for sufficiently large $t$, since the degree of a vertex is increasing in $s$,
$s\leq(r+1)t$ and $f\searrow 0$. Thus, for each $k$, and recalling that
$a_{t}<t$, for all $t$, our choice of $h$ leads to

$\begin{split}\mathbb{P}\left(j\nleftrightarrow v^{*}\text{in
}G_{kt}\;\middle|\;G_{(k-1)t},d_{(k-1)t}(j)\geq g(t),v^{*}\text{ is a
star}\right)&\leq\left(1-\frac{C_{1}}{4(r+1)^{2}C_{2}}\frac{g(t)}{th(a_{t})}\right)^{t}\leq
e^{-2\log t}\end{split}$

Recalling that $G_{t}(f)$ has at most $t$ vertices deterministically, by an
union bound argument the above inequality allows us to say that w.h.p in time
interval $[(k-1)t,kt]$ all the vertices in $G_{t}(f)$ having degree at least
$g(t)$ end up sending at least one edge to the star in $G_{kt}(f)$. Therefore,
w.h.p all vertices in $G_{t}(f)$ having degree at least $g(t)$ actually send
at least $r$ edges to the star in $G_{(r+1)t}(f)$.

Finally, let $H_{t}$ be the subgraph of $G_{t}(f)$ composed by all vertices
whose degree is at least $g(t)$. Conditioning that $V_{t}(f)\leq 3f(t)t/2$
vertices, the sum of the degree of all vertices not in $H_{t}$ satisfies

$\sum_{v\notin H_{t}}d_{t}v<\frac{3}{2}g(t)f(t)t=\frac{3t}{2}.$ (140)

Since the sum of all degrees equals in $G_{t}(f)$ equals $2t$, by the above
inequality, $d_{t}H_{t}\geq t/2$, whenever $V_{t}(f)\leq 3f(t)t/2$, which
occurs w.h.p. This shows that whenever $G_{t}(f)$ has property $1$,
$G_{(r+1)t}$ has properties $1$ and $2$ with the extra feature that each
vertex in $H$ shares at least $r$ edges with $v^{*}$ w.h.p. Therefore,

$\mathbb{P}\left(G_{t}\notin\mathcal{P}^{2}_{t}\right)\leq\mathbb{P}\left(G_{t}\notin\mathcal{P}^{2}_{t},G_{t/r}\in\mathcal{P}^{1}_{t/r}\right)+\mathbb{P}\left(G_{t}\notin\mathcal{P}^{1}_{t}\right)=o(1).$
(141)

In the next lines we show that if $G_{t}(f)$ has property $2$ then the
subgraph $H_{t}$, seen as a subgraph of $G_{2rt}$, has at least $cf(t)t$
vertices sending $r$ edges to it, for a constant $c$, w.h.p. The way we prove
this is forcing a positive proportion of vertices of degree $1$ in $G_{t}(f)$
to connect in $H_{t}$ at time $2t$ and iterating the process $r$ times,
similarly to what we have done for $H_{t}$. For this, we need some
definitions. Denote by $N_{t}(1)$ the random variable which counts the number
of vertices having degree $1$ at time $t$. Also, let $A_{s}$ and $C_{s}$ be
the following random sets

$\begin{split}A_{s}:=\left\\{v\in N_{t}(1)\;\middle|\;v\nrightarrow
H_{t}\text{ up to time }s\right\\};\quad C_{s}=\left\\{v\in
N_{t}(1)\;\middle|\;v\rightarrow H_{t}\text{ up to time
}s\right\\}.\end{split}$ (142)

Observe that for all $s\in[t,2t]$ we have $N_{t}(1)=A_{s}\cup C_{s}$. In
words, $A_{s}$ is the set of those vertices of $N_{t}(1)$ which did not
connect to $H_{t}$ at none of the edges created at time between $t$ and $s$.
In this sense, we say a vertex in $A_{s}$ is available to connect to $H_{t}$.
On the other hand, $C_{s}$ contains exactly those that connected to $H_{t}$
between time $t$ and $s$.

At each step, we try to connect an available vertex to $H_{t}$ using an edge-
step. We are going to prove that w.h.p after $t$ steps $|C_{2t}|$ is a
positive proportion of $N_{t}(1)$. So, let $\\{Y_{s}\\}_{s\geq t}$ be the
following process

$Y_{s}:=\mathds{1}\left\\{\text{some vertex }v\text{ in }A_{s}\text{ connects
to }H_{t}\text{ at time }s\right\\}.$ (143)

Note that $|C_{2t}|=\sum_{s=t}^{2t}Y_{s}$. And consider the following stopping
time

$\eta:=\inf\left\\{s\geq t:|C_{s}|\geq N_{t}(1)/2\right\\},$ (144)

To simplify our writing, we will denote by $\mathbb{P}_{G_{t}}$ the law of the
graph process conditioned on a graph $G_{t}$ with property $2$. With this
notation in mind, observe that, for $s\in[t,2t]$, there exists a constant $c$
such that

$\mathbb{P}_{G_{t}}\left(Y_{s+1}=1\;\middle|\;G_{s}(f)\right)\geq(1-f(s+1))\frac{|A_{s}|d_{s}H_{t}}{2s^{2}}\geq\frac{c|A_{s}|}{t},$
(145)

since $d_{s}H_{t}\geq c^{\prime}t$. Then, by the definition of $\eta$, it also
follows that

$\mathbb{P}_{G_{t}}\left(Y_{s+1}=1,\eta>s\;\middle|\;G_{s}(f)\right)\geq\frac{cN_{t}/2}{t}\mathds{1}_{\\{\eta>s\\}}=:q\mathds{1}_{\\{\eta>s\\}}.$
(146)

The above inequality implies that on the event $\\{\eta>2t\\}$ the sum
$\sum_{s=t}^{2t}Y_{s}$ dominates a r.v. distributed as $\mathrm{bin}(t,q)$.
Then,

$\begin{split}\mathbb{P}_{G_{t}}\left(|C_{2t}|\leq\varepsilon
N_{t}(1)\right)&\leq\mathbb{P}_{G_{t}}\left(\mathrm{bin}(t,q)\leq\varepsilon
N_{t}(1),\eta>2t\right)+\mathbb{P}_{G_{t}}\left(|C_{2t}|\leq\varepsilon
N_{t}(1),\eta\leq 2t\right).\end{split}$ (147)

Choosing $\varepsilon<\min\\{c/2,1/2\\}$ and using Chernouff bounds, we obtain
that

$\begin{split}\mathbb{P}_{G_{t}}\left(|C_{2t}|\leq\varepsilon
N_{t}(1)\right)&\leq\mathbb{P}_{G_{t}}\left(\mathrm{bin}(t,q)\leq\varepsilon
N_{t}(1)\right)\leq e^{-cN_{t}(1)},\end{split}$ (148)

for some positive constant $c$, since $|C_{2t}|\geq N_{t}(1)/2$ on
$\\{\eta\leq 2t\\}$ and $\mathrm{bin}(t,q)$ has mean $cN_{t}/2$. The above
upper bound combined with inequality (141) and Theorem 2 of [2], which
guarantees that $N_{t}(1)$ is large enough, yields
$\mathbb{P}\left(|C_{2t}|\leq\varepsilon N_{t}(1)\right)$ is bounded from
above by

$\begin{split}\mathbb{P}\left(|C_{2t}|\leq\varepsilon
N_{t}(1),G_{t}(f)\in\mathcal{P}^{2}_{t},N_{t}(1)\geq
cf(t)t\right)+\mathbb{P}\left(G_{t}(f)\notin\mathcal{P}^{2}_{t}\text{ or
}N_{t}(1)\leq ctf(t)\right)=o(1).\end{split}$

Now we can iterate this argument with the set $C_{2t}$ instead of $N_{t}(1)$
to guarantee w.h.p that there exist at least $cf(t)t$ vertices sending at
least two edges to $H_{t}$ in $G_{3t}(f)$. This shows that there exists a
constant $c$ such that w.h.p $G_{t}(f)$ belongs to the family of (multi)graphs
below

$\begin{split}\mathcal{P}^{3}_{t}:=\left\\{G\in\mathcal{P}^{2}_{t}:\exists
S\subset G\text{ s.t. }|S|\geq cf(t)t\text{ and all }v\in S\text{ connects
}r\text{ times to }H_{t}\right\\}.\end{split}$ (149)

Finally, fixed a sequence $\\{a_{t}\\}_{t\in\mathbb{N}}$ and $r\geq 2$, we let
the family $\mathcal{P}^{3}_{t}$ constructed as above be our family
$\mathcal{G}_{t}$. Now we are left to prove that the bootstrap percolation
process on a (multi)graph in the collection $\mathcal{G}_{t}$ and parameters
$a_{t}$ and $r$ w.h.p has an outbreak of infection.

Summarizing all we have proven about $G_{t}(f)$ so far, a (multi)graph in
$\mathcal{G}_{t}$ has the following structure:

  1. (1)

$G_{t}(f)$ has at most $cf(t)t$ vertices;

  2. (2)

There exists a star $v^{*}\in G_{t}(f)$ such that

$d_{t}v^{*}\geq\frac{C_{1}}{C_{2}}\cdot\frac{t}{h(a_{t})}.$

And consequently

$\Gamma_{t}(v^{*})\geq C\frac{f(t)t}{h(a_{t})},$ (150)

where $\Gamma_{t}(v^{*})$ denotes the number of neighbors of $v^{*}$. We
explain the above lower bound latter.

  3. (3)

All vertices of degree at least $g(t)$ are connected $r$ times to $v^{*}$.
This is the subgraph $H_{t}$;

  4. (4)

There exists a subset $S\subset G_{t}$ of order $f(t)t$ whose elements are
connected to $H_{t}$ at least $r$ times.

To see why (150) holds, observe that if $v^{*}$ has degree at least
$Ct/h(a_{t})$ at time $t$, then for $s\in[t,2t]$, we have that

$\mathbb{P}\left(\Delta\Gamma_{s}(v^{*})\geq
1,\mid\mathcal{F}_{s},d_{t}v^{*}\geq C\cdot\frac{t}{h(a_{t})}.\right)\geq
Cf(s)\cdot\frac{t}{2sh(a_{t})}\geq\frac{C^{\prime}f(2t)}{h(a_{t})}.$

Thus, the number of neighbors at time $2t$ dominates a binomial random
variable with parameters $t$ and $C^{\prime}f(2t)/h(a_{t})$.

Having all the properties above in mind, we start the bootstrap percolation
process. Observe that the number of infected neighbors of $v^{*}$ dominates a
binomial random variable with parameters $Cf(t)t/h(a_{t})$ and $a_{t}/f(t)t$.
Thus, at the initial round, w.h.p, $v^{*}$ has at least $r$ infected
neighbors. At the second round the star gets infected and this is enough to
spread the infection. At the third round all the subgraph $H_{t}$ gets
infected and finally at the next round $S$ gets infected. This proves that in
four steps a positive proportion of $G_{t}(f)$ gets infected and proves our
theorem. ∎

##  Appendix A Martingale concentration inequalities

For the sake of completeness we state here two useful concentration
inequalities for martingales which are used throughout the paper.

######  Theorem A.1 (Azuma-Höffeding Inequality - see [8]).

Let $(M_{n},\mathcal{F})_{n\geq 1}$ be a martingale satisfying

$\lvert M_{i+1}-M_{i}\rvert\leq a_{i}$

Then, for all $\l>0$ we have

$\mathbb{P}\left(|M_{n}-M_{0}|>\lambda\right)\leq\exp\left(-\frac{\lambda^{2}}{\sum_{i=1}^{n}a_{i}^{2}}\right).$

######  Theorem A.2 (Freedman’s Inequality - see [13]).

Let $(M_{n},\mathcal{F}_{n})_{n\geq 1}$ be a (super)martingale. Write

$V_{n}:=\sum_{k=1}^{n-1}\mathbb{E}\left[(M_{k+1}-M_{k})^{2}\middle|\mathcal{F}_{k}\right]$

and suppose that $M_{0}=0$ and

$\lvert M_{k+1}-M_{k}\rvert\leq R,\textit{ for all }k.$

Then, for all $>0$ we have

$\mathbb{P}\left(M_{n}\geq\lambda,V_{n}\leq\sigma^{2},\textit{ for some
}n\right)\leq\exp\left(-\frac{\lambda^{2}}{2\sigma^{2}+2R\lambda/3}\right).$

##  Appendix B Karamata theory

The three following results are used throughout the paper.

######  Corollary B.1 (Representation theorem - Theorem $1.4.1$ of [5]).

Let $f$ be a continuous regularly varying function with index of regular
variation $\gamma$. Then, there exists a slowly varying function $\ell$ such
that

$f(t)=t^{\gamma}\ell(t),$ (151)

for all $t$ in the domain of $f$.

######  Corollary B.2.

Let $f$ be a continuous regularly varying function with index of regular
variation $\gamma<0$. Then,

$f(x)\to 0,$ (152)

as $x$ tends to infinity. Moreover, if $\ell$ is a slowly varying function,
then for every $\varepsilon>0$

$x^{-\varepsilon}\ell(x)\to 0\text{ and }x^{\varepsilon}\ell(x)\to\infty$
(153)

###### Proof.

Comes as a straightforward application of Theorem $1.3.1$ of [5] and Corollary
B.1. ∎

######  Theorem B.3 (Karamata’s theorem - Proposition $1.5.8$ of [5]).

Let $\ell$ be a continuous slowly varying function and locally bounded in
$[x_{0},\infty)$ for some $x_{0}\geq 0$. Then

  * (a)

for $\alpha>-1$

$\int_{x_{0}}^{x}t^{\alpha}\ell(t)dt\sim\frac{x^{1+\alpha}\ell(x)}{1+\alpha}.$
(154)

  * (b)

for $\alpha<-1$

$\int_{x}^{\infty}t^{\alpha}\ell(t)dt\sim\frac{x^{1+\alpha}\ell(x)}{1+\alpha}.$
(155)

Acknowledgements  C.A. was partially supported by the Deutsche
Forschungsgemeinschaft (DFG). R.R. was supported by the project Stochastic
Models of Disordered and Complex Systems. The Stochastic Models of Disordered
and Complex Systems is a Millennium Nucleus (NC120062) supported by the
Millenium Scientific Initiative of the Ministry of Science and Technology
(Chile).

## References

  * [1] C. Alves, R. Ribeiro, and R. Sanchis.  Agglomeration in a preferential attachment random graph with edge-steps.  arXiv preprint arXiv: 1901.02486, 2019.
  * [2] C. Alves, R. Ribeiro, and R. Sanchis.  Preferential attachment random graphs with edge-steps functions.  arXiv preprint arXiv: 1704.08276, 2019.
  * [3] M. Amin Abdullah and N. Fountoulakis.  A phase transition in the evolution of bootstrap percolation processes on preferential attachment graphs.  Random Structures & Algorithms, 52(3):379–418, 2018.
  * [4] A-L. Barabási and R. Albert.  Emergence of scaling in random networks.  Science, 1999.
  * [5] N H Bingham, C M Goldie, and J L Teugels.  Regular variation, volume 27.  Cambridge university press, 1989.
  * [6] B. Bollobás, O. Riordan, J. Spencer, and G. Tusnády.  The degree sequence of a scale-free random graph process.  Random Structures and Algorithms, 18:279–290, 2001.
  * [7] Yu V Borovskikh and VS Korolyuk.  Martingale approximation.  Walter de Gruyter GmbH & Co KG, 2019.
  * [8] F. Chung and L. Lu.  Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics).  American Mathematical Society, Boston, MA, USA, 2006.
  * [9] R Durret.  Probability: theory and examples,(2nd edn.), duxburry.  Belmont. Calif.
  * [10] R. Durrett.  Random Graph Dynamics (Cambridge Series in Statistical and Probabilistic Mathematics).  Cambridge University Press, 2006.
  * [11] F Eggenberger and G Polya.  Uber die statistik verketteter vorgange af angewandte math.  U. Mech, 3:279–289, 1923.
  * [12] P. Erdos and A. Renyi.  On random graphs i.  Publ. Math. Debrecen, 6:290, 1959.
  * [13] D. A. Freedman.  On tail probabilities for martingales.  Ann. Probab., 3(1):100–118, 1975.
  * [14] Peter Hall and Christopher C Heyde.  Martingale limit theory and its application.  Academic press, 2014.
  * [15] Y. Malyshkin and E. Paquette.  The power of choice combined with preferential attachment.  Electronic Communications in Probability, 19(44):1–13, 2014.
  * [16] T. Móri.  The maximum degree of the barabasi-albert random tree.  Comb. Probab. Computing, 2005.
  * [17] E. Peköz, A. Röllin, and N. Ross.  Pólya urns with immigration at random times.  Bernoulli, 25(1):189–220, 2019.
  * [18] N. Sidorova.  Time-dependent póya urns.  arXiv preprint arXiv:1807.04844, 2018.
  * [19] S.H Strogatz and D. J. Watts.  Tcollective dynamics of ’small-world’ networks.  Nature, 1998.
  * [20] R. Van Der Hofstad.  Random graphs and complex networks, volume 1.  Cambridge university press, 2016.
  * [21] D. Znamenski, G. Hooghiemstra, and R. van der Hofstad.  A phase transition for the diameter of the configuration model.  Internet Mathematics, 4(1):113–128, 2007.