# Topological properties of P.A. random graphs with edge-step functions

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  Rémy Sanchis3 3Departamento de Matemática,
Universidade Federal de Minas Gerais, Av. Antônio Carlos 6627 C.P. 702 CEP
30123-970 Belo Horizonte-MG, Brazil
e-mail<EMAIL_ADDRESS>
(Date:
1 Institute of Mathematics, University of Leipzig
2 PUC Chile, Pontificia Universidad Católica de Chile.
3 Departamento de Matemática, Universidade Federal de Minas Gerais. )

###### Abstract.

In this work we investigate a preferential attachment model whose parameter is
a function $f:\mathbb{N}\to[0,1]$ that drives the asymptotic proportion
between the numbers of vertices and edges of the graph. We investigate
topological features of the graphs, proving general bounds for the diameter
and the clique number. Our results regarding the diameter are sharp when $f$
is a regularly varying function at infinity with strictly negative index of
regular variation $-\gamma$. For this particular class, we prove a
characterization for the diameter that depends only on $-\gamma$. More
specifically, we prove that the diameter of such graphs is of order $1/\gamma$
with high probability, although its vertex set order goes to infinity
polynomially. Sharp results for the diameter for a wide class of slowly
varying functions are also obtained. The almost sure convergence for the
properly normalized logarithm of the clique number of the graphs generated by
slowly varying functions is also proved.

_Keywords_ : complex networks; cliques; preferential attachment; concentration
bounds; diameter; scale-free; small-world
MSC 2010 subject classifications. Primary 05C82; Secondary 60K40, 68R10

##  1\. Introduction

P. Ërdos and A. Rényi in their seminal paper [17] introduced the random graph
model that now carries their name in order to solve combinatorial problems.
However, the theory of Random Graphs as a whole has proven to be a useful tool
for treating concrete problems as well. Any discrete set of entities whose
elements interact in a pairwise fashion may be seen as a graph: the vertices
represent the entities, and the edges, the possible interactions. This
approach is nowadays intuitive and very fruitful. In the scenario where there
exists some randomness on the interactions among the entities, random graphs
became the natural tool to represent abstract or real phenomena.

From a mathematical/statistical point of view, the Ërdos-Rényi model – and
many others related to it – is homogeneous, in the sense that its vertices are
statistically indistinguishable. However, the empirical findings of the
seminal work of A. Bárabasi and R. Álbert [5] suggested that many real-world
networks are non-homogeneous. They observed that such graphs were scale-free,
i.e., their degree sequence had a power-law distribution. The authors proposed
a mechanism – known as preferential attachment – that could explain the
emergence of such highly skewed distributions. Roughly speaking, the idea is
that some sort of popularity drives the interaction among the entities.

Motivated mainly by these empirical findings, nowadays Preferential Attachment
models (PA-models for short) constitutes a well known class of random graph
models investigated from both theoretical and applied perspectives. Recently,
the preferential attachment mechanism has been generalized in many ways and
combined with other rules of attachment, such as spatial proximity [19] and
fitness of vertices [14]. It also arises naturally even in models where it is
not entirely explicit such as the deletion-duplication models [4, 26], in
which vertices’ degree still evolve according to the PA-rule. Furthermore, the
PA-models provide an interesting and natural environment for other random
processes, such as bootstrap percolation, contact process and random walks,
see [3, 11, 20] for recent examples of random processes whose random media is
sampled from some PA-model.

When dealing with PA-models, there exists a set of natural questions that
arises. They concern the empirical degree distribution, the order of the
diameter and the robustness of the network. Their interest relies on modeling
purposes and on the implications for the graph’s combinatorial structures.

In this paper we address the two latter topics on a PA-model which is a
modification of the BA-model. The kind of result we pursuit is to show that
some graph properties hold asymptotically almost surely (a.a.s). Given a
sequence of random graphs $\\{G_{t}\\}_{t\in\mathbb{N}}$, we say that a graph
property $\mathcal{P}$ holds a.a.s, if

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

i.e., the probability of observing such property increases to $1$ as $t$ goes
to infinity. For instance, $\mathcal{P}$ may be the set of graphs having
diameter less than the logarithm of the total number of vertices.

In order to offer a clearer discussion of our results, we introduce the model
in the next subsection, then we discuss separately the properties which we
want the graph to satisfy a.a.s, as well as the associated motivation.

###  1.1. Preferential attachment model with an edge-step function

The model we investigate here in its generality was proposed in [2] and
combines the traditional preferential attachment rule with a function called
edge-step function that drives the growth rate of the vertex set.

The model has one parameter $f$ which is a real non-negative function with
domain given by $\mathbb{N}$ and bounded by one on the $L_{\infty}$-norm.
Without loss of generality and to simplify the expressions we deal with, we
start the process from an initial graph $G_{1}$ consisting in one vertex and
one loop. The model evolves inductively and at each step the next graph is
obtained by performing one of the two stochastic operations defined below on
the previous one:

  * •

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{\text{degree}(u)}{\sum_{w\in
G}\text{degree}(w)}.$

  * •

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.

The model alternates between the two types of operations according to a
sequence $\\{Z_{t}\\}_{t\geq 1}$ of independent random variables such that
$Z_{t}\stackrel{{\scriptstyle\tiny d}}{{=}}\mathrm{Ber}(f(t))$. We then define
inductively a random graph process $\\{G_{t}(f)\\}_{t\geq 1}$ as follows:
start with $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$.

Given $f$, its partial sum is an important quantity for us and we reserve the
letter $F$ to denote it, i.e., $F$ is a function defined as

(1.1) $F(t):=1+\sum_{s=2}^{t}f(s).$

Observe that the edge-step function $f$ is intimately related to the growth of
the vertex set. If we let $V_{t}$ denote the number of vertices added up to
time $t$, then

(1.2) $V_{t}=1+\sum_{s=2}^{t}Z_{s}\approx F(t),$

since the sequence of random variables $(Z_{s})_{s\geq 1}$ is independent.
Thus, abusing from the notation for a brief moment, we may write

$\frac{\mathrm{d}V_{t}}{\mathrm{d}t}=f(t).$

When the proper machinery has been settled, we will discuss in Section 8 that
some regularity should be imposed on $f$ in order to avoid some pathological
behaviors. For now, we define a list of conditions we may impose on $f$ at
different points of the paper in order to get the proper results. For
instance, we say $f$ satisfies condition $(\mathrm{D})$ if it is non-
increasing. We define the further conditions:

(D0) $f\text{ is non-increasing and }\lim_{t\to\infty}f(t)=0;$ (S)
$\sum_{s=1}^{\infty}\frac{f(s)}{s}<\infty;$ (Lκ)
$\sum_{s=t^{1/13}}^{t}\frac{f(s)}{s}<(\log t)^{\kappa},\text{ for all
}t\in\mathbb{N}\text{ and some }\kappa\in(0,1);$ (RVγ) $\exists\gamma,\text{
such that }\forall
a>0,\;\lim_{t\to\infty}\frac{f(at)}{f(t)}=\frac{1}{a^{\gamma}}.$

We must point out that for modeling purposes, conditions (D) and (D0) may be
desirable. For instance, in the context of social networks, these conditions
assure that the rate at which new individuals join the network is decreasing
as the size of the network increases. Whereas, conditions (S) and (Lκ) are
related to the order of the maximum degree of $G_{t}(f)$. In [2], the authors
point out that the maximum degree at time $t$ should be of order

(1.3) $t\cdot\exp\left\\{-\frac{1}{2}\sum_{s=2}^{t}\frac{f(s)}{s-1}\right\\}.$

A function satisfying condition (RVγ) is called regularly varying at infinity
and the exponent $\gamma$ is called the index of regular variation. Functions
in this class are well-studied in mathematics in many contexts and a variety
of asymptotic results for them and their integrals is known due mainly to the
theory developed by Karamata, see [8] for a complete reference.

In general, we may say that this paper investigates how sensitive some graph
observables are to changes of $f$ and aims at a general characterization of
such observables for a class of functions $f$ that is as wide as possible.

###  1.2. Robustness and large cliques

As said before, one of the main questions concerns the robustness of the
network or how vulnerable the network is to spread of a disease [6] or to
deliberate/random attacks [10]. Regarding the spread of rumors of diseases
some graph substructures play important roles, such as stars, triangles and
cliques (complete subgraphs). The latter is also related to the robustness of
the network, since the existence of a large clique may let the network less
vulnerable to attacks aiming at edge-deletion.

In [7], the authors give lower and upper bounds for the clique number in a
uncorrelated PA-model. Their bounds are polynomial on the number of vertices.
In the same direction, in [21] the authors prove some sort of phase transition
on the clique number of a random graph $G(n,\alpha)$ on $n$ vertices and
degree sequence obeying a power-law with exponent $\alpha$. For their model,
when $\alpha>2$ the clique number is of constant size, whereas for heavy
tails, when $0<\alpha<2$, $\omega(G(n,\alpha))$ is a power of $n$.

In this matter, we prove the existence a.a.s of large cliques whose order
depends essentially on the definite integral of $f$. The result is formally
stated on the theorem below

######  Theorem 1 (Large cliques).

Let $f$ be an edge-step function satisfying condition (D0). Then, for every
$\delta\in(0,1)$, there exist a positive constant $C$ depending on $\delta$
only such that

${\mathbb{P}}\left(\exists K_{n}\subset G_{t}(f),\textit{ such that }n\geq
CF(t^{\frac{1-\delta}{2}})\right)=1-o(1),$

where $K_{n}$ denotes a subgraph isomorphic to the complete graph with $n$
vertices.

For edge-step functions which are also slowly varying varying the above
theorem can provide the right order of largest clique of $G_{t}(f)$, i.e., the
so-called clique number, denoted by $\omega(G_{t}(f))$. In the more general
case of a regularly varying function $f$, a non-sharp result can be obtained.
We summarize this in the Corollary below

######  Corollary 1.4 (Clique number for regular varying functions).

let $f$ be an edge-step function satisfying conditions (D0) and (RVγ), for
$\gamma\in[0,1)$. Then,

  1. (a)

for any $\varepsilon>0$ and $t$ sufficiently large

${\mathbb{P}}\left(t^{(1-\gamma)\frac{1-\varepsilon}{2}}\leq\omega(G_{t}(f))\leq
7t^{\frac{1}{2}}\right)\geq 1-\frac{1}{\log(t)};$

  2. (b)

For $f$ under (RV0), we have

$\lim_{t\to\infty}\frac{\log\omega(G_{t}(f))}{\log
F(t^{\frac{1}{2}})}=1,\;\text{almost surely.}$

###  1.3. Shaping the diameter

Another topological property of graphs which is also related to spread of
rumors and connectivity of networks is the diameter, that is, the maximal
graph distance between two vertices of said graph. Originally, investigating
the diameter of real-world networks, the authors in [25] observed that,
although coming from different contexts, those networks usually have diameter
of order less than the logarithm of the number of verices, the so-called
small-world phenomena.

In this paper we also address the issue of determining the order of the
diameter. Our main goals in this subject are to obtain a characterization for
the diameter imposing conditions on $f$ as weak as possible and also to obtain
regimes for the diameter arbitrarily small but still preserving the
scalefreeness of the graph.

In order to slow the growth of the diameter of PA-models, two observables play
important roles: the maximum degree and the proportion of vertices with low
degree. The former tends to concentrate connections on vertices with very high
degree which acts in the way of shortening the diameter, since they attract
connections to them. Whereas the latter, acts in the opposite way. In [28] and
[18], the authors have shown that in the configuration model with power-law
distribution the diameter order is extremely sensitive to the proportion of
vertices with degree 1 and 2.

One way to reduce the effect of low degree vertices on the diameter is via
affine preferential attachment rules, i.e., introducing a parameter $\delta$
and choosing vertices with probability proportional to their degree plus
$\delta$. In symbols, conditionally on $G_{t}$, we connect a new vertex
$v_{t+1}$ to an existing one $u$ with probability

${\mathbb{P}}\left(v_{t+1}\rightarrow
u\middle|G_{t}\right)=\frac{\text{degree}(u)+\delta}{\sum_{w\in
G_{t}}(\text{degree}(w)+\delta)}.$

By taking a negative $\delta$, the above rule increases the influence of high
degree vertices and indeed decreases drastically the diameter’s order. For
instance, for positive $\delta$ the diameter of $G_{t}$ is at least $\log(t)$,
whereas for $\delta<0$ the diameter of $G_{t}$ is at most $\log\log t$. See
[15] for several results on the diameter of different combinations for the
affine preferential attachment rule.

Diminishing the effect of low degree vertices is not enough to break the
growth of the diameter completely. The reason for that is, despite their low
degree, these vertices exist in large amount. Even the existence of a vertex
with degree close to $t$ at time $t$ may not be enough to freeze the
diameter’s growth. In [23] the authors have proven that the maximum degree of
a modification of the BA-model is of order $t$ at time $t$. However, the
authors believe that this is not enough to obtain a diameter of order
$\log\log t$, the reason being that this large hub still has to compete with a
large number of low degree vertices.

####  1.3.1. General bounds for the diameter

As said before, our goal is to develop bounds for the diameter of $G_{t}(f)$
with $f$ as general as possible. Under the condition of monoticity, we prove
the following lower bound

######  Theorem 2 (Lower bound on the diameter).

Let $f$ be an edge-step function satisfying condition $(\mathrm{D})$. Then

(1.5)
${\mathbb{P}}\left(\mathrm{diam}(G_{t}(f))\geq\frac{1}{3}\left(\frac{\log
t}{\log\log t}\wedge\frac{\log t}{-\log f(t)}\right)\right)=1-o(1).$

For the upper bound, by a coupling argument, we are able to prove that the
diameter of the Barabási-Albert random tree is the ceiling for the diameter
generated by any $f$. Requiring more information on $f$, we prove upper bounds
that, for a broad class of functions, are of the same order of the lower
bounds given by the previous theorem. This is all summarized in the Theorem
below.

######  Theorem 3 (Upper bound on the diameter).

Let $f$ be an edge-step function. Then

  1. (a)

$\mathrm{diam}(G_{t}(f))$ is at most the diameter of the Barabási-Albert
random tree, i.e.,

${\mathbb{P}}\left(\mathrm{diam}(G_{t}(f))\leq\log t\right)=1-o(1).$

  2. (b)

if $f$ also satisfies condition (S) then there exists a positive constant
$C_{1}$ such that

${\mathbb{P}}\left(\mathrm{diam}(G_{t}(f))\leq 2+6\left(\frac{\log
t}{-\log\left(\sum_{s=t^{\frac{1}{13}}}^{t}\frac{f(s)}{s-1}\right)}\wedge\frac{\log
t}{\log\log t}\right)\right)\geq 1-C_{1}t^{-144^{-1}};$

  3. (c)

if $f$ satisfies condition (Lκ) then there exists a positive constant $C_{2}$
such that

${\mathbb{P}}\left(\mathrm{diam}(G_{t}(f))\leq 2+\frac{6}{1-\kappa}\frac{\log
t}{\log\log t}\right)\geq 1-C_{2}t^{-144^{-1}}.$

####  1.3.2. The class regularly varying functions

In [2], the authors prove a characterization of the empirical degree
distribution of graphs generated by $f$ satisfying condition (RVγ), for
$\gamma\in[0,1)$. More specifically, they prove that the degree distribution
of such graphs obeys a power law distribution whose exponent depends only on
the index of regular variation $-\gamma$.

A byproduct of our general bounds is a similar characterization for the
diameter. For edge-step functions satisfying conditions (D0) and (RVγ) for
$\gamma\in(0,\infty)$ the graphs generated by such functions have constant
diameter and its order depends only on the index of regular variation
$-\gamma$. We state this result in the theorem below

######  Theorem 4 (Diameter of regularly varying functions).

Let $f$ be an edge-step function satisfying conditions (D0) and (RVγ), for
$\gamma\in(0,\infty)$. Then,

${\mathbb{P}}\left(\frac{1}{4\gamma}\leq\mathrm{diam}(G_{t}(f))\leq\frac{100}{\gamma}+2\right)=1-o(1).$

####  1.3.3. The class of slowly varying functions

The case when $\gamma=0$ is richer in terms of possible orders of the diameter
and does not admit a nice characterization as the one we obtain for positive
$\gamma$. In this settings, we present another consequence of our bounds for
particular subclasses of the class of slowly varying functions. Let us first
define the subclass of functions and later state how our results fit these
specific classes.

(1.6) $L:=\left\\{f\text{ is an edge-step function such that
}f(t)=\frac{1}{\log^{\alpha}(t)},\text{ for some }\alpha>0\right\\};$ (1.7)
$E:=\left\\{f\text{ is an edge-step function such that
}f(t)=e^{-\log^{\alpha}(t)},\text{ for some }\alpha\in(0,1)\right\\}.$

It is straightforward to verify that functions belonging to the set above
defined are slowly varying. For functions belonging to the two subclasses $L$
and $E$, our results have the following consequences, verifiable through
elementary calculus,

######  Corollary 1.8.

Let $f$ be an edge-step function.

  1. (a)

if $f$ belongs to $L$, with $\alpha\leq 1$, then

${\mathbb{P}}\left(\frac{1}{3}\frac{\log t}{\log\log
t}\leq\mathrm{diam}(G_{t}(f))\leq\frac{8}{\alpha}\frac{\log t}{\log\log
t}\right)=1-o(1);$

  2. (b)

if $f$ belongs to $L$, with $\alpha>1$, then

${\mathbb{P}}\left(\frac{1}{3\alpha}\frac{\log t}{\log\log
t}\leq\mathrm{diam}(G_{t}(f))\leq\frac{7}{\alpha-1}\frac{\log t}{\log\log
t}\right)=1-o(1);$

  3. (c)

if $f$ belongs to $E$, then

${\mathbb{P}}\left(C_{\alpha}^{-1}(\log
t)^{1-\alpha}\leq\mathrm{diam}(G_{t}(f))\leq C_{\alpha}(\log
t)^{1-\alpha}\right)=1-o(1),$

for some $C_{\alpha}\geq 1$.

###  1.4. Comparing $G_{t}(f)$ and $G_{t}(h)$

If two edge-step functions are “close” to each other in some sense, then one
should expect that the random processes they generate should be “close” as
well. We make precise this intuition in the theorem below. In words, if $f$
and $h$ are close in the $L_{1}(\mathbb{N})$-norm (denoted by
$\|\cdot\|_{1}$), then $\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq 1})$ is close to
$\mathrm{Law}(\\{G_{t}(h)\\}_{t\geq 1})$ in the total variation distance,
denoted by $\mathrm{dist}_{TV}(\cdot,\cdot)$.

######  Theorem 5.

Consider $f$ and $h$ two edge-step functions. We have

(1.9) $\mathrm{dist}_{TV}\left(\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq
1}),\mathrm{Law}(\\{G_{t}(h)\\}_{t\geq 1})\right)\leq\|f-h\|_{1}.$

In particular, if $(f_{n})_{n\in\mathbb{N}}$ is a sequence of edge-step
functions, then

(1.10) $f_{n}\stackrel{{\scriptstyle
L_{1}(\mathbb{N})}}{{\longrightarrow}}f\implies\mathcal{L}((G_{t}(f_{n}))_{t\geq
1})\stackrel{{\scriptstyle\mathrm{dist}_{TV}}}{{\longrightarrow}}\mathcal{L}((G_{t}(f))_{t\geq
1}).$

The above theorem may be read as a perturbative statement. It assures that we
may add a small noise $\epsilon=\epsilon(t)$ to an edge-step function $f$ and
still obtain the same process up to an error of at most $\|\epsilon\|_{1}$ in
total variation distance.

###  1.5. Main technical ideas

In order to prove the existence of some given subgraph in the (affine) BA-
random graphs a key ingredient is usually to use the fact that two given
vertices $v_{i}$ and $v_{j}$ may be connected only at one specific time-step,
since (assuming $i<j$) the model’s dynamic only allows $v_{j}$ to connect to
$v_{i}$ at the moment in which $v_{j}$ is created. This property facilitates
the computation of the probability of the occurrence of a given subgraph and
decreases the combinatorial complexity of the arguments. In [9, 16] the
authors estimate the number of triangles and cherries (paths of length $3$) on
the (affine) BA-model and their argument relies heavily on this feature of the
model. In our case, however, the edge-step prevents an application of such
arguments, since a specific subgraph may appear at any time after the vertices
have been added.

Another difficulty in our setup is the degree of generality we work with. Our
case replaces the parameter $p\in(0,1]$ in the models investigated in [1, 12,
13] by any non-negative real function $f$ with $\|f\|_{\infty}\leq 1$. The
introduction of such function naturally increases the complexity of any
analytical argument one may expect to rely on and makes it harder to discover
threshold phenomena. This is the reason why in our work the Karamata’s Theory
of regularly varying functions is crucial in order to prove sharper results.

In order to overcome the issues presented above, more specifically to prove
Theorem 1 and Theorem 5, we construct an auxiliary process that we call the
doubly-labeled random tree process, $\\{\mathcal{T}_{t}\\}_{t\geq 1}$. In
essence, this process is a realization of the traditional BA-model (obtained
in our settings choosing $f\equiv 1$) where each vertex has two labels
attached to it. We then show in Proposition 2.1 how to generate $G_{t}(f)$
from $\mathcal{T}_{t}$ using the information on those labels. This procedure
allows us to generate $G_{t}(f)$ and $G_{t}(h)$, for two distinct functions
$f$ and $h$, from exactly the same source of randomness. The upshot is that an
edge-step function may be seen as a map from the space of doubly-labeled trees
to the space of (multi)graphs – therefore it makes sense to use the notation
$f(\mathcal{T}_{t})$. Furthermore, this map has the crucial property of being
monotonic (in a way we make precise latter). Roughly speaking, if $f\leq h$,
then certain monotonic graph observables respect this order, so if $\zeta$ is
such an observable than
$\zeta(f(\mathcal{T}_{t}))\leq\zeta(h(\mathcal{T}_{t}))$. In Proposition 2.5
we give important examples of suitable monotonic graph observables, the
diameter being one of them. Our machinery then allows us to transpose some
results about graphs generated for functions in a particular regime to another
just by comparing the functions themselves. We use known results about cliques
when $f$ is taken to be a constant less than one to propagate this result down
other regimes of functions.

For the proof of Theorem 2, we apply the second moment method on the number of
isolated paths. This approach demands correlation estimations for the
existence of two such paths in $G_{t}(f)$, which we do only under the
assumption of $f$ being monotonic. For Theorem 3, we apply a lower bound for
the degree of earlier vertices which is obtained by estimation of negative
moments of a given vertex’s degree, and then show that, under conditions (S)
or (Lκ), long paths of younger vertices are unlikely and older vertices are
all very close in graph distance. Finally, using results from the Karamata’s
theory of regularly varying functions, we verify that this broad class of
functions satisfies our assumptions, proving Theorem 4.

###  1.6. Organization

In Section 2 we introduce the doubly-labeled random tree process and prove the
main results about it and as a consequence of this results, we obtain Theorem
5. In Section 3 we explore the theory developed in the previous section to
prove the existence of large cliques, i.e., Theorem 1. Then, in Section 4, we
prove technical estimates for the degree of a given vertex, which is needed
for the upper bound on the diameter. Section 5 is devoted to the general lower
bound for the diameter, i.e., for the proof of Theorem 2. We prove the upper
bound for the diameter, Theorem 3, in Section 6. Finally, in Section 7 we show
how our results fit on the class of the regularly varying functions and
subclasses of slowly varying functions. We end the paper at Section 8 with
some comments on the affine version of our model and a brief discussion on
what may happen to the model if some regularity conditions are dropped.

###  1.7. Notation

We let $V(G_{t}(f))$ and $E(G_{t}(f))$ denote the set of vertices and edges of
$G_{t}(f)$, respectively. Given a vertex $v\in V(G_{t}(f))$, we will denote by
$D_{t}(v)$ its degree in $G_{t}(f)$. We will also denote by $\Delta D_{t}(v)$
the _increment_ of the discrete function $D_{t}(v)$ between times $t$ and
$t+1$, that is,

$\Delta D_{t}(v)=D_{t+1}(v)-D_{t}(v).$

When necessary in the context, we may use $D_{G}(v)$ to denote the degree of
$v$ in the graph $G$.

Given two sets $A,B\subseteq V(G_{t}(f))$, we let $\\{A\leftrightarrow B\\}$
denote the event where there exists an edge connecting a vertex from $A$ to a
vertex from $B$. We denote the complement of this event by
$\\{A\nleftrightarrow B\\}$. We let $\mathrm{dist}(A,B)$ denote the graph
distance between $A$ and $B$, i.e. the minimum number of edges that a path
that connects $A$ to $B$ must have. When one of these subsets consists of a
single vertex, i.e. $A=\\{v\\}$, we drop the brackets from the definition and
use $\\{v\leftrightarrow B\\}$ and $\mathrm{dist}(v,B)$, respectively.

For $t\in\mathbb{N}$, we let $[t]$ denote the set $\\{1,\dots,t\\}$.

Regarding constants, we let $C_{1},C_{2},\dots$ and $c,c_{1},c_{2},\dots$ be
positive real numbers that do not depend on $t$ whose values may vary in
different parts of the paper. The dependence on other parameters will be
highlighted throughout the text.

Since our model is inductive, we use the notation $\mathcal{F}_{t}$ to denote
the $\sigma$-algebra generated by all the random choices made up to time $t$.
In this way we obtain the natural filtration
$\mathcal{F}_{0}\subset\mathcal{F}_{1}\subset\dots$ associated to the process.

##  2\. The doubly-labeled random tree process

In this section we introduce a stochastic process
$\\{\mathcal{T}_{t}\\}_{t\geq 1}$ that provides a grand coupling between the
random graphs $\\{G_{t}(f)\\}_{t\geq 1}$ for every edge-step function $f$.

The process $\\{\mathcal{T}_{t}\\}_{t\geq 1}$ is essentially a realization of
the Barabási-Albert random tree where each vertex has two labels: an earlier
vertex chosen according to the preferential attachment rule and an independent
uniform random variable. The label consisting in the earlier vertex can be
seen as a “ghost directed edge”, we later use these random labels to collapse
subsets of vertices into a single vertex in order to obtain a graph with the
same distribution as $G_{t}(f)$ for any prescribed function
$f:\mathbb{N}\to[0,1]$.

We begin our process with a graph $\mathcal{T}_{1}$ consisting as usual in a
single vertex and a single loop connecting said vertex to itself. We then
inductively construct the labeled graph $\mathcal{T}_{t+1}$ from
$\mathcal{T}_{t}$ in the following way:

Figure 1. A sample of the process $\\{\mathcal{T}_{t}\\}_{t\geq 1}$ up to time
$6$ without the uniform labels. The dashed lines indicate the label
$\ell(v_{j})$ taken by each vertex $v_{j}$.

  * (i)

We add to $\mathcal{T}_{t}$ a vertex $v_{t+1}$;

  * (ii)

We tag $v_{t+1}$ with a random label $\ell(v_{t+1})$ chosen from the set
$V(\mathcal{T}_{t})$ with the preferential attachment rule, that is, with
probability of choosing $u\in V(\mathcal{T}_{t})$ proportional to the degree
of $u$ in $\mathcal{T}_{t}$;

  * (iii)

Independently from the step above, we add an edge $\\{w,v_{t+1}\\}$ to
$E(\mathcal{T}_{t})$ where $w\in V(\mathcal{T}_{t})$ is also randomly chosen
according to the preferential attachment rule, see Figure 1.

We then finish the construction by tagging each vertex $v_{j}\in
V(\mathcal{T}_{t})$ with a second label consisting in an independent random
variable $U_{j}$ with uniform distribution on the interval $[0,1]$, as shown
in Figure 2. We note that only the actual edges contribute to the degree taken
in consideration in the preferential attachment rule, the tags are not
considered.

Figure 2. The graph $\mathcal{T}_{6}$, now each vertex receives an independent
uniform random variable.

We now make precise the notation $f(\mathcal{T}_{t})$ which indicates that an
edge-step function $f$ may also be seen as a function that maps a doubly-
labeled tree to a (multi)graph. Our goal is to define this map in such way
that $f(\mathcal{T}_{t})\stackrel{{\scriptstyle d}}{{=}}G_{t}(f)$.

In order to do so, let us fix such a function $f$. Given $v_{j}\in
V(\mathcal{T}_{t})$, we compare $U_{j}$ to $f(j)$. If $U_{j}\leq f(j)$, we do
nothing. Otherwise, we collapse $v_{j}$ onto its label $\ell(v_{j})$, that is,
we consider the set $\\{v_{j},\ell(v_{j})\\}$ to be a single vertex with the
same labels as $\ell(v_{j})$. We then update the label of all vertices $v$
such that $\ell(v)=v_{j}$ to $\\{v_{j},\ell(v_{j})\\}$. This procedure is
associative in the sense that the order of the vertices on which we perform
this operation does not affect the final resulting graph, as long as we
perform it for all the vertices of $\mathcal{T}_{t}$. We let then
$f(\mathcal{T}_{t})$ be the (multi)graph obtained when this procedure has run
over all the $t$ vertices of $\mathcal{T}_{t}$. We refer to Figure 3 as an
illustration of the final outcome.

In the next proposition we prove that $f(\mathcal{T}_{t})$ is indeed
distributed as $G_{t}(f)$.

Figure 3. The figure shows how one can sample the distribution of $G_{6}(f)$
using the labeled graph $\mathcal{T}_{6}$.

######  Proposition 2.1.

Let $\mathcal{T}_{t}$ be the doubly-labeled tree above defined and $f$ an
edge-step function. Then,

$f(\mathcal{T}_{t})\stackrel{{\scriptstyle d}}{{=}}G_{t}(f).$

###### Proof.

We first observe that the associativity of the collapsing operation and the
independence of the sequence $(U_{j})_{j\geq 1}$ from the previous operations
imply that we can glue together the vertex $v_{t+1}$ to $\ell(v_{t+1})$
whenever $U_{t+1}>f(t+1)$ right after we complete step (iii) of the above
construction by induction. The resulting graph has either a new vertex
$v_{t+1}$ with an edge $\\{w(v_{t+1}),v_{t+1}\\}$ or an edge
$\\{w(v_{t+1}),\ell(v_{t+1})\\}$ with the exact same probability distribution
as the $(t+1)$-th step in the construction of the graph $(G_{t}(f))_{t\geq
1}$. By induction, both random graphs have the same distribution.

In the light of the above discussion and Proposition 2.1, from now on, we will
tacitly assume that all process $\\{G_{t}(f)\\}_{t\geq 1}$ for all edge-step
functions are on the same probability space provided by our previous results.

A straightforward consequence of Proposition 2.1 is Theorem 5 which roughly
speaking states that edge-step functions close to each other in the
$L_{1}(\mathbb{N})$-norm generates essentially the same processes. Once we
have the machinery provided by Proposition 2.1, the proof of this fact becomes
a simple application of the union bound.

###### Proof of Theorem 5.

Fixed two edge-step functions $f$ and $h$, by Proposition 2.1 we have that

(2.2) $\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq
1})=\mathrm{Law}(\\{f(\mathcal{T}_{t})\\}_{t\geq 1}).$

Thus

(2.3) $\begin{split}\mathrm{dist}_{TV}\left(\mathrm{Law}(\\{G_{t}(f)\\}_{t\geq
1}),\mathrm{Law}(\\{G_{t}(h)\\}_{t\geq
1})\right)&\leq{\mathbb{P}}\left(\\{f(\mathcal{T}_{t})\\}_{t\geq
1}\neq\\{h(\mathcal{T}_{t})\\}_{t\geq 1}\right)\\\
&\leq\sum_{i=1}^{\infty}{\mathbb{P}}\left(U_{i}\in(f(i)\wedge h(i),f(i)\vee
h(i))\right)\\\ &=\sum_{i=1}^{\infty}|f(i)-g(i)|\\\ &=\|f-g\|_{1},\end{split}$

and the above equation immediately implies (1.10).

The next step is to use the coupling provided by the auxiliary process
$\\{\mathcal{T}_{t}\\}_{t\geq 1}$ to compare graph observable of graphs
generated by different edge-step functions. This method will allow us to
transport results we have obtained for a fixed $f$ to other edge-step
functions by comparing them with $f$. To do this we introduce the notion of
increasing (decreasing) graph observable.

######  Definition 1 (Monotone graph observable).

We say that a (multi)graph observable $\zeta$ is increasing if, given two
edge-step functions $f$ and $h$, we have that

(2.4) $f(s)\leq h(s),\forall s\leq
t\implies\zeta(f(\mathcal{T}_{t}))\leq\zeta(h(\mathcal{T}_{t}))\;\textit{a.s.}$

When the second inequality in (2.4) holds with “$\geq$”, we say $\zeta$ is
decreasing.

A first example of an increasing observable is the total number of vertices.
Indeed, since every vertex $v_{j}$ of $\mathcal{T}_{t}$ remain preserved under
$f$ whenever its $U_{j}$ label is less than $f(j)$, it follows that every
$f$-preserved $v_{j}$ is $h$-preserved as well.

The next proposition states that the maximum degree is a decreasing observable
whereas the diameter, in which we are interested in, is an increasing one.

######  Proposition 2.5.

Let $f$ and $h$ be two edge-step functions satisfying the relation $f(s)\leq
h(s)$ for all $s\in(1,\infty)$. Then,

  1. (a)

the maximum degree is a _decreasing_ graph observable. More precisely, if we
let $D_{\textit{max}}(G)$ denote the maximum degree of a (multi)graph $G$,
then

${\mathbb{P}}\left(\forall t\in\mathbb{N},\;D_{\textit{max}}(G_{t}(f))\geq
D_{\textit{max}}(G_{t}(h))\right)=1;$

  2. (b)

the diameter is an _increasing_ graph observable. More precisely,

${\mathbb{P}}\left(\forall
t\in\mathbb{N},\;\mathrm{diam}(G_{t}(f))\leq\mathrm{diam}(G_{t}(h))\right)=1$

###### Proof.

The proofs follow from an analysis of the action of $f$ over
$\mathcal{T}_{t}$.

Proof of part (a): We first point out that if $v_{s}$ is a vertex of
$\mathcal{T}_{t}$ whose $U_{s}$-label is less than $f(s)$, then

(2.6) $D_{G_{t}(f)}(v_{s})\geq D_{G_{t}(h)}(v_{s}).$

To see why the above inequality is true, notice that the degree of $v_{s}$ in
$G_{t}(f)$ is the total number of solid edges (see Figure 2) incident on
$v_{s}$ in $\mathcal{T}_{t}$ plus the total number of vertices whose
$\ell$-label points to $v_{s}$ and whose $U$-label is greater than $f$.
Formally,

(2.7) $D_{G_{t}(f)}(v_{s})=\sum_{r=1}^{t}\mathbb{1}\left\\{v_{r}\to
v_{s}\text{ in
}\mathcal{T}_{t}\right\\}+\mathbb{1}\left\\{\ell(v_{r})=v_{s},U_{r}\geq
f(r)\right\\}.$

The contribution of the first term in the RHS of the above identity remains
stable under $f$ and $h$, however, being $f(r)\leq h(r)$ for all $r\leq t$, we
automatically have

$\mathbb{1}\left\\{\ell(v_{r})=v_{s},U_{r}\geq
f(r)\right\\}\geq\mathbb{1}\left\\{\ell(v_{r})=v_{s},U_{r}\geq h(r)\right\\},$

which implies that $D_{G_{t}(f)}(v_{s})\geq D_{G_{t}(h)}(v_{s})$.

To finish the proof of this part, notice that, if $v_{s}$ is truly a vertex in
$G_{t}(h)$ but is glued to its $\ell$-label under $f$, this operation just
increases the maximum degree in the sense that the degree of $\ell(v_{s})$
inherits all the contributions of $v_{s}$. Thus, if $v_{\textit{max}}$ is a
vertex that achieves $D_{\textit{max}}(G_{t}(h))$, then if $v_{\textit{max}}$
is also a vertex of $G_{t}(f)$ by the above discussion, its degree is at least
$D_{\textit{max}}(G_{t}(h))$. On the other hand, if it is identified to
$\ell(v_{\textit{max}})$, then the degree of $\ell(v_{\textit{max}})$ is also
at least the maximum degree of $G_{t}(h)$.

Proof of part (b): Observe that if $u$ and $w$ are vertices whose $U$-label is
less than $f$ and such that $u\leftrightarrow w$ in $G_{t}(f)$, then $u$ and
$w$ are possibly not connected by a single edge in $G_{t}(h)$, in other words,
if $\mathrm{dist}_{G_{t}(f)}(u,w)=1$ then $\mathrm{dist}_{G_{t}(h)}(u,w)\geq
1$. Therefore, if $v_{0}=u,v_{1},\cdots,v_{k}=w$ is a minimal path in
$G_{t}(f)$, by the previous observation, this path induces a path in
$G_{t}(h)$ whose length is equal to or greater than $k$.

On the other hand, if $u=v_{0},v_{1},\cdots,v_{k}=w$ is a path realizing the
minimal distance between $u$ and $w$, in $G_{t}(h)$ we have that this path
induces another path in $G_{t}(f)$ of same length or less. To see this, just
notice that, if $U_{j}>f(j)$ and $\ell(v_{j})$ points to a vertex outside the
path for some $j\in\\{2,3,\cdots,k-1\\}$, then, after identifying $v_{j}$ to
its $\ell$-label, this operation does not increase the path length. This is
enough to conclude the proof.

##  3\. Large Cliques: proof of Theorem 1

In this section we keep exploring the machinery developed in previous
sections. Here, we transpose the existence of large cliques using the edge-
step function, i.e., if $h$ is such that $G_{t}(h)$ has a clique of order $K$
and $f$ another function satisfying $f(s)\leq h(s)$ for all $s\in(1,\infty)$,
then the clique existence propagates to $G_{t}(f)$ too but with a possibly
$f$-dependent order.

Our strategy to prove Theorem 1 will be to apply the results obtained for the
function identically equal to $p$, with $p\in(0,1)$ (which we denote by
$\mathrm{cons}_{p}$) in [1] and propagate them to smaller functions. For the
sake of the reader’s convenience, we state and comment the aforementioned
results here. Given $m\in\mathbb{Z}_{+}$, we order the vertices of
$G_{t}(\mathrm{cons}_{p})$ from oldest to earliest and then divide them into
blocks of size $m$. We then denote by $d_{t,m}(j)$ the sum of all degrees of
the vertices from the $j$-th block. The following theorem has a very involved
notation, but in essence it provides with high probability an explicit
polynomial lower bound for $d_{t,m}(j)$.

######  Theorem (Theorem 2 from [1] ).

Given $p\in(0,1]$, let $\xi\in(0,2(2-p)^{-1}-1)$ and fix $m\in\mathbb{Z}_{+}$
sufficiently large. Define

$\zeta_{m}:=\frac{(1-p)}{2(2-p)m^{\xi}}.$

and let

$1<R<m(1-p/2)(1-\zeta_{m}).$

There exists a positive constant $c=c(m,R,p)$ such that, for

$\beta\in(0,(1-p/2)(1-\zeta_{m}))\textit{ and }j\geq m^{\frac{2}{1-p}}+1,$

we have

(3.1) $\mathbb{P}\left(d_{t,m}(j)<t^{\beta}\right)\leq
c\frac{j^{R}}{t^{R-\beta
R(1-p/2)^{-1}(1-\zeta_{m})^{-1}}}+\frac{m}{[(j-1)m]^{99}}.$

Using the above bound one can then prove

######  Theorem (Theorem $1$ from [1]).

For any $\varepsilon>0$ and every $p\in(0,1)$, it follows that

(3.2) ${\mathbb{P}}\left(\exists K_{n}\subset
G_{t}(\mathrm{cons}_{p}),\textit{ such that
}n=t^{(1-\varepsilon)\frac{(1-p)}{2-p}}\right)=1-o(1).$

We can now use the doubly-labeled tree together with the above results in
order to prove Theorem 1. It will be useful to recall our special notation to
the expected number of vertices,

(3.3) $F(t):={\mathbb{E}}V(G_{t}(f))=1+\sum_{s=2}^{t}f(s).$

###### Proof of Theorem 1.

Given $\delta>0$ sufficiently small, let $\varepsilon,p=\delta/6$ so that

$\alpha=\alpha(p,\varepsilon):=\frac{1-p}{2-p}(1-\varepsilon)>\frac{1}{2}\left(1-\frac{\delta}{2}\right).$

In the proof of Theorem $1$ of [1] one uses Theorem $2$ of [1] to show that
there exist a fixed integer $m=m(\varepsilon,p)>0$ and a small number
$\varepsilon^{\prime}\in(0,\alpha)$ with the following property: if one
divides the set of vertices born between times $t^{\varepsilon^{\prime}}$ and
$t^{\alpha}$ into disjoint subsets of $m$ vertices born _consecutively_ , then
with high probability (at least $1$ minus a polynomial function of $t$) one
can choose a vertex from each of these subsets in such a way that the subgraph
induced by the set of chosen vertices is a complete subgraph of
$G_{t}(\mathrm{cons}_{p})$.

Having the above in mind and letting $m$ be the auxiliary $m$ that appears in
proof of Theorem 1 of [1], define the following event

(3.4)
$A_{p,\varepsilon^{\prime},m,k}:=\left\\{\begin{array}[]{c}\exists\\{t_{1},\cdots,t_{k}\\}\subset[t]\text{
such that
}t_{j}\in(t^{\varepsilon^{\prime}}+(j-1)m,t^{\varepsilon^{\prime}}+jm]\\\
\text{and }v_{t_{j}}\leftrightarrow v_{t_{i}}\textit{ in
}G_{t}(\mathrm{cons}_{p})\text{ for all }i,j\in[k]\end{array}\right\\}.$

In the context of the doubly labeled tree process, the event
$A_{p,\varepsilon^{\prime},m,k}$ says that we may find $k$ vertices of
$\mathcal{T}_{t}$ with the property that the $j$-th vertex $v_{t_{j}}$ was
added by the doubly-labeled tree process sometime in the interval
$(t^{\varepsilon^{\prime}}+(j-1)m,t^{\varepsilon^{\prime}}+jm]$ and its
$U_{t_{j}}$-label is less than $p$. Moreover, when we apply
$\mathrm{cons}_{p}$ on $\mathcal{T}_{t}$ in the event
$A_{p,\varepsilon^{\prime},m,k}$, all these $k$ vertices form a complete graph
in the resulting graph $G_{t}(\mathrm{cons}_{p})$. Theorem $1$ of [1] states
that setting $k=t^{\alpha}-t^{\varepsilon^{\prime}}$, the event
$A_{p,\varepsilon^{\prime},m,k}$ occurs with probability at least
$1-t^{-\eta}$, for some positive small $\eta$ depending on $p$, which, in our
case, is a function of $\delta$. Thus, for $t$ large enough, we may simply use
that

(3.5) ${\mathbb{P}}\left(A_{p,\varepsilon^{\prime},m,t^{\alpha}}\right)\geq
1-\frac{1}{\log t},$

this bound will be useful for the proof of Corollary 1.4. This is why we are
exchanging a polynomial decay by a $\log$ one, to get rid off the dependency
on $\delta$ and consequently simplify latter arguments.

Now, let $t$ be large enough so that $f(t^{\varepsilon^{\prime}})<p$. This is
possible since $f$ decreases to zero. Also notice that if $u$ and $v$ are
vertices of $G_{t}(f)$ added after time $t^{\varepsilon^{\prime}}$ and are
connected in $G_{t}(\mathrm{cons}_{p})$, then they are connected in $G_{t}(f)$
as well. Moreover, since $f$ is non-increasing and the $U$-labels are assigned
independently and according to a uniform distribution on $[0,1]$, we have for
all $j\leq k$

(3.6) ${\mathbb{P}}\left(U_{t_{j}}\leq
f(t_{j})\;\middle|\;A_{p,\varepsilon^{\prime},m,k}\right)\geq
p^{-1}f(t^{\varepsilon^{\prime}}+jm).$

Setting $k=(t^{\alpha}-t^{\varepsilon^{\prime}})/m$ and using that $f$ is non-
increasing, we have that

(3.7) $m\sum_{j=0}^{k}f(t^{\varepsilon^{\prime}}+jm)\geq
F(t^{\alpha})-F(t^{\varepsilon^{\prime}}+m)\geq F(t^{\alpha})/2$

for large enough $t$.

By the independence of the $U$-labels, it follows that conditioned on
$A_{p,\varepsilon^{\prime},m,k}$, the random variable that counts how many
vertices of the clique in $G_{t}(\mathrm{cons}_{p})$ remain vertices of
$G_{t}(f)$ as well is a sum of $k$ independent random variables taking values
on $\\{0,1\\}$ and whose expected value is greater than $F(t^{\alpha})/2mp$.
Finally, by Chernoff bounds, this random variable is at least half its
expected value with probability at least $1-\exp\\{-F(t^{\alpha})/16mp\\}$.
This and (3.5) gives us that there exists a constant $C_{\delta}$ such that

(3.8) ${\mathbb{P}}\left(\nexists K_{n}\subset G_{t}(f),\textit{ such that
}n\geq C_{\delta}F(t^{\frac{1-\delta}{2}})\right)\leq\frac{1}{\log
t}+e^{-F(t^{\alpha})/16mp},$

which proves the Theorem.

##  4\. Technical estimates for the degree

In this section we develop technical estimates related to the degree of a
given vertex. We begin by stating one of the most fundamental identities in
the study of preferential attachment models: the conditional distribution of
the increment of the degree of a given vertex. Given $v\in V(G_{t}(f))$, we
have

(4.1) $\begin{split}\mathbb{P}\left(\Delta
D_{t}(v)=0\middle|\mathcal{F}_{t}\right)&=f(t+1)\left(1-\frac{D_{t}(v)}{2t}\right)+(1-f(t+1))\left(1-\frac{D_{t}(v)}{2t}\right)^{2}\\\
\mathbb{P}\left(\Delta
D_{t}(v)=1\middle|\mathcal{F}_{t}\right)&=f(t+1)\frac{D_{t}(v)}{2t}+2(1-f(t+1))\frac{D_{t}(v)}{2t}\left(1-\frac{D_{t}(v)}{2t}\right),\\\
\mathbb{P}\left(\Delta
D_{t}(v)=2\middle|\mathcal{F}_{t}\right)&=(1-f(t+1))\frac{D_{t}(v)^{2}}{4t^{2}}.\end{split}$

To see why the above identities hold true, observe for example that in order
for $\Delta D_{t}(v)=0$, either a vertex step was taken, and the vertex did
not connect to $v$, or an edge step was taken and neither of the endpoints of
the new edge connected to $v$. The other equations follow from analogous
reasonings. As a direct consequence, we obtain

(4.2) $\begin{split}{\mathbb{E}}\left[\Delta
D_{t}(v)\middle|\mathcal{F}_{t}\right]&=1\cdot
f(t+1)\cdot\frac{D_{t}(v)}{2t}+1\cdot
2(1-f(t+1))\frac{D_{t}(v)}{2t}\left(1-\frac{D_{t}(v)}{2t}\right)\\\
&\quad+2\cdot(1-f(t+1))\frac{D^{2}_{t}(v)}{4t^{2}}\\\
&=\left(1-\frac{f(t+1)}{2}\right)\frac{D_{t}(v)}{t}.\end{split}$

Using the above equation repeatedly one obtains, conditioned on the event
where the vertex $v$ is born at time $t_{0}$,

(4.3)
$\begin{split}{\mathbb{E}}\left[D_{t}(v)\right]&={\mathbb{E}}\left[{\mathbb{E}}\left[D_{t}(v)\middle|\mathcal{F}_{t-1}\right]\right]\\\
&=\left(1+\frac{1}{t-1}-\frac{f(t)}{2(t-1)}\right){\mathbb{E}}\left[D_{t-1}(v)\right]\\\
&=\prod_{s=t_{0}}^{t-1}\left(1+\frac{1}{s}-\frac{f(s+1)}{2s}\right).\end{split}$

We state a lower bound for the degree, whose proof comes from a direct
application of Theorem $2$ of [1] and Proposition 2.5, which assures that the
maximum degree is a decreasing graph observable.

######  Lemma 1.

Let $f$ be an edge-step function such that $f(t)\rightarrow 0$ as $t$ goes to
infinity. Then, for any fixed $\varepsilon>0$ we have

${\mathbb{P}}\left(D_{\textit{max}}\left(G_{t}(f)\right)<t^{1-\varepsilon}\right)\leq
t^{-2}.$

###### Proof.

By Theorem $2$ of [1], w.h.p, $D_{\text{max}}(G_{t}(p))$ is at least
$t^{(1-\varepsilon)(1-p/2)}$, for fixed $\varepsilon>0$ and $p\in(0,1)$. Thus,
taking $p_{0}$ small enough, we have that $D_{\text{max}}(G_{t}(p_{0}))$ is at
least $t^{1-\varepsilon}$, w.h.p.

Then, using Proposition 2.5, we have that for large enough $t$,
$D_{\text{max}}(G_{t}(f))\geq D_{\text{max}}(G_{t}(p_{0}))$ which proves the
Lemma.

Our objective now is to obtain a polynomial lower bound for the degree of
older vertices, which will be important in the proof of the upper bound for
the diameter in Theorem 3. We begin with an upper bound for the expectation of
the multiplicative inverse of the degree. Recall the definition of the process
$(Z_{t})_{t\geq 1}$, consisting of independent Bernoulli variables that
dictate whether a vertex-step or an edge-step is performed at time $t$.

######  Lemma 2.

Given any edge-step function $f$, consider the process $\\{G_{t}(f)\\}_{t\geq
1}$. Denote by $v_{i}$ the vertex born at time $i\in\mathbb{N}$. We have

(4.4) ${\mathbb{E}}\left[(D_{t}(v_{i}))^{-1}Z_{i}\right]\leq
f(i)\left(\frac{t-1}{i}\right)^{-\frac{1}{6}}.$

And consequently

(4.5)
${\mathbb{P}}\left(D_{t}(v_{i})\leq\left(\frac{t-1}{i}\right)^{\frac{1}{12}}\middle|Z_{i}=1\right)\leq\left(\frac{t-1}{i}\right)^{-\frac{1}{12}}.$

###### Proof.

If $Z_{i}=1$, then for every $s\geq 1$ we have that $\Delta D_{s}(v_{i})\geq
0$, that $D_{s+1}(v_{i})\leq D_{s}(v_{i})+2\leq 3D_{s}(v_{i})$, and that
$D_{s}(v_{i})$ is $\mathcal{F}_{s}$ measurable. Together with (4.2), these
facts imply. on the event $\\{Z_{i}=1\\}$,

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

since $f(k)\leq 1$ for very $k\in\mathbb{N}$. Therefore,

(4.7)
${\mathbb{E}}\left[Z_{i}\cdot(D_{s+1}(v_{i}))^{-1}\middle|\mathcal{F}_{s}\right]\leq
Z_{i}(1-(6s)^{-1})(D_{s}(v_{i}))^{-1}.$

Iterating the above argument from $i$ until $t$, we obtain

(4.8) ${\mathbb{E}}\left[Z_{i}\cdot(D_{t}(v_{i}))^{-1}\right]\leq
f(i)\prod_{s=i}^{t-1}\left(1-\frac{1}{6s}\right)\leq
f(i)\exp\left\\{-\frac{1}{6}\sum_{s=i}^{t-1}\frac{1}{s}\right\\}\leq
f(i)\left(\frac{t-1}{i}\right)^{-\frac{1}{6}},$

proving (4.4). Equation (4.5) is then obtained by an elementary application of
the Markov inequality:

(4.9)
$\begin{split}{\mathbb{P}}\left(D_{t}(v_{i})\leq\left(\frac{t-1}{i}\right)^{\frac{1}{12}}\middle|Z_{i}=1\right)&={\mathbb{P}}\left((D_{t}(v_{i}))^{-1}\geq\left(\frac{t-1}{i}\right)^{-\frac{1}{12}}\middle|Z_{i}=1\right)\\\
&\leq\left(\frac{t-1}{i}\right)^{\frac{1}{12}}{\mathbb{E}}\left[(D_{t}(v_{i}))^{-1}\middle|Z_{i}=1\right]\\\
&\leq\left(\frac{t-1}{i}\right)^{-\frac{1}{12}}.\end{split}$

We now provide an elementary consequence of the above result, which uses the
union bound in order to show that, with high probability, every vertex born
before time $t^{\frac{1}{12}}$ has degree at least $t^{\frac{1}{15}}$ by time
$t$.

######  Lemma 3.

Using the same notation as in Lemma 2 we have, for every edge-step function
$f$ and for sufficiently large $t\in\mathbb{N}$,

(4.10) ${\mathbb{P}}\left(\exists i\in\mathbb{N},1\leq i\leq
t^{\frac{1}{12}},\text{ such that }Z_{i}=1\text{ and }D_{t}(v_{i})\leq
t^{\frac{1}{15}}\right)\leq Ct^{-\frac{1}{144}}.$

###### Proof.

By the union bound and equation (4.5), we have that the probability in the
left hand side of (4.10) is smaller than or equal to

(4.11)
$\begin{split}\sum_{i=1}^{t^{\frac{1}{12}}}{\mathbb{P}}\left(Z_{i}=1,D_{t}(v_{i})\leq
t^{\frac{1}{15}}\right)&\leq\sum_{i=1}^{t^{\frac{1}{12}}}f(i){\mathbb{P}}\left(D_{t}(v_{i})\leq\left(\frac{t-1}{i}\right)^{\frac{1}{12}}\middle|Z_{i}=1\right)\\\
&\leq\sum_{i=1}^{t^{\frac{1}{12}}}\left(\frac{t-1}{i}\right)^{-\frac{1}{12}}\\\
&\leq Ct^{-\frac{1}{12}+\frac{1}{12}\left(1-\frac{1}{12}\right)}\\\ &\leq
Ct^{-\frac{1}{144}},\end{split}$

finishing the proof of the Lemma.

##  5\. General lower bound for the diameter: proof of Theorem 2

The proof of Theorem 2 follows a second moment argument. The idea is to count
the number of “long” (the specific size depending on $f$ and $t$) _isolated
paths_ in $G_{t}(f)$. We begin by showing that the expected number of isolated
paths goes to infinity with $t$ in Lemma 4. We then show in Lemma 5 that the
presence of a specific isolated path is almost independent from the presence
of some other given isolated path whenever said paths are disjoint. This
“almost independence” makes the second moment of the number of such paths very
close to the first moment squared. The proof is then completed via the Payley-
Zygmund inequality.

We start by defining precisely what we mean by an isolated path.

######  Definition 2 (Isolated path).

Let $l$ be a positive integer. Let $\vec{t}=(t_{1},..,t_{l})$ be a vector of
distinct positive integers. We say that this vector corresponds to an isolated
path $\\{v_{t_{1}},\dots,v_{t_{l}}\\}$ in $G_{t}(f)$ if and only if:

  * •

$t_{l}\leq t$;

  * •

$t_{i}<t_{j}$ whenever $1\leq i<j\leq l$;

  * •

during each time $t_{i}$, $i=1,\dots,l$, a vertex-step is performed;

  * •

for every integer $k\leq l$, the subgraph induced by the vertices
$\\{v_{t_{i}}\\}_{1\leq i\leq k}$ is connected in $G_{t_{k}}(f)$;

  * •

for $i=1,\dots,l-1$, the degree of $v_{t_{i}}$ in $G_{t}(f)$ is $2$. The
degree of $v_{t_{l}}$ in $G_{t}(f)$ is $1$.

In other words, an isolated path $\\{v_{t_{i}}\\}_{1\leq i\leq l}$ is a path
where each vertex $v_{t_{i}}$, for $i=2,\dots,l$, is born at time $t_{i}$ and
makes its first connection to its predecessor $v_{t_{i-1}}$. Other than that,
no other vertex or edge gets attached to $\\{v_{t_{i}}\\}_{1\leq i\leq l}$. We
will denote $\\{v_{t_{i}}\\}_{1\leq i\leq l}$ by $v_{\vec{t}}$.

Given $\xi\in(0,1)$, denote by $\mathcal{S}_{l,\xi}(t)$ the set of all
isolated paths in $G_{t}(f)$ of size $l$ whose vertices were created between
times $\xi t$ and $t$. Our first goal is to obtain lower bounds for
${\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]$:

######  Lemma 4.

Let $f$ be a non-increasing edge-step function, then, for any $0<\xi<1$ and
any integer $l$, the following lower bound holds:

(5.1)
${\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\geq\binom{(1-\xi)t}{l}\frac{f(t)^{l}}{(2t)^{l-1}}\left(1-\frac{2l}{\xi
t}\right)^{t}.$

Furthermore, for

(5.2) $l\leq\frac{1}{3}\left(\frac{\log t}{\log\log t}\wedge\frac{\log
t}{-\log f(t)}\right),$

we have that, for sufficiently large $t$,

(5.3) ${\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\geq t^{\frac{1}{4}}.$

###### Proof.

The random variable $|\mathcal{S}_{l,\xi}(t)|$ can be written as

(5.4)
$|\mathcal{S}_{l,\xi}(t)|=\sum_{t_{1}<t_{2}<\dots<t_{l}}\mathbb{1}\left\\{v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right\\}\quad\implies\quad{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]=\sum_{t_{1}<t_{2}<\dots<t_{l}}\mathbb{P}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right).$

So it will be important to obtain a proper lower bound for
$\mathbb{P}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right)$. Given a time
vector of an isolated path $\vec{t}=(t_{1},\dots,t_{l})$ such that $\xi t\leq
t_{1}<t_{2}<\dots<t_{l}\leq t$, it follows that

(5.5)
$\mathbb{P}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right)\geq\frac{f(t)^{l}}{(2t)^{l-1}}\left(1-\frac{2l}{\xi
t}\right)^{t},$

since in order for $v_{\vec{t}}$ to be in $\mathcal{S}_{l,\xi}(t)$, we need to
assure that $l$ vertices are born exactly at times $t_{1},\dots,t_{l}$ (which
happens with probability greater than $f(t)^{l}$, by the monotonicity of $f$),
that $v_{t_{i}}$ connects to $v_{t_{i-1}}$ for every $i=2,\dots,l$ (which
happens with probability greater than $(2t)^{-(l-1)}$), and that no other
vertex or edge connects to $v_{\vec{t}}$ until time $t$ (which happens with
probability greater than $\left(1-\frac{2l}{\xi t}\right)^{t}$).

Finally, by counting the number of possible ways to choose
$t_{1}<t_{2}<\dots<t_{l}$ so that $t_{i}\in[\xi t,t]$ for $1\leq i\leq l$, we
obtain 5.1.

We now assume $l$ to be such that 5.2 holds. Stirling’s formula gives us

$\begin{split}\log\left(\binom{(1-\xi)t}{l}\right)&\geq
c+(1-\xi)t\log((1-\xi)t)-(1-\xi)t+\frac{\log((1-\xi)t)}{2}\\\ &\quad-l\log
l+l-\frac{\log l}{2}\\\
&\quad-((1-\xi)t-l)\log((1-\xi)t-l)+(1-\xi)t-l-\frac{\log((1-\xi)t-l)}{2},\end{split}$

Since $l\ll t$, we obtain

(5.6) $\log\left(\binom{(1-\xi)t}{l}\right)\geq l\log t-l\log l-cl.$

Equation (5.5) then implies, again for sufficiently large $t$,

(5.7)
$\log\left(\mathbb{P}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right)\right)\geq
l\log f(t)-(l-1)\log t-cl.$

Combining the above inequality with (5.1), (5.2), and (5.6) gives us that, for
large enough $t$,

$\begin{split}{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\geq\exp\left\\{l\log
t-l\log l+l\log f(t)-(l-1)\log t-cl\right\\}\geq t^{\frac{1}{4}},\end{split}$

since

$l\log l\leq\frac{1}{3}\frac{\log t}{\log\log t}\log\log
t\left(1-\frac{\log\log\log t+\log 3}{\log\log t}\right)\leq\frac{\log t}{3},$

which finishes the proof of the lemma.

Some new notation will be useful throughout the proof of Theorem 2:

######  Definition 3 (Degree of an isolated path).

Given an isolated path $v_{\vec{t}}=\\{v_{t_{j}}\\}_{1\leq j\leq l}$, we
denote by $D_{r}(v_{\vec{t}})$ the sum of the degrees of each of its vertices
at time $r$, i.e. :

$D_{r}(v_{\vec{t}})=\sum_{t_{i}\in\vec{t}}D_{r}(v_{t_{i}}),$

where we assumed that $D_{r}(v_{t_{i}})=0$ if $t_{i}<r$.

Note that if $r>t_{l}$ and $v_{\vec{t}}$ has size $l$, then
$D_{r}(v_{\vec{t}})=2l-1$. Furthermore, by the same reasoning as in (4.1),

(5.8) $\begin{split}{\mathbb{P}}\left(\Delta
D_{s}(v_{\vec{t}})=0~{}\middle|\mathcal{F}_{s}\right)&=f(s+1)\left(1-\frac{D_{s}(v_{\vec{t}})}{2s}\right)+(1-f(s+1))\left(1-\frac{D_{s}(v_{\vec{t}})}{2s}\right)^{2}\\\
&=1-\left(1-\frac{f(s+1)}{2}-(1-f(s+1))\frac{D_{s}(v_{\vec{t}})}{4s}\right)\frac{D_{s}(v_{\vec{t}})}{s}.\end{split}$

Paley-Zigmund’s inequality (see e.g. section $5.5$ of [22]) assures us that,
for any $0\leq\theta\leq 1$,

(5.9)
$\mathbb{P}\left(|\mathcal{S}_{l,\xi}(t)|>\theta{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\right)\geq(1-\theta)^{2}\frac{\left({\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\right)^{2}}{{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|^{2}\right]}.$

If we are able to guarantee that

  1. (i)

${\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\rightarrow\infty$;

  2. (ii)

$\left({\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\right)^{2}=(1-o(1)){\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|^{2}\right]$;

then by choosing
$\theta=\theta(t)={\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]^{-1/2}$,
we see that

$\mathbb{P}\left(|\mathcal{S}_{l,\xi}(t)|>{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]^{1/2}\right)\geq\left(1-{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]^{-1/2}\right)^{2}(1-o(1))=1-o(1),$

thus guaranteeing with probability $1-o(1)$ the existence of many isolated
paths of length $l$, finishing the proof of the theorem.

By Lemma 4, we know that item (i) is true. Therefore from now on we will focus
on proving item (ii).

In order for the isolated path $v_{\vec{t}}$ to appear the following must
happen:

  * •

a vertex $v_{t_{1}}$ must be be created at time $t_{1}$, which happens with
probability $f(t_{1})$;

  * •

between times $t_{1}+1$ and $t_{2}-1$ there can be no new connection to
$v_{t_{1}}$, which, by (5.8), happens with probability

$\prod_{r_{1}=t_{1}+1}^{t_{2}-1}\left(1-\left(1-\frac{f(r_{1})}{2}-(1-f(r_{1}))\frac{1}{4(r_{1}-1)}\right)\frac{1}{r_{1}-1}\right);$

  * •

In general, at time $t_{k}$ a vertex $v_{t_{k}}$ is created and makes its
first connection to $v_{t_{k-1}}$, no new connection is then made to
$\\{v_{t_{j}}\\}_{1\leq j\leq k}$ between times $t_{k}+1$ and $t_{k+1}-1$ for
every $k=2,\dots,l-1$, all this happens with probability equal to

$\displaystyle
f(t_{k})\frac{1}{2(t_{k}-1)}\prod_{r_{k}=t_{k}+1}^{t_{k+1}-1}\left(1-\left(1-\frac{f(r_{k})}{2}-(1-f(r_{k}))\frac{D_{r_{k}}(v_{\vec{t}})}{4(r_{k}-1)}\right)\frac{D_{r_{k}}(v_{\vec{t}})}{r_{k}-1}\right)$
$\displaystyle=f(t_{k})\frac{1}{2(t_{k}-1)}\prod_{r_{k}=t_{k}+1}^{t_{k+1}-1}\left(1-\left(1-\frac{f(r_{k})}{2}-(1-f(r_{k}))\frac{2k-1}{4(r_{k}-1)}\right)\frac{2k-1}{r_{k}-1}\right);$

  * •

finally, a vertex $v_{t_{l}}$ is born at time $t_{l}$, connects to
$v_{t_{l-1}}$ and no new connection is made to $\\{v_{t_{j}}\\}_{1\leq j\leq
l}$ between times $t_{l}+1$ and $t$.

This implies

(5.10)
$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle{\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right)$\mbox{}\hfil\\\
&=f(t_{1})\prod_{r_{1}=t_{1}+1}^{t_{2}-1}\left(1-\left(1-\frac{f(r_{1})}{2}-(1-f(r_{1}))\frac{1}{4(r_{1}-1)}\right)\frac{1}{r_{1}-1}\right)\\\
&\quad\times\dots\times
f(t_{k})\frac{1}{2(t_{k}-1)}\prod_{r_{k}=t_{k}+1}^{t_{k+1}-1}\left(1-\left(1-\frac{f(r_{k})}{2}-(1-f(r_{k}))\frac{2k-1}{4(r_{k}-1)}\right)\frac{2k-1}{r_{k}-1}\right)\\\
&\quad\times\dots\times
f(t_{l})\frac{1}{2(t_{l}-1)}\prod_{r_{l}=t_{l}+1}^{t}\left(1-\left(1-\frac{f(r_{l})}{2}-(1-f(r_{l}))\frac{2l-1}{4(r_{l}-1)}\right)\frac{2l-1}{r_{l}-1}\right).\end{split}$

Given two time vectors $\vec{r}$ and $\vec{t}$, we note that
${\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$ is
only nonzero if $\vec{r}$ and $\vec{t}$ have either disjoint or identical sets
of entries. Our focus now is on proving the following lemma:

######  Lemma 5.

Let $l$ be such that (5.2) is satisfied. For two isolated paths with disjoint
time vectors $\vec{t}$ and $\vec{r}$, we have

(5.11)
$\frac{{\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)}{{\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)}=1+o(1).$

###### Proof.

To prove the above result we will make a comparison between the two
probabilities terms
${\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$
and
${\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$.
We can write both these terms as products in the manner of (5.10). We can then
compare the terms from these products associated to each time $s\in[\xi t,t]$.
There are two cases we must study.

Case 1: $s\in\vec{t}$ but $s\notin\vec{r}$ ($s\notin\vec{t}$ but
$s\in\vec{r}$.).

The product term related to time $s$ in
${\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$ is

(5.12) $\frac{f(s)}{2(s-1)},$

since a new vertex is created and then makes its first connection specifically
to the latest vertex of $\vec{t}$. On the other hand, the term related to time
$s$ in
${\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$
is

$\frac{f(s)}{2(s-1)}\left(1-\left(1-\frac{f(s)}{2}-(1-f(s))\frac{D_{s-1}(v_{\vec{r}})}{4(s-1)}\right)\frac{D_{s-1}(v_{\vec{r}})}{s-1}\right),$

since the term related to $s$ in the product form of
${\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right)$ continues to
be equal to (5.12), but the related term in
${\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$ is

(5.13)
$\left(1-\left(1-\frac{f(s)}{2}-(1-f(s))\frac{D_{s-1}(v_{\vec{r}})}{4(s-1)}\right)\frac{D_{s-1}(v_{\vec{r}})}{s-1}\right).$

The above expression is the term that will appear regarding the time $s$ in
the fraction in the left hand side of (5.11). This case occurs $2l$ times
since the isolated paths are disjoint. Thus, recalling that $s\in[\xi t,t]$,
$l\leq 3^{-1}\log(t)/\log(\log(t))$, and that the degree of each isolated path
is at most $2l-1$, we obtain that there exist constants $c_{1},c_{2}>0$ such
that we can bound the product of all the terms of the form (5.13) from above
by

$\left(1-\frac{c_{1}}{t}\right)^{2l},$

and from below by

$\left(1-\frac{c_{2}l}{t}\right)^{2l}.$

Observe that both products go to $1$ as $t$ goes to infinity.

Case 2: $s\notin\vec{t}$ and $s\notin\vec{r}$.

In ${\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$ as well as
in ${\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right)$ we see
terms of the form (5.13), since we must avoid the isolated paths in both
events. But in the term related to
${\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)$ we
actually observe

$\left(1-\left(1-\frac{f(s)}{2}-(1-f(s))\frac{(D_{s-1}(v_{\vec{t}})+D_{s-1}(v_{\vec{r}}))}{4(s-1)}\right)\frac{(D_{s-1}(v_{\vec{t}})+D_{s-1}(v_{\vec{r}}))}{s-1}\right),$

since we must guarantee that neither isolated path receives a connection. We
note however that

$\displaystyle\left(1-\left(1-\frac{f(s)}{2}-(1-f(s))\frac{D_{s-1}(v_{\vec{r}})}{4(s-1)}\right)\frac{D_{s-1}(v_{\vec{r}})}{s-1}\right)$
$\displaystyle\phantom{**********************}\times\left(1-\left(1-\frac{f(s)}{2}-(1-f(s))\frac{D_{s-1}(v_{\vec{t}})}{4(s-1)}\right)\frac{D_{s-1}(v_{\vec{t}})}{s-1}\right)\quad$
$\displaystyle=\left(1-\left(1-\frac{f(s)}{2}-(1-f(s))\frac{(D_{s-1}(v_{\vec{t}})+D_{s-1}(v_{\vec{r}}))}{4(s-1)}\right)\frac{(D_{s-1}(v_{\vec{t}})+D_{s-1}(v_{\vec{r}}))}{s-1}\right)$
$\displaystyle\phantom{**********************}\times\left(1+O\left(\frac{l^{2}}{t^{2}}\right)\right),$

since $D_{s-1}(v_{\vec{t}}),D_{s-1}(v_{\vec{r}})\leq 2l-1$ and $s\geq\xi t$.
In the fraction in the left hand side of (5.11), we will then have $\Theta(t)$
terms of the form

$\left(1+O\left(\frac{l^{2}}{t^{2}}\right)\right),$

But again, as in Case $1$, their product goes to 1 as $t\to\infty$ since
$l^{2}=o(t)$. This finishes the proof of the Lemma.

We can finally finish the proof of the theorem.

###### Proof of Theorem 2.

Let again $l$ be such that (5.2) is satisfied, and consider $\xi\in(0,1)$.
Since it is impossible for two non disjoint and non equal isolated paths to
exist at the same time, we have that

(5.14)
$\begin{split}{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|^{2}\right]&={\mathbb{E}}\left[\left(\sum_{\vec{t}}\mathbb{1}\left\\{v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right\\}\right)\left(\sum_{\vec{r}}\mathbb{1}\left\\{v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right\\}\right)\right]\\\
&=\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\text{disjoint}\end{subarray}}{\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)+{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right],\end{split}$

and that

$\left({\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\right)^{2}=\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\text{disjoint}\end{subarray}}{\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)+\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\vec{r}\cap\vec{t}\neq\emptyset\end{subarray}}{\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right).$

Therefore, by lemmas 4 and 5, we obtain

(5.15)
$\begin{split}\frac{{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|^{2}\right]}{\left({\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\right)^{2}}&=\frac{\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\text{disjoint}\end{subarray}}{\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l}(t)\right)}{\left({\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\right)^{2}}+\frac{{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]}{\left({\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]\right)^{2}}\\\
&\leq\frac{\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\text{disjoint}\end{subarray}}{\mathbb{P}}\left(v_{\vec{t}},v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)}{\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\text{disjoint}\end{subarray}}{\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)}+\frac{1}{{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]}\\\
&\leq\frac{\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\text{disjoint}\end{subarray}}(1+o(1)){\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)}{\sum_{\begin{subarray}{c}\vec{t},\vec{r}\\\
\text{disjoint}\end{subarray}}{\mathbb{P}}\left(v_{\vec{t}}\in\mathcal{S}_{l,\xi}(t)\right){\mathbb{P}}\left(v_{\vec{r}}\in\mathcal{S}_{l,\xi}(t)\right)}+\frac{1}{{\mathbb{E}}\left[|\mathcal{S}_{l,\xi}(t)|\right]}\\\
&\leq 1+o(1),\end{split}$

which proves the desired result.

##  6\. General upper bound for the diameter: proof of Theorem 3

In this section we provide a proof for Theorem 3. The main idea is to use
Lemmas 1 and 3 to show that, with high probability, all vertices born up to
time $t^{\frac{1}{12}}$ are in a connected component with diameter $2$. We
then use a first moment estimate (Lemma 7 below) to show that the lengths of
the paths formed by newer vertices have the desired upper bound.

Given $k\in\mathbb{N}$ and $k$ times $s_{1},\dots,s_{k}\in\mathbb{N}$ such
that $s_{1}<\dots<s_{k}$, we say that the vector of times
$\vec{s}=(s_{1},\dots,s_{k})$ is a _vertex path_ if in the process
$\\{G_{t}(f)\\}_{t\geq 1}$, at each time $s_{j}$, for $j=2,\dots,k$, a vertex
is born and makes its first (vertex-step) connection to the vertex born at
time $s_{j-1}$. We denote by

$\\{s_{1}\leftarrow s_{2}\leftarrow\dots\leftarrow s_{k}\\}$

the event where $\vec{s}$ is a vertex path. We will show:

######  Lemma 6.

Using the notation above, we have, for each vector
$\vec{s}=(s_{1},\dots,s_{k})$ and step function $f$,

(6.1) $\displaystyle{\mathbb{P}}\left(s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow s_{k}\right)\leq
f(s_{1})\frac{s_{k}-1}{s_{1}+1}\prod_{m=2}^{k}\frac{f(s_{m})}{2(s_{m}-1)}.$

###### Proof.

Consider the events $\\{s_{1}\leftarrow s_{2}\leftarrow\dots\leftarrow
s_{k-1}\\}$ and $\\{s_{k-1}\leftarrow s_{k}\\}$, defined analogously as the
event in the above equation, but for the vectors $(s_{1},\dots,s_{k-1})$ and
$(s_{k-1},s_{k})$ respectively. We have

(6.2) $\begin{split}{\mathbb{P}}\left(s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow
s_{k}\right)&={\mathbb{E}}\left[\mathbb{1}\\{s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow s_{k-1}\\}{\mathbb{P}}\left(s_{k-1}\leftarrow
s_{k}\middle|\mathcal{F}_{s_{k}-1}\right)\right]\\\
&={\mathbb{E}}\left[\mathbb{1}\\{s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow
s_{k-1}\\}f(s_{k})\cdot\frac{D_{s_{k}-1}(v_{s_{k-1}})}{2(s_{k}-1)}\right].\end{split}$

But, crucially, conditioned on the event where a vertex is born at time
$s_{k-1}$, the degree of said vertex at time $s_{k}-1$ depends only on the
connections made after time $s_{k-1}$, and is therefore independent of the
indicator function above. We then obtain, by (4.3),

(6.3)
$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle{\mathbb{P}}\left(s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow s_{k}\right)$\mbox{}\hfil\quad\\\
&={\mathbb{E}}\left[\mathbb{1}\\{s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow
s_{k-1}\\}f(s_{k})\cdot\frac{D_{s_{k}-1}(v_{s_{k-1}})}{2(s_{k}-1)}\middle|Z_{s_{k-1}}=1\right]f(s_{k-1})\\\
&=f(s_{k-1})f(s_{k}){\mathbb{P}}\left(s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow
s_{k-1}\middle|Z_{s_{k-1}}=1\right){\mathbb{E}}\left[\frac{D_{s_{k}-1}(v_{s_{k-1}})}{2(s_{k}-1)}\middle|Z_{s_{k-1}}=1\right]\\\
&={\mathbb{P}}\left(s_{1}\leftarrow s_{2}\leftarrow\dots\leftarrow
s_{k-1}\right)\frac{f(s_{k})}{2(s_{k}-1)}\prod_{m=s_{k-1}}^{s_{k}-2}\left(1+\frac{1}{m}-\frac{f(m+1)}{2m}\right)\\\
&\leq{\mathbb{P}}\left(s_{1}\leftarrow s_{2}\leftarrow\dots\leftarrow
s_{k-1}\right)\frac{f(s_{k})}{2(s_{k}-1)}\exp\left\\{\sum_{m=s_{k-1}}^{s_{k}-2}\left(\frac{1}{m}-\frac{f(m+1)}{2m}\right)\right\\},\end{split}$

by elementary properties of the exponential function. Iterating the above
argument and recalling that the vertex $s_{1}$ is born with probability
$f(s_{1})$, we obtain

(6.4) $\begin{split}{\mathbb{P}}\left(s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow s_{k}\right)&\leq
f(s_{1})\exp\left\\{\sum_{m=s_{1}}^{s_{k}-2}\left(\frac{1}{m}-\frac{f(m+1)}{2m}\right)\right\\}\prod_{m=2}^{k}\frac{f(s_{m})}{2(s_{m}-1)}\\\
&\leq
f(s_{1})\frac{s_{k}-1}{s_{1}+1}\prod_{m=2}^{k}\frac{f(s_{m})}{2(s_{m}-1)},\end{split}$

finishing the proof of the lemma.

Given $k,t_{0},t\in\mathbb{N}$, denote by $\mathcal{V}_{k,t_{0}}(t)$ the set
of all vertex-paths of length $k$ whose vertices were born between times
$t_{0}$ and $t$. Our goal now is to bound from above the expectation of
$|\mathcal{V}_{k,t_{0}}(t)|$, this will be accomplished in the next lemma.

######  Lemma 7.

Using the notation above defined, we have, for $k,t_{0},t\in\mathbb{N}$,

(6.5) ${\mathbb{E}}\left[|\mathcal{V}_{k,t_{0}}(t)|\right]\leq
C_{1}\exp\left\\{2\log
t-(k-2)\left(\log(k-2)+C_{2}+\log\left(\sum_{j=t_{0}}^{t}\frac{f(j)}{j-1}\right)\right)\right\\}.$

###### Proof.

We will use Lemma 6 and the an application of the union bound. First, fix
$s_{1},s_{k}\in\mathbb{N}$ such that $t_{0}\leq s_{1}<s_{k}\leq t$. We have,
by Stirling’s approximation formula and the positivity of the terms involved,

(6.6) $\begin{split}\sum_{\begin{subarray}{c}s_{2},s_{3},\dots,s_{k-1}\\\
s_{1}<s_{2}<\dots<s_{k-1}<s_{k}\end{subarray}}\prod_{m=2}^{k-1}\frac{f(s_{m})}{s_{m}-1}&\leq\frac{1}{(k-2)!}\left(\sum_{j=t_{0}}^{t}\frac{f(j)}{j-1}\right)^{k-2}\\\
&\leq
C\exp\left\\{-(k-2)\left(\log(k-2)-1-\log\left(\sum_{j=t_{0}}^{t}\frac{f(j)}{j-1}\right)\right)\right\\}.\end{split}$

We can then show, by the above equation, Lemma 6, and the union bound,

(6.7)
$\begin{split}{\mathbb{E}}\left[|\mathcal{V}_{k,t_{0}}(t)|\right]&\leq\sum_{\begin{subarray}{c}s_{1},\dots,s_{k}\\\
t_{0}\leq s_{1}<\dots<s_{k}\leq
t\end{subarray}}{\mathbb{P}}\left(s_{1}\leftarrow
s_{2}\leftarrow\dots\leftarrow s_{k}\right)\\\
&\leq\sum_{\begin{subarray}{c}s_{1},\dots,s_{k}\\\ t_{0}\leq
s_{1}<\dots<s_{k}\leq
t\end{subarray}}f(s_{1})\frac{s_{k}-1}{s_{1}+1}\prod_{m=2}^{k}\frac{f(s_{m})}{2(s_{m}-1)}\\\
&=\frac{1}{2^{k-1}}\sum_{\begin{subarray}{c}s_{1},s_{k}\\\ t_{0}\leq
s_{1}<s_{k}\leq
t\end{subarray}}\frac{f(s_{1})f(s_{k})}{s_{1}+1}\sum_{\begin{subarray}{c}s_{2},\dots,s_{k-1}\\\
s_{1}<s_{2}<\dots<s_{k-1}<s_{k}\end{subarray}}\prod_{m=2}^{k-1}\frac{f(s_{m})}{s_{m}-1}\\\
&\leq
C\exp\left\\{-(k-2)\left(\log(k-2)+C_{2}-\log\left(\sum_{j=t_{0}}^{t}\frac{f(j)}{j-1}\right)\right)\right\\}\sum_{\begin{subarray}{c}s_{1},s_{k}\\\
t_{0}\leq s_{1}<s_{k}\leq t\end{subarray}}\frac{f(s_{1})f(s_{k})}{s_{1}+1}\\\
&\leq C\exp\left\\{2\log
t-(k-2)\left(\log(k-2)+C_{2}-\log\left(\sum_{j=t_{0}}^{t}\frac{f(j)}{j-1}\right)\right)\right\\},\end{split}$

thus concluding the proof of the result.

We can finally finish the proof of Theorem 3.

###### Proof of Theorem 3.

We prove part (a) first.

Proof of part (a): This part follows immediately from the fact that the B-A
random tree has diameter bounded by $\log t$ a.a.s (see Theorem $7.1$ of [27])
combined with Proposition 2.5 which states that the diameter is an increasing
graph observable.

Proof of part (b): Recall that, in this part of the theorem, $f$ is under
condition (S), which holds if $\sum_{s=2}^{\infty}f(s)/s$ is finite.

For $t_{0},t\in\mathbb{N}$ and $\delta\in(0,1)$, let $A_{\delta}(t_{0},t)$ be
the event where every vertex born before time $t_{0}$ has degree at least
$t^{\delta}$ in $G_{t}(f)$. For $\varepsilon\in(0,1)$, let
$B_{\varepsilon}(t)$ be the event where there exists a vertex $v$ in
$V(G_{t}(f))$ such that $D_{t}(v)\geq t^{1-\varepsilon}$. Then, by Lemmas 1
and 3, we have

(6.8) ${\mathbb{P}}\left(A_{\frac{1}{15}}(t^{\frac{1}{12}},t)\right)\geq
1-Ct^{-144^{-1}},\quad\quad{\mathbb{P}}\left(B_{\frac{1}{30}}(t)\right)\geq
1-t^{-2}.$

We have, on the event where two vertices $u_{1},u_{2}\in V(G_{t}(f))$ are such
that $D_{t}(u_{1})\geq t^{15^{-1}}$ and $D_{t}(u_{2})\geq t^{1-30^{-1}}$,

(6.9) $\begin{split}{\mathbb{P}}\left(u_{1}\nleftrightarrow u_{2}\text{ in
}G_{2t}(f)\right)&\leq\prod_{s=t+1}^{2t}\left(1-\frac{f(s)}{2(s-1)}\right)\left(1-\frac{t^{15^{-1}}t^{1-30^{-1}}}{4(s-1)^{2}}\right)\\\
&\leq\exp\left\\{-\frac{t^{15^{-1}}t^{1-30^{-1}}}{16t^{2}}\cdot t\right\\}\\\
&=\exp\left\\{-\frac{t^{-30^{-1}}}{16}\right\\}.\end{split}$

Recall the notation $v_{i}$ symbolizing the vertex born at time
$i\in\mathbb{N}$. Together with (6.8) and the union bound, the above equation
implies

$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle{\mathbb{P}}\left(\exists
i,j\in\mathbb{N},\text{ such that }1\leq i<j\leq
t^{12^{-1}},Z_{i}=Z_{j}=1,\text{ and }\mathrm{dist}(v_{i},v_{j})>2\text{ in
}G_{2t}(f)\right)$\mbox{}\hfil\phantom{***}\\\ &\leq
Ct^{-144^{-1}}+t^{-2}+\sum_{1\leq i<j\leq
t^{\frac{1}{12}}}{\mathbb{P}}\left(A_{\frac{1}{15}}(t^{\frac{1}{12}},t),B_{\frac{1}{30}}(t),\mathrm{dist}(v_{i},v_{j})>2\text{
in }G_{2t}(f)\right)\\\ &\leq
Ct^{-144^{-1}}+t^{-2}+t^{-6^{-1}}\exp\left\\{-\frac{t^{-30^{-1}}}{16}\right\\}\\\
&\leq Ct^{-144^{-1}}.\end{split}$

This implies the existence of a constant $C_{1}>0$ such that the probability
of there existing two vertices born before time $C_{1}t^{12^{-1}}$ such that
the distance between said vertices is larger than $2$ in $G_{t}(f)$ is
polynomially small in $t$. We now turn our attention to vertices born after
$t^{\frac{1}{13}}$. We will use Lemma 7 in order to bound the probability of
there existing long vertex-paths formed by vertices born after
$t^{\frac{1}{13}}$, the notion of a “long” path being $f$-dependent. Let
$V_{t}(t^{\frac{1}{13}})$ denote the set of all vertices of $V(G_{t}(f))$ born
before time $t^{\frac{1}{13}}$, let ${\bf
d}_{\mathrm{max}}(t^{\frac{1}{13}},t)$ be the length of a maximal vertex-path
of vertices born between times $t^{\frac{1}{13}}$ and $t$. Let $u_{1},u_{2}\in
V(G_{t}(f))$. Since $G_{t}(f)$ is connected,

(6.10)
$\begin{split}\mathrm{dist}(u_{1},u_{2})&\leq\mathrm{dist}(u_{1},V_{t}(t^{\frac{1}{13}}))+\mathrm{diam}(V_{t}(t^{\frac{1}{13}}))+\mathrm{dist}(u_{2},V_{t}(t^{\frac{1}{13}}))\\\
&\leq 2{\bf
d}_{\mathrm{max}}(t^{\frac{1}{13}},t)+\mathrm{diam}(V_{t}(t^{\frac{1}{13}})).\end{split}$

But we know that $\mathrm{diam}(V_{t}(t^{\frac{1}{13}}))\leq 2$ with high
probability. Bounding ${\bf d}_{\mathrm{max}}(t^{\frac{1}{13}},t)$ then gives
us an a.a.s. upper bound for the diameter of $G_{t}(f)$.

Now, given $t\in\mathbb{N}$, if

(6.11) $k\geq 3\left(\frac{\log
t}{-\log\left(\sum_{s=t^{\frac{1}{13}}}^{t}\frac{f(s)}{s-1}\right)}\wedge\frac{\log
t}{\log\log t}\right),$

then, by Lemma 7, and since
$\log\left(\sum_{j=t^{\frac{1}{13}}}^{t}\frac{f(j)}{j-1}\right)$ is eventually
negative for large $t$ (recall again that $f$ satisfies (S)), we have,

(6.12) $\begin{split}{\mathbb{P}}\left({\bf
d}_{\mathrm{max}}>k\right)&\leq{\mathbb{E}}\left[|\mathcal{V}_{k,t^{1/13}}(t)|\right]\\\
&\leq C_{1}\exp\left\\{2\log
t-(k-2)\left(\log(k-2)+C_{2}-\log\left(\sum_{j=t^{\frac{1}{13}}}^{t}\frac{f(j)}{j-1}\right)\right)\right\\}\\\
&\leq Ct^{-\frac{1}{2}}.\end{split}$

The above upper bound and (6.10) proves part (b).

Proof of part (c): Recall that in this part, we are under condition (Lκ),
which holds if, for $\kappa\in(0,1)$ and every $t\in\mathbb{N}$ sufficiently
large, one has

(6.13) $\sum_{s=t^{1/13}}^{t}\frac{f(s)}{s}<(\log t)^{\kappa}.$

Then, let $k$ be so that

$k\geq\frac{3}{1-\kappa}\frac{\log t}{\log\log t}.$

We then obtain, again by Lemma 7, for sufficiently large $t$,

(6.14)
$\begin{split}\@ADDCLASS{ltx_eqn_lefteqn}$\displaystyle{\mathbb{P}}\left({\bf
d}_{\mathrm{max}}>k\right)$\mbox{}\hfil\quad\quad\\\
&\leq{\mathbb{E}}\left[|\mathcal{V}_{k,t^{1/13}}(t)|\right]\\\ &\leq
C_{1}\exp\left\\{2\log
t-(k-2)\left(\log(k-2)+C_{2}-\log\left(\sum_{j=t^{\frac{1}{13}}}^{t}\frac{f(j)}{j-1}\right)\right)\right\\}\\\
&\leq C_{1}\exp\left\\{2\log t-\frac{3}{1-\kappa}\frac{\log t}{\log\log
t}\left((1-\kappa)\log\log t-C-\log\log\log t\right)\right\\}\\\ &\leq
Ct^{-\frac{1}{2}}.\end{split}$

Finally, the above upper bound together with (6.10) finishes the proof of the
Theorem.

##  7\. The family of regularly varying functions

In this section we explore our results when more information on $f$ is
provided. In particular, we assume that $f$ satisfies condition (RVγ) for
$\gamma\in[0,1)$. Recall that this condition holds whenever

$\exists\gamma,\text{ such that }\forall
a>0,\;\lim_{t\to\infty}\frac{f(at)}{f(t)}=\frac{1}{a^{\gamma}}.$

Also recall that when $f$ satisfies the above condition for $\gamma>0$ we say
it is a regular varying function with index of regular variation $-\gamma$.
The case $\gamma=0$ is said to be slowly varying.

To prove the results under the assumption of regular variation our arguments
rely on the theorems from Karamata’s theory. In particular, the Representation
Theorem (Theorem 1.4.1 of [8]) and Karamata’s theorem (Proposition 1.5.8 of
[8]). The former states that if $f$ is a regularly varying function with index
$-\gamma$, then there exists a slowly varying function $\ell$ such that $f$ is
of the form

(7.1) $f(t)=\frac{\ell(t)}{t^{\gamma}}.$

Whereas, the latter states that if $\ell$ is a slowly varying function, then,
for any $a<1$

(7.2)
$\int_{1}^{t}\frac{\ell(x)}{x^{a}}\mathrm{d}x\sim\frac{\ell(t)t^{1-a}}{1-a},$

and for $a>1$, we have

(7.3)
$\int_{t}^{\infty}\frac{\ell(x)}{x^{a}}\mathrm{d}x\sim\frac{\ell(t)}{(a-1)t^{a-1}}.$

We begin by proving Corollary 1.4, which gives lower and upper bounds for the
clique number $\omega(G_{t}(f))$.

###### Proof of Corollary 1.4.

We prove part (a) first.

Proof of part (a): The lower bound follows from (7.1), when $f$ is regularly
varying, (7.2) and Theorem 1. Just observe that, if $f$ is regularly varying,
then $F(t)=\Theta({t^{1-\gamma}})$, whereas if it is slowly, we have
$F(t)=\Theta(f(t)t)$. In the latter case, we appeal to another result from
Karamata’s Theory (Corollary A.6 of [2]) which assures that for all
$\varepsilon>0$,

(7.4) $\frac{f(t)}{t^{\varepsilon}}\stackrel{{\scriptstyle
t\to\infty}}{{\longrightarrow}}0.$

Then, by Theorem 1, $G_{t}(f)$ has, with probability $1-o(1)$, a clique of
order $C_{\varepsilon}F(t^{\frac{1}{2}(1-\frac{\varepsilon}{2})})$, which
gives the desired lower bound for $\omega(G_{t}(f))$. The upper bound comes
from the deterministic bound that says that a graph with $t$ (simple) edges
has at most $t^{\frac{3}{2}}$ triangles (see e.g. Theorem $4$ of [24]), and
the fact that a complete subgraph with $k$ vertices has $6^{-1}k(k-1)(k-2)$
triangles.

Proof of part (b): First observe that for any small $\varepsilon>0$ by (7.2),
$F(t^{\frac{1}{2}(1-\varepsilon)})\gg\log\log t$ for large enough $t$. Thus,
by (3.8), we have that

(7.5) ${\mathbb{P}}\left(\omega(G_{t}(f))\geq
C_{\varepsilon}F(t^{\frac{1-\varepsilon}{2}})\right)\geq 1-\frac{2}{\log t}.$

Now, define the following sequence of deterministic times

(7.6) $t_{k}:=(1+\varepsilon)^{k^{2}}.$

By the first Borel-Cantelli Lemma and (7.5) we have that,

(7.7)
$\liminf_{k\to\infty}\frac{\log\omega(G_{t_{k}}(f))}{\log(C_{\varepsilon}F(t_{k}^{\frac{1-\varepsilon}{2}}))}\geq
1,\;\text{a.s.}$

Using that $f$ is slowly varying, Karamata’s Theorem (7.2), and (7.4), we also
have that

(7.8)
$\lim_{t\to\infty}\frac{\log(C_{\varepsilon}F(t^{\frac{1-\varepsilon}{2}}))}{\log
F(t^{\frac{1}{2}})}=1-\frac{\varepsilon}{2}.$

For the same reason, it also follows that

(7.9) $\lim_{t\to\infty}\frac{\log
F(t^{\frac{1}{2}})}{\log(7t^{\frac{1}{2}})}=1.$

Then (7.7) yields

(7.10) $\liminf_{k\to\infty}\frac{\log\omega(G_{t_{k}}(f))}{\log
F(t_{k}^{\frac{1}{2}})}\geq 1-\varepsilon,\;\text{a.s.}.$

And using the upper bound given in part (a) and (7.9) we also obtain

(7.11) $\limsup_{k\to\infty}\frac{\log\omega(G_{t_{k}}(f))}{\log
F(t_{k}^{\frac{1}{2}})}\leq 1,\;\text{a.s.}$

Now, note that $\omega(G_{t}(f))\leq\omega(G_{t+1}(f))$, since $G_{t}(f)$ is
contained in $G_{t+1}(f)$. Thus, for any time $t\in(t_{k},t_{k+1})$ it follows

(7.12) $\begin{split}\frac{\log(\omega(G_{t_{k}}(f)))}{\log
F(t_{k+1}^{\frac{1}{2}})}\leq\frac{\log(\omega(G_{t}(f)))}{\log
F(t^{\frac{1}{2}})}\leq\frac{\log(\omega(G_{t_{k+1}}(f)))}{\log
F(t_{k}^{\frac{1}{2}})}.\end{split}$

Using (7.10), (7.11) and that

$\lim_{k\to\infty}\frac{\log F(t_{k+1}^{\frac{1}{2}})}{\log
F(t_{k}^{\frac{1}{2}})}=1$

we finally obtain that

(7.13)
$1-\varepsilon\leq\liminf_{t\to\infty}\frac{\log(\omega(G_{t}(f)))}{\log
F(t^{\frac{1}{2}})}\leq\limsup_{t\to\infty}\frac{\log(\omega(G_{t}(f)))}{\log
F(t^{\frac{1}{2}})}\leq 1,\;\text{a.s.}.$

Since $\varepsilon$ was arbitrarily chosen, we conclude the proof.

The next step is to prove the constant order of the diameter of the graphs
generated by regularly varying functions and how it depends on the index of
regular variation on infinity. This result is stated on Theorem 4 and we
provide a proof for it below.

###### Proof of Theorem 4.

We begin proving the lower bound.

Lower bound: By the Representation Theorem (7.1) we have that there exists a
slowly varying function $\ell$ such that $f(t)=\ell(t)/t^{\gamma}$. Moreover,
(7.4) implies that

(7.14) $\frac{\log\ell(t)}{\log t}\to 0.$

Thus, we have that

(7.15) $-\frac{\log t}{\log f(t)}=\frac{\log
t}{\gamma\log(t)+\log\ell(t)}=\frac{1-o(1)}{\gamma}.$

Applying Theorem 2 gives us a lower bound of order $\gamma^{-1}$.

Upper bound: By the Representation Theorem and (7.4), we have that $f$ also
satisfies condition (S). Just notice that

(7.16)
$\sum_{s=1}^{\infty}\frac{f(s)}{s}=\sum_{s=1}^{\infty}\frac{\ell(s)}{s^{1+\gamma}}<\infty.$

And by Karamata’s Theorem (Equation (7.3) in particular) we have that

(7.17)
$\sum_{s=t^{\frac{1}{13}}}^{t}\frac{\ell(s)}{s^{1+\gamma}}\sim\frac{\ell(t)}{t^{\gamma\frac{\gamma}{13}}}\implies-\frac{\log
t}{\log\left(\sum_{s=t^{\frac{1}{13}}}^{t}\frac{\ell(s)}{s^{1+\gamma}}\right)}\sim\frac{\log
t}{\frac{\gamma}{13}\log t+\log\ell(t)}=\frac{13(1-o(1))}{\gamma}$

And finally, applying Theorem 3 we prove the result.

##  8\. Final comments

We end this paper with a brief discussion on the affine version of our model
and how dropping some regularity conditions on $f$ may produce a sequence of
graphs $\\{G_{t}\\}_{t\in\mathbb{N}}$ that has a subsequence which is
essentially of complete graphs and another one which is close to the BA-model.

### Affine version

At the introduction, we have discussed the affine version of the PA-rule,
which we recall below.

${\mathbb{P}}\left(v_{t+1}\rightarrow
u\middle|G_{t}\right)=\frac{\text{degree}(u)+\delta}{\sum_{w\in
G_{t}}(\text{degree}(w)+\delta)}.$

In [2], the authors showed that the effect of the affine term $\delta$
vanishes in the long run when one is dealing with the empirical degree
distribution. I.e., their results show that $\delta$ has no effect on the
degree sequence of the graphs, what is not observed in the affine version of
the BA-model, for which the exponent of the power-law distribution depends on
$\delta$, see [13]. However, regarding the diameter, we believe $\delta$ may
have an increasing/decreasing effect on the diameter’s order. One also may
find interesting to consider $\delta=\delta(t)$ and investigate which one
takes over: is it the edge-step function or the affine term?

### Dropping regularity conditions

In this part we illustrate that dropping some assumptions on $f$ may produce a
somewhat pathological sequence of graphs. For instance, if we drop the
assumption of $f$ being non-increasing, we may obtain a sequence of graphs
whose diameter sequence oscillates between $1$ and $\log t$. More generally,
the sequence of graphs oscillates between graphs similar to the BA-random
tree, $\\{\mathrm{BA}_{t}\\}_{t\in\mathbb{N}}$, and graphs close to complete
graphs.

Let $(t_{k})_{k\in\mathbb{N}}$ be the following sequence: $t_{0}=1$ and
$t_{k+1}:=\exp\\{t_{k}\\}$, for $k>1$. Now, let $h$ be the edge-step function
defined as follows

(8.1) $h(t)=\begin{cases}1&\quad\text{ if }t\in[t_{2k},t_{2k+1}],\\\
0&\quad\text{ if }t\in(t_{2k+1},t_{2k+2}).\end{cases}$

The idea behind such $h$ is that between times $[t_{2k},t_{2k+1}]$ the process
behaves essentially as the traditional BA-model, whereas at interval
$(t_{2k+1},t_{2k+2})$ the process “messes things up” connecting almost all
vertices by only adding new edges. Moreover, in both regimes the process has
time enough to “forget about what was built in the past”.

Using Lemma 3 and reasoning as in (6.9), one may prove that

$\mathrm{diam}_{G_{t_{2k+1}^{13}}(h)}G_{t_{2k+1}}(h)\leq 2,\text{ a.a.s.}$

However, the process does not add any new vertex in the interval
$(t_{2k+1},t_{2k+2})$. Therefore, $\mathrm{diam}G_{t_{2k+2}}(h)\leq 2$, a.a.s.

On the other hand, if we sample $G_{t_{2k+3}}(h)$ and $\mathrm{BA}_{t_{2k+3}}$
from the doubly-labeled tree $\mathcal{T}_{t_{2k+3}}$ it follows that the
quantity

$\max_{u>t_{2k+2}}\mathrm{dist}(u,\mathcal{T}_{t_{2k+2}})$

remains the same under $h$ and under $f\equiv 1$, since paths using vertices
added after $t_{2k+2}$ belong to the graphs generated by both functions.
Finally, noting that $\mathcal{T}_{t_{2k+2}}$ has diameter at most $\log
t_{2k+2}=t_{2k+1}$ w.h.p, which means it is a very small graph when compared
to $\mathcal{T}_{t_{2k+3}}$, it is not hard to see that the diameter of
$G_{2k+3}(h)$ has the same order the diameter from $\mathrm{BA}_{t_{2k+3}}$.

Observe that the function $h$ may be constructed considering it equal to any
other edge-step function $f$ instead of the constant case $1$. Roughly
speaking, when we sample both processes from the doubly-labeled random tree,
up to a very small subgraph, the graph $G_{t_{2k+1}}(h)$ is similar to
$G_{t_{2k+1}}(f)$, whereas, $G_{t_{2k}}(h)$ is a graph of diameter at most $2$
and whose vertices have degree at least a subpolynomial of $t_{2k}$.

The conclusion is that if we drop some monoticity assumption on $f$, we may
obtain a sequence of graphs having at least two subsequences that are
completely different as graphs.

Acknowledgements  We are thankful to Roberto Imbuzeiro Oliveira for the many
inspiring and pleasant conversations. C.A. was partially supported by Fundação
de Amparo à Pesquisa do Estado de São Paulo (FAPESP), grants 2013/24928-2 and
2015/18930-0, and by the Deutsche Forschungsgemeinschaft (DFG). R.R. was
partially supported by Conselho Nacional de Desenvolvimento Científico e
Tecnológico (CNPq) and 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). R.S. has been partially
supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico
(CNPq) and by FAPEMIG (Programa Pesquisador Mineiro), grant PPM 00600/16.

## References

  * [1] C. Alves, R. Ribeiro, and R. Sanchis.  Large communities in a scale-free network.  Journal of Statistical Physics, 166(1):137–149, 2017.
  * [2] C. Alves, R. Ribeiro, and R. Sanchis.  Preferential attachment random graphs with edge-step functions.  04 2017.
  * [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. Backhausz and T. F. Móri.  Asymptotic properties of a random graph with duplications.  J. Appl. Probab., 52(2):375–390, 06 2015.
  * [5] A-L. Barabási and R. Albert.  Emergence of scaling in random networks.  Science, 1999.
  * [6] N. Berger, B. Bollobás, C. Borgs, J. Chayes, and O. Riordan.  Degree distribution of the fkp network model.  Theoretical computer science, 379(3):306–316, 2007.
  * [7] G. Bianconi and M. Marsili.  Emergence of large cliques in random scale-free networks.  EPL (Europhysics Letters), 74(4):740, 2006.
  * [8] N. H. Bingham, C. M. Goldie, and J. L. Teugels.  Regular variation, volume 27 of encyclopedia of mathematics and its applications, 1989.
  * [9] B. Bollobás and O. Riordan.  Mathematical results on scale-free random graphs. in handbook of graphs and networks: From the genome to the internet.  pages 1–34, 2003.
  * [10] B. Bollobás and O. Riordan.  Robustness and vulnerability of scale-free random graphs.  Internet Math., 1(1):1–35, 2003.
  * [11] S. Chatterjee and R. Durrett.  Contact processes on random graphs with power law degree distributions have critical value 0.  Ann. Probab., 37(6):2332–2356, 11 2009.
  * [12] F. Chung and L. Lu.  Complex Graphs and Networks (Cbms Regional Conference Series in Mathematics).  American Mathematical Society, Boston, MA, USA, 2006.
  * [13] C. Cooper and A. Frieze.  A general model of web graphs.  Random Struct. Algorithms, 22(3):311–335, 2003.
  * [14] S. Dereich and M. Ortgiese.  Robust analysis of preferential attachment models with fitness.  Combinatorics, Probability and Computing, 23(3):386–411, 2014\.
  * [15] S. Dommers, R. van der Hofstad, and G. Hooghiemstra.  Diameters in preferential attachment models.  Journal of Statistical Physics, 139(1):72–107, 2010.
  * [16] N. Eggemann and S.D. Noble.  The clustering coefficient of a scale-free random graph.  Discrete Applied Mathematics, 2011.
  * [17] P. Erdös and A. Rényi.  On random graphs i.  Publicationes Mathematicae Debrecen, 6:290, 1959.
  * [18] D. Fernholz and V. Ramachandran.  The diameter of sparse random graphs.  Random Structures and Algorithms, 30(4):482–516, 2007.
  * [19] E. Jacob and P. Mörters.  Spatial preferential attachment networks: Power laws and clustering coefficients.  Ann. Appl. Probab., 25(2):632–662, 04 2015.
  * [20] E. Jacob and P. Mörters.  The contact process on scale-free networks evolving by vertex updating.  Royal Society Open Science, 4(5):170081, 2017.
  * [21] S. Janson, T. Luczak, and I. Norros.  Large cliques in a power-law random graph.  J. App. Prob., 2010.
  * [22] Russell Lyons and Yuval Peres.  Probability on Trees and Networks, volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics.  Cambridge University Press, New York, 2016.  Available at http://pages.iu.edu/~rdlyons/.
  * [23] Y. Malyshkin and E. Paquette.  The power of choice combined with preferential attachement.  Electronic Communications in Probability, 19(44):1–13, 2014.
  * [24] I. Rivin.  Counting cycles and finite dimensional lp norms.  Advances in applied mathematics, 29(4):647–662, 2002.
  * [25] S.H Strogatz and D. J. Watts.  Tcollective dynamics of ’small-world’ networks.  Nature, 1998.
  * [26] E. Thörnblad.  Asymptotic degree distribution of a duplication–deletion random graph model.  Inter. Math., 11, 03 2014.
  * [27] R. Van Der Hofstad.  Random graphs and complex networks volume 2.  Available on http://www. win. tue. nl/ rhofstad/ NotesRGCNII. pdf, 2018.
  * [28] 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.