# Color-avoiding percolation on the Erdős-Rényi random graph

Lyuben Lichev  Univ. Jean Monnet, Saint-Etienne, France  Univ. Claude Bernard
Lyon 1, Lyon, France  Bruno Schapira  Univ. Claude Bernard Lyon 1, Lyon,
France  Univ. Aix-Marseille, Marseille, France

###### Abstract

We consider a recently introduced model of color-avoiding percolation defined
as follows. Every edge in a graph $G$ is colored in some of $k\geq 2$ colors.
Two vertices $u$ and $v$ in $G$ are said to be _CA-connected_ if $u$ and $v$
may be connected using any subset of $k-1$ colors. CA-connectivity defines an
equivalence relation on the vertex set of $G$ whose classes are called _CA-
components_.

We study the component structure of a randomly colored Erdős-Rényi random
graph of constant average degree. We distinguish three regimes for the size of
the largest component: a supercritical regime, a so-called intermediate
regime, and a subcritical regime, in which the largest CA-component has
respectively linear, logarithmic, and bounded size. Interestingly, in the
subcritical regime, the bound is deterministic and given by the number of
colors.

Keywords: color-avoiding percolation, Erdős-Rényi random graph.

MSC Class: 05C80, 60C05, 60K35, 82B43

##  1 Introduction

In this paper, we are interested in the model of (edge-)color-avoiding
percolation defined as follows. Fix a set of $k\geq 2$ colors and a graph $G$,
and color every edge of $G$ in at least one color. We say that two vertices
$u$ and $v$ in $G$ are _color-avoiding connected_ , or _CA-connected_ for
short, if $u$ and $v$ may be connected using any subset of $k-1$ colors. In
fact, CA-connectivity defines an equivalence relation on the vertex set of $G$
whose classes are called _CA-components_. The model has been motivated by a
number of real-world applications, for example, avoiding a set of mistrusted
information channels (where colors correspond to eavesdroppers), or avoiding a
set of possibly corrupted links in a network. In a sense, a network with large
CA-components may be considered resistant to attacks from a set of adversaries
where the adversaries control all channels but can only attack the network
separately.

Color-avoiding percolation was introduced by Krause, Danziger, and Zlatić [7,
8]. In their work, the authors were interested in vertex-colored graphs and
analyzed a vertex analog of CA-connectivity. While some empirical observations
were made for scale-free networks, the focus was put on Erdős-Rényi random
graphs due to their better CA-connectivity [7]. In a subsequent work, Kadović,
Krause, Caldarelli, and Zlatić [5] defined mixed CA-percolation where both
vertices and edges have colors. To a large extent, each of these foundational
papers based their conclusions on experimental evidence.

Precise mathematical treatment of the subject is challenging for several
reasons. Firstly, unlike connected components in a graph, the CA-components
cannot be found by a local exploration of the graph in general. Indeed, note
that even if two vertices are neighbors in the graph, all paths that connect
them and avoid a certain color may be rather long. Secondly, while one edge in
a graph may merge at most two components or divide a single connected
component into two parts, a single colored edge may lead to a merging of a lot
of different CA-components. For example, consider two parallel paths of length
$2\ell+1$, and for every $i\in[2\ell+1]$, connect the $i$-th vertex in one of
the paths with the $i$-th vertex in the other path. Also, color the odd edges
in the paths in blue, the even edges in red, and the edges between them in
green, see Figure 1. Then, it may be easily checked that all CA-components in
the obtained graph are of size 1 while adding a blue edge between the last
vertices in the two paths creates $2\ell+1$ components of size 2 at once. Last
but not least, in the framework of random graphs, deleting the edges in two
different colors from the original graph leads to two distinct subgraphs that
can have a large intersection, and can therefore be highly correlated.

Figure 1: Blue, red and green edges are represented by dotted, dashed, and
solid segments, respectively. One may easily check that on the left, every
vertex is alone in its CA-component, while on the right, the addition of a
single blue edge leads to the appearance of many CA-components of size 2.

To our knowledge, a rigorous mathematical treatment of the behavior of color-
avoiding percolation on random graphs has only been studied in a recent work
of Ráth, Varga, Fekete, and Molontay [10]. In their paper, they show that
under a certain subcriticality assumption, the number of CA-components of a
given fixed size renormalized by $n$ converges in probability to a fixed
constant. Moreover, under the same assumption, it is proved that the size of
the largest CA-component renormalized by $n$ converges in probability to a
fixed constant. They also characterize the behavior of that constant in the
barely supercritical regime.

Our goal here is to go further in the analysis of the structure of CA-
components in a randomly colored Erdős-Rényi random graph around the threshold
of appearance of a giant component. Apart from simplifying the approach of
[10] and getting rid of their additional hypothesis, we show that the
parameter space may be naturally divided into three regimes. In each of them,
we conduct a careful analysis of the size of the largest CA-component as well
as the number of small CA-components.

###  1.1 Main results

For a positive integer $m$, we denote $[m]=\\{1,\ldots,m\\}$. In particular,
we reserve the notation $[k]$ to denote the set of colors, and the notation
$[n]$ for the set of vertices of our graphs. Recall that for $p\in[0,1]$, the
Erdős-Rényi random graph $G(n,p)$, or ER random graph for short, with
parameters $n$ and $p$ is the graph on the vertex set $[n]$ where the edge
between any two distinct vertices is present with probability $p$,
independently from all other edges.

Consider now a non-increasing sequence of positive real numbers
$\lambda_{1}\geq\dots\geq\lambda_{k}$, and define a family of $k$ independent
Erdős-Rényi random graphs $G_{i}=G(n,\tfrac{\lambda_{i}}{n})$ for $i\in[k]$ on
the same vertex set $[n]$ (alternatively, this family can be seen as a
multigraph $([n],E_{1},\dots,E_{k})$ where $E_{i}$ is the edge set of
$G_{i}$). In order to easily refer to and distinguish the graphs
$(G_{i})_{i=1}^{k}$, we say that for every $i\in[k]$, the edges of $G_{i}$ are
given color $i$. Define further

$\Lambda=\lambda_{1}+\dots+\lambda_{k},\quad\text{and}\quad\lambda_{i}^{*}=\Lambda-\lambda_{i}\quad\text{for
every }i\in[k].$

In particular,
$\lambda_{1}^{*}\leq\lambda_{2}^{*}\leq\dots\leq\lambda_{k}^{*}$. Also, we set

$G=G_{1}\cup\ldots\cup G_{k},$ (1)

and for $I\subseteq[k]$,

$G_{I}=\bigcup_{i\in I}G_{i},\quad\text{and}\quad
G^{I}=\bigcup_{i\in[k]\setminus I}G_{i},$

with the shorthand notation $G_{i}$ and $G^{i}$, respectively, when
$I=\\{i\\}$.

Recall that two vertices $u$ and $v$ in $G$ are CA-connected if $u$ and $v$
are connected in each of the graphs $(G^{i})_{i=1}^{k}$. Moreover, CA-
connectivity is an equivalence relation with classes called CA-components. The
CA-component of a vertex $u\in[n]$ is denoted by $\widetilde{\mathcal{C}}(u)$,
and $|\widetilde{\mathcal{C}}(u)|$ denotes its size. Our main object of
interest is the size of the largest CA-component in $G$. Under the assumption
that $\sum_{i\in I}\lambda_{i}<1$ for every set $I\subseteq[k]$ of size $k-2$,
it was shown in [10] that there exists a constant $a\in[0,1]$ such that

$\frac{\max_{u\in[n]}|\widetilde{\mathcal{C}}(u)|}{n}\xrightarrow[n\to\infty]{\mathbb{P}}a,$
(2)

and that the constant $a$ is positive if and only if $\lambda_{1}^{*}>1$,
which is called the _supercritical regime_. Here, we improve this result in
three directions:

  * •

We observe that (2) can be easily derived from the convergence in distribution
of the neighborhood of a typical vertex, and this does not require any
additional technical assumptions.

  * •

In the subcritical regime (that is, when $\lambda_{k}^{*}<1$), we prove that
asymptotically almost surely (a.a.s.), any CA-component has size at most $k$.
Moreover, the random variables $(N_{\ell})_{\ell=2}^{k}$ which count the
number of CA-components of size $2,\ldots,k$, respectively, jointly converge
in distribution to independent Poisson random variables.

  * •

We start investigating the more difficult intermediate regime (that is, when
$\lambda_{k}^{*}>1>\lambda_{1}^{*}$). In this setting, we show a weak law of
large numbers under the assumption that $\lambda_{k}^{*}>1>\lambda_{k-1}^{*}$.

These results are summarized in the following theorem.

######  Theorem 1.1.

Suppose that $k\geq 2$.

  1. (i)

There exists $a_{1}\in[0,1)$, such that

$\frac{\max_{u\in[n]}|\widetilde{\mathcal{C}}(u)|}{n}\xrightarrow[n\to\infty]{\mathbb{P}}a_{1}.$

Moreover, one has $a_{1}>0$ if and only if $\lambda_{1}^{*}>1$.

  2. (ii)

If $\lambda_{k}^{*}>1>\lambda_{k-1}^{*}$, then there is a positive constant
$a_{2}$ such that

$\frac{\max_{u\in[n]}|\widetilde{\mathcal{C}}(u)|}{\log
n}\xrightarrow[n\to\infty]{\mathbb{P}}a_{2}.$

  3. (iii)

If $\lambda_{k}^{*}<1$, then a.a.s.
$\max_{u\in[n]}|\widetilde{\mathcal{C}}(u)|\leq k$. Moreover, there are
positive constants $\beta_{2},\ldots,\beta_{k}$, such that

$(N_{2},\ldots,N_{k})\xrightarrow[n\to\infty]{d}\bigotimes_{\ell=2}^{k}\mathrm{Po}(\beta_{\ell}),$

that is, the random variables $(N_{\ell})_{\ell=2}^{k}$ jointly converge in
distribution to $k-1$ independent Poisson variables with means
$\beta_{2},\ldots,\beta_{k}$ as $n\to\infty$.

Note that in the above result, we recover an analog of the famous transition
from a linear to a logarithmic size for the largest connected component, which
appears in an ER random graph $G(n,\tfrac{\lambda}{n})$ as the parameter
$\lambda$ crosses the critical value $1$. However, unlike this standard
setting, one original feature of CA-percolation is that there is an additional
regime where the size of the largest CA-component remains bounded.
Furthermore, the critical cases $\lambda_{1}^{*}=1$ and $\lambda_{k}^{*}=1$
appear to be more subtle, see Proposition 1.3 below and Section 4 for more on
this.

Now, we take a closer look at each of the three parts of Theorem 1.1. Part (i)
should not be very surprising as, on the one hand, if $\lambda_{1}^{*}\leq 1$,
then a.a.s. the largest connected component in $G^{1}$ has sublinear size, and
thus the largest CA-component as well. On the other hand, if
$\lambda_{1}^{*}>1$, then a.a.s. the largest CA-component is obtained by
intersecting the largest connected components in each of the graphs
$G^{1},\dots,G^{k}$, which all have linear size. However, we stress that the
whole point of the proof is to handle the lack of independence between these
components. To do this, we use a local limit argument for a sequence of
randomly colored ER random graphs, which also allows us to recover and improve
in a simple way a result of [10] on the number of CA-components of given size.

######  Proposition 1.2.

There exists a sequence of non-negative real numbers $(\nu_{\ell})_{\ell\geq
1}$ such that $\sum_{\ell\geq 1}\nu_{\ell}=1-a_{1}$, and for each $\ell\geq
1$,

$\frac{|\\{u\in[n]:|\widetilde{\mathcal{C}}(u)|=\ell\\}|}{n}=\frac{\ell\cdot
N_{\ell}}{n}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{\nu}_{\ell}.$ (3)

Moreover, one has $\nu_{\ell}>0$ for all $\ell\geq 1$ if and only if
$\lambda_{k}^{*}>1$, while if $\lambda_{k}^{*}\leq 1$, then $\nu_{1}=1$.

Altogether, this proposition and Part (i) of Theorem 1.1 answer a question
from [10] by showing that one can get rid of their technical assumption.

For Part (ii) of Theorem 1.1, the main observation is that the largest CA-
component comes from intersecting a connected component in $G_{k}$ with the
largest component of $G^{k}$. In fact this argument also gives us that the
size of the largest CA-component in the critical case
$\lambda_{k}^{*}=1>\lambda_{k-1}^{*}$ is tight.

######  Proposition 1.3.

Suppose that $\lambda_{k}^{*}=1>\lambda_{k-1}^{*}$. Then,

$\sup_{n\geq 1}\
\mathbb{P}\Big{(}\max_{u\in[n]}|\widetilde{\mathcal{C}}(u)|\geq
M\Big{)}\xrightarrow[M\to\infty]{}0.$

The question of whether in this critical case the size of the largest CA-
component converges in distribution remains open. In fact, even knowing if the
support is asymptotically bounded by a deterministic constant is unknown.

In the remaining intermediate regime, i.e. when $\lambda_{k-1}^{*}\geq
1>\lambda_{1}^{*}$, one can easily show that the size of the largest CA-
component is still of logarithmic order. However, proving concentration seems
to be a challenging problem, which remains out of reach with our present
techniques.

Part (iii), as we already mentioned, is arguably the most original part. In
this case, the largest connected component in each of the graphs
$G^{1},\dots,G^{k}$ has only logarithmic size, which makes it very difficult
for a pair of vertices to be connected in all $k$ graphs. This explains, at
least heuristically, why the largest CA-component has bounded size, although
the fact that the bound is deterministic may appear as unexpected. Actually,
as we shall see, the main reason for which the upper bound is given by the
number of colors is that a.a.s. every CA-component is either contained in a
single edge, or all paths connecting two of its vertices and avoiding some
color are contained in a single cycle.

Finally, we provide an explicit expression of $\beta_{k}$ in terms of
$\lambda_{1},\ldots,\lambda_{k}$ in Remark 3.7. While it is possible to do the
same for the other values of $\beta_{m}$ for $m<k$, the formula and the
computation tend to get more and more tedious as $m$ decreases.

We now comment on the proofs themselves in more detail.

#### Outline of the proofs.

As already mentioned, the proofs of Part (i) of Theorem 1.1 and Proposition
1.2 are based on the well-known local convergence of Erdős-Renyi random graphs
to Bienaymé-Galton-Watson trees, or BGW trees for short, with Poisson
offspring distribution. In our setting of edge-colored ER random graph, the
local limit can be seen as a BGW tree with $\text{Po}(\Lambda)$ offspring
distribution where additionally each edge is colored with color $i\in[k]$ with
probability $\lambda_{i}/\Lambda$, independently for different edges. Then,
the constant $a_{1}$ is just the probability that for every $i\in[k]$, the
connected component of the root is infinite when we erase the edges colored
with color $i$. The same approach allows to prove Proposition 1.2, with
$(\nu_{\ell})_{\ell\geq 1}$ being the probability distribution of the size of
the CA-component of the root in the aforementioned BGW tree. However, here the
notion of CA-component must be suitably adjusted, as already noticed in [10]:
for each $i\in[k]$, two vertices are declared to be connected when erasing
color $i$ if either they are indeed connected by a path in the BGW tree that
avoids color $i$, or if they both connect to infinity by paths avoiding color
$i$. It is then not difficult to see that, for this notion of CA-connectivity,
the constant $a_{1}$ is also the probability that the CA-component of the root
is infinite.

On the other hand, the proofs of (ii), Proposition 1.3 and (iii) have a
different flavor. Firstly, we outline the proof strategy for (ii). To begin
with, we make use of the following fact, which might be of independent
interest. Consider a subcritical Erdős-Renyi random graph
$G(n,\tfrac{\lambda}{n})$, and independently color each of its vertices in
black with some probability $q\in(0,1]$. Then, we show that the maximal number
of black vertices which are all connected in $G(n,\tfrac{\lambda}{n})$ divided
by $\log n$ converges in probability towards a positive constant. This result
extends the concentration for the size of the largest component in a
subcritical ER random graph, which corresponds to $q=1$. The proof is obtained
by solving an energy-entropy optimization problem, where the energy
corresponds to the cost of having a large number of black vertices in a given
connected component of $G(n,\tfrac{\lambda}{n})$, while the entropy factor
comes from the fact that as $b$ decreases, the number of connected components
of size $b\log n$ in $G(n,\tfrac{\lambda}{n})$ increases. The link with (ii)
arises as one realizes (the nontrivial fact) that when $\lambda_{k-1}^{*}<1$,
the largest CA-component necessarily comes from intersecting a component in
$G_{k}$ (which is subcritical) with the largest component of $G^{k}$ (which is
supercritical), the two being independent, and the fact that the vertex set of
the giant component in the latter can be approximated by a binomial random
subset of vertices. A similar argument also leads to a proof of Proposition
1.3. We refer to Sections 2.3, 2.4, and 3.2 for more details.

Concerning (iii), the crux of the proof is to show that when
$\lambda_{k}^{*}<1$, a.a.s. every CA-component of size at least two is
contained either in a cycle of $G$ or in a single edge (the latter happening
only if the CA-component has exactly two vertices which are linked by an edge
in at least two different colors), see Lemma 3.4. The proof of this result
relies on a combination of some counting arguments (e.g. showing that a.a.s.
connected subgraphs of $G(n,\lambda/n)$ of size at most some constant times
$\log n$ contain at most one cycle, see Lemma 2.5), and a more probabilistic
lemma showing that a.a.s. all CA-components have bounded size (see in
particular Lemma 3.2). Once this is established, (iii) follows from standard
results on the asymptotic numbers of short cycles in an Erdős-Renyi random
graph.

######  Remark 1.4.

Note that the notion of CA-component of a vertex $u$ is usually defined as the
set of vertices connected to $u$ when deleting edges of color $i$ for any
$i\in[k]$ (that is, unlike in our setting, edges in color $i$ cannot be used
even if they have more than one color). While all our results would also hold
with this definition, ours is slightly more convenient to deal with,
especially in the intermediate regime, since this way $G_{i}$ and $G^{i}$ are
independent.

#### Further notation and terminology.

In general, we omit the dependence on $n$, $\Lambda$ and
$(\lambda_{i})_{i\in[k]}$ for convenience of notation.

For $I\subseteq[k]$ and a vertex $u\in[n]$, we denote by $\mathcal{C}_{I}(u)$
and $\mathcal{C}^{I}(u)$ the connected components of $u$ in $G_{I}$ and
$G^{I}$, respectively. An edge is said to be _repeated_ if it participates in
at least two of $G_{1},\ldots,G_{k}$.

In this paper, we often identify graphs with their vertex sets. For instance,
given a graph $H$, we call _size_ of $H$ its number of vertices, which we
denote by $|H|$. For a set $S$ of vertices of $H$, we denote by $H[S]$ the
subgraph of $H$ induced by $S$ (that is, the graph with vertex set $S$ and
edge set given by the edges of $H$ with both vertices in $S$). Moreover, for
two vertices $u,v$ in $H$, we denote by $\\{u\xleftrightarrow{H\,}v\\}$ the
event that $u$ and $v$ are connected in $H$.

A sequence of events $(\mathcal{E}_{n})_{n\geq 1}$ is said to hold a.a.s. if
$\mathbb{P}(\mathcal{E}_{n})\to 1$ as $n\to\infty$. Given two positive real
sequences $(f_{n})_{n\geq 1}$ and $(g_{n})_{n\geq 1}$, we write
$f_{n}=o(g_{n})$ if $f_{n}/g_{n}\to 0$ when $n\to\infty$, and
$f_{n}=\mathcal{O}(g_{n})$ if there exists a constant $C>0$ such that
$f_{n}\leq Cg_{n}$ for all $n\geq 1$. Furthermore, we write $\xrightarrow{d}$
to denote convergence in distribution of a sequence of random variables, and
$\xrightarrow{\mathbb{P}}$ for convergence in probability.

Finally, we denote by $\mathrm{Po}(\lambda)$ the Poisson distribution with
parameter $\lambda$, and by $\text{Bin}(n,q)$ the Binomial distribution with
parameters $n$ and $q$. For a family of distributions $(\mu_{i})_{i\in I}$, we
denote by $\bigotimes_{i\in I}\mu_{i}$ the distribution of a vector
$(X_{i})_{i\in I}$ of independent random variables where $X_{i}\sim\mu_{i}$
for every $i\in I$.

#### Plan of the paper.

The rest of the paper is organized as follows. In the next section, we recall
some known facts about ER random graphs, both in the subcritical and
supercritical regimes, and show the result on the size of the largest black
connected set in a (vertex-)colored subcritical ER random graph which was
mentioned above. Then, in Section 3 we give the proof of our main results,
Theorem 1.1 and Propositions 1.2 and 1.3, and finally discuss some open
questions in Section 4.

##  2 Preliminaries on Erdős-Rényi random graphs

In this section, we gather some results on the random graph
$G(n,\tfrac{\lambda}{n})$. Apart from the results in Section 2.4, most of the
material presented here is well-known, and we sometimes include short proofs
only for the reader’s convenience.

We let $\mathcal{C}(u)$ denote the connected component of a vertex $u\in[n]$.
Also, for $\lambda>0$, set

$I_{\lambda}=\lambda-1-\log\lambda.$ (4)

It is easy to check that this is a positive real number for all $\lambda>0$
different from 1. Also, for every integer $s\geq 0$, we define

$Z_{s}=\sum_{u\in[n]}\mathds{1}_{\\{|\mathcal{C}(u)|\,\geq\,s\\}}.$

###  2.1 Subcritical regime: cluster size and two-point connectivity

Fix $\lambda\in(0,1)$. Then, it is well-known that

$\frac{\max_{u\in[n]}|\mathcal{C}(u)|}{\log
n}\xrightarrow[n\to\infty]{\mathbb{P}}\frac{1}{I_{\lambda}},$ (5)

see e.g. Theorems 4.4 and 4.5 in [11]. It will also be useful to have a bound
on the upper tail of the typical cluster size. The following one will be
sufficient for our purposes.

######  Lemma 2.1 (see display (4.3.11) in [11]).

Fix $\lambda\in(0,1)$. Then, for every $t\geq 1$,

$\mathbb{P}(|\mathcal{C}(u)|\geq t)\leq\mathrm{e}^{-I_{\lambda}\cdot\,t}.$

A reverse inequality holds as well when $t$ does not grow too fast with $n$.
In particular, we shall need the following result (see e.g. displays (4.3.34)
and (4.3.37) in [11]).

######  Lemma 2.2.

Fix $\lambda\in(0,1)$ and $a\in(0,1/I_{\lambda}]$. Then,

$\mathbb{P}(|\mathcal{C}(u)|\geq a\log n)\geq
n^{-(1+o(1))I_{\lambda}\cdot\,a}.$

Moreover, Lemma 2.1 has the following important consequence.

######  Corollary 2.3.

Fix $\lambda\in(0,1)$. Then, for every pair of distinct vertices $u,v$ in
$G(n,\frac{\lambda}{n})$,

$\mathbb{P}(v\in\mathcal{C}(u))\leq\frac{1}{n}\cdot\frac{\mathrm{e}^{-I_{\lambda}}}{1-\mathrm{e}^{-I_{\lambda}}}.$

###### Proof.

It suffices to observe that for every $t\geq 1$, conditionally on the event
$\\{|\mathcal{C}(u)|=t\\}$, the set of vertices different from $u$ and
contained in $\mathcal{C}(u)$ is uniformly distributed among all possible
subsets of $[n]\setminus\\{u\\}$ of size $t-1$. In particular, for every
$v\neq u$,

$\mathbb{P}(v\in\mathcal{C}(u)\mid|\mathcal{C}(u)|=t)=\frac{t-1}{n-1}\leq\frac{t}{n}.$
(6)

By summing over all positive integers $t\in[n]$ and using Lemma 2.1, we get

$\mathbb{P}(v\in\mathcal{C}(u))\leq\sum_{t=1}^{n}\frac{t}{n}\cdot\mathbb{P}(|\mathcal{C}(u)|=t)=\frac{1}{n}\sum_{t=1}^{n}\mathbb{P}(|\mathcal{C}(u)|\geq
t)\leq\frac{1}{n}\cdot\frac{e^{-I_{\lambda}}}{1-e^{-I_{\lambda}}},$

as desired. ∎

The next result provides concentration of the variables $Z_{s}$ when $s$ is of
order $\log n$. The equality for the expectation is a direct consequence of
Lemmas 2.1 and 2.2, while the two inequalities for the variance follow from
Proposition 4.7 in [11] and Lemma 2.1, respectively.

######  Lemma 2.4.

Let $\lambda\in(0,1)$ and $a\in(0,1/I_{\lambda}]$. Then,

$\mathbb{E}[Z_{a\log
n}]=n^{1-(1+o(1))I_{\lambda}\cdot\,a}\quad\text{and}\quad\mathrm{Var}[Z_{a\log
n}]\leq
n\cdot\mathbb{E}\big{[}|\mathcal{C}(1)|\mathds{1}_{\\{|\mathcal{C}(1)|\,\geq\,a\log
n\\}}\big{]}\leq n^{1-(1+o(1))I_{\lambda}\cdot\,a}.$

###  2.2 On the number of cycles

We start with a result showing that a.a.s. all connected subgraphs of
$G(n,\tfrac{\lambda}{n})$ of size at most some constant (depending on
$\lambda$) times $\log n$ contain at most one cycle, and when $\lambda<1$, all
those with size at least $\varepsilon\log n$ are trees for any fixed
$\varepsilon>0$.

######  Lemma 2.5.

Fix $\lambda>0$.

  1. 1.

There is a positive constant $c_{1}=c_{1}(\lambda)$ such that a.a.s. the
following holds: for every set $S\subseteq[n]$ with $|S|\leq c_{1}\log n$,
whenever the subgraph of $G(n,\tfrac{\lambda}{n})$ induced by $S$ is
connected, it contains at most one cycle.

  2. 2.

If $\lambda<1$, then for every $\varepsilon>0$, a.a.s. all components of size
larger than $\varepsilon\log n$ are trees.

######  Remark 2.6.

In fact, concerning the second statement of this lemma, more is true: as shown
in the proof below, the expected number of vertices whose connected component
contains at least one cycle is bounded uniformly in $n$.

###### Proof of Lemma 2.5.

Concerning the first part of the lemma, note that any connected graph with at
least two cycles contains as a subgraph a spanning tree together with two
additional edges. Furthermore, by Cayley’s formula the number of spanning
trees of the complete graph with size $m$ is equal to $m^{m-2}$. Therefore,
for every $c>0$, by using that
$\tbinom{n}{m}\leq\left(\tfrac{n\mathrm{e}}{m}\right)^{m}$, we deduce that the
expected number of subgraphs of $G(n,\tfrac{\lambda}{n})$ which are connected,
contain at least two cycles and at most $c\log n$ vertices, is bounded from
above by,

$\sum_{m=1}^{\lfloor c\log
n\rfloor}m^{m-2}\cdot\binom{m}{2}^{2}\cdot\binom{n}{m}\cdot\left(\frac{\lambda}{n}\right)^{m+1}\leq\frac{1}{n}\sum_{m=1}^{\lfloor
c\log n\rfloor}m^{2}(\mathrm{e}\lambda)^{m+1},$

which is $o(1)$ if one chooses $c<\frac{1}{1+\max(0,\log\lambda)}$. The proof
of the first part is completed by an application of Markov’s inequality.

For the second part, we compute the expected number of vertices in components
of size at most $2I_{\lambda}^{-1}\log n$ containing a cycle. Taking also into
account the fact that no vertex in a component of size $m$ is connected to any
of the $n-m$ vertices outside the component, the previous computation implies
that the above expectation is at most

$\sum_{m=1}^{2I_{\lambda}^{-1}\log n}m\cdot
m^{m-2}\cdot\binom{m}{2}\cdot\binom{n}{m}\cdot\left(\frac{\lambda}{n}\right)^{m}\left(1-\frac{\lambda}{n}\right)^{m(n-m)}\leq(1+o(1))\sum_{m=1}^{2I_{\lambda}^{-1}\log
n}m\cdot\mathrm{e}^{-I_{\lambda}m}=\mathcal{O}(1).$

Thus, by Markov’s inequality there are a.a.s. less than $\varepsilon\log n$
vertices in components of size at most $2I_{\lambda}^{-1}\log n$ containing a
cycle. However, by Lemma 2.1 a.a.s. all components have size at most
$2I_{\lambda}^{-1}\log n$, which completes the proof. ∎

######  Remark 2.7.

The following modification of Lemma 2.5 holds with almost the same proof.

  1. 1.

There exists $c_{1}=c_{1}(\Lambda)$ such that a.a.s. for every set
$S\subseteq[n]$ with $|S|\leq c_{1}\log n$, whenever the subgraph of $G$
induced by $S$ is connected, it either contains at most one cycle and no
repeated edges or at most one repeated edge and no cycles.

  2. 2.

If $\lambda_{i}^{*}<1$ for some $i$, then for every $\varepsilon>0$, a.a.s.
all connected components of $G^{i}$ of size at least $\varepsilon\log n$ are
trees with no repeated edges.

The next lemma is a well-known result concerning the number of cycles of given
size that will be needed for the proof of Theorem 1.1 (iii). We refer e.g. to
Corollary 4.9 from [1] for a proof.

######  Lemma 2.8 ([1], Corollary 4.9).

Fix $\lambda>0$. For $m\geq 3$, denote by $C_{m}$ the number of cycles of
length $m$ in the graph $G(n,p)$ with $p=(1+o(1))\tfrac{\lambda}{n}$. Then,
for any fixed $\ell\geq 3$,

$(C_{3},\ldots,C_{\ell})\xrightarrow[n\to\infty]{d}\bigotimes_{m=3}^{\ell}\mathrm{Po}(\gamma_{m}),$

where for all $m\in\\{3,\dots,\ell\\}$, $\gamma_{m}=\tfrac{\lambda^{m}}{2m}$.

Lemma 2.8 has the following direct consequence. Recall that an edge is said to
be repeated in $G$ if it is part of at least two of the graphs
$G_{1},\dots,G_{k}$.

######  Corollary 2.9.

Denote by $C_{2}$ the number of repeated edges in $G$. Then, with the same
notation as in Lemma 2.8, for every $\ell\geq 2$,

$(C_{2},\ldots,C_{\ell})\xrightarrow[n\to\infty]{d}\bigotimes_{m=2}^{\ell}\mathrm{Po}(\gamma_{m}),$

where $\gamma_{2}=\tfrac{1}{2}\sum_{i,j\in[k],i<j}\lambda_{i}\lambda_{j}$ and
for all $m\in\\{3,\dots,\ell\\}$, $\gamma_{m}=\tfrac{\Lambda^{m}}{2m}$.

###### Proof.

Using that $G$ is distributed as an Erdős-Rényi random graph with parameters
$n$ and

$p=1-\prod_{i=1}^{k}\left(1-\frac{\lambda_{i}}{n}\right)=(1+o(1))\cdot\frac{\Lambda}{n},$

the joint convergence of $(C_{3},\ldots,C_{\ell})$ is given by Lemma 2.8.

On the other hand, by definition
$C_{2}\sim\text{Bin}(\tfrac{n(n-1)}{2},\tfrac{2(1+o(1))\gamma_{2}}{n^{2}})$,
and thus $C_{2}$ converges in distribution to $\text{Po}(\gamma_{2})$. It only
remains to justify the asymptotic independence between $C_{2}$ and the other
variables. The argument is the same as the one showing asymptotic independence
of $C_{3},\dots,C_{\ell}$, see Theorem 4.8 and Corollary 4.9 in [1]. Briefly,
one can first notice by a simple first moment argument that a.a.s. no vertex
participates simultaneously in a repeated edge and in a cycle of length at
most $\ell$. Thus, the variables $(C_{3},\dots,C_{\ell})$ a.a.s. coincide with
the cycle counts in the graph, obtained by deleting all vertices in repeated
edges, which conditionally on $C_{2}$ is an ER random graph with at least
$n-2C_{2}$ vertices. Using that $\mathbb{E}[C_{2}]=\mathcal{O}(1)$, and more
precisely that a.a.s. $n-2C_{2}=n-o(n)$, implies the corollary. ∎

###  2.3 Supercritical regime: stochastic domination of the giant component

Recall that when $\lambda>1$, the graph $G(n,\tfrac{\lambda}{n})$ has a.a.s. a
unique connected component of linear size (called the _giant_ component). More
precisely, it is well-known that

$\frac{\max_{u\in[n]}|\mathcal{C}(u)|}{n}\xrightarrow[n\to\infty]{\mathbb{P}}\mu_{\lambda}$
(7)

where $\mu_{\lambda}$ is the survival probability of a Bienaymé-Galton-Watson
tree with offspring distribution $\mathrm{Po}(\lambda)$ characterized as the
unique positive solution of the equation $1=e^{-\lambda t}+t$, see display
(3.6.2) and Theorem 4.8 in [11]. Recall also that conditionally on its size,
the set of vertices in the giant component is uniformly distributed among the
family of subsets of $[n]$ of that size. As a consequence, one has the
following stochastic comparison with binomial random subsets of vertices.

######  Lemma 2.10.

Fix $\lambda>1$ and $\varepsilon>0$. Let $\mathcal{C}_{\max}$ be the a.a.s.
unique largest connected component of $G(n,\tfrac{\lambda}{n})$. Let also
$(X_{v})_{v\in[n]}$ and $(Y_{v})_{v\in[n]}$ be two sequences of i.i.d.
Bernoulli random variables with respective parameters
$\max(\mu_{\lambda}-\varepsilon,0)$ and $\min(\mu_{\lambda}+\varepsilon,1)$.
Then, there is a coupling of these two sequences with
$G(n,\tfrac{\lambda}{n})$ such that a.a.s. one has

$\\{v:X_{v}=1\\}\subseteq\mathcal{C}_{\max}\subseteq\\{v:Y_{v}=1\\}.$ (8)

###### Proof.

Note that conditionally on their respective sizes, the three sets appearing in
(8) are sampled uniformly at random among all subsets of $[n]$ of that size.
The lemma then follows by the weak law of large numbers and (7), which
together imply that a.a.s.

$\sum_{v\in[n]}X_{v}\leq|\mathcal{C}_{\max}|\leq\sum_{v\in[n]}Y_{v}.$

∎

###  2.4 On the intersection of a giant with independent subcritical clusters

Fix $q\in(0,1)$ and $\lambda\in(0,1)$. For every $x\in[q,1)$, define

$J_{q}(x)=x\log\frac{x}{q}+(1-x)\log\frac{1-x}{1-q},\quad\text{and
set}\quad\rho(q,\lambda)=\inf_{x\in[q,1)}\frac{I_{\lambda}+J_{q}(x)}{x}.$

Consider a sequence $(X_{v})_{v\in[n]}$ of independent Bernoulli random
variables with parameter $q$, and independently a graph
$G(n,\tfrac{\lambda}{n})$. For $u\in[n]$ and $t\geq 0$, define

$\widetilde{Z}_{t}=\sum_{u\in[n]}\mathds{1}_{\\{\sum_{v\in\mathcal{C}(u)}X_{v}\,\geq\,t\\}}.$

The next lemma is similar in essence to Lemma 2.4.

######  Lemma 2.11.

Fix $a\in(0,\tfrac{1}{\rho(q,\lambda)}]$. Then,

$\mathbb{E}[\widetilde{Z}_{a\log
n}]=n^{1-(1+o(1))\rho(q,\lambda)\,\cdot\,a}\quad\text{and}\quad\mathrm{Var}[\widetilde{Z}_{a\log
n}]\leq n^{1-(1+o(1))\rho(q,\lambda)\,\cdot\,a}.$

###### Proof.

We begin by proving the estimate on the mean. To start with, we recall two
large deviation estimates for Binomial random variables. On the one hand, for
every $x\in[q,1)$ and every $N\geq 1$ (see e.g. Corollary 2.20 in [11]),

$\mathbb{P}(\text{Bin}(N,q)\geq xN)\leq\exp\big{(}-N\cdot J_{q}(x)\big{)},$
(9)

and on the other hand, for every fixed $x\in[q,1)$ (see e.g. Theorem 2.2.3 and
Exercice 2.2.23 in [3]),

$\mathbb{P}(\text{Bin}(N,q)\geq xN)\geq\exp\big{(}-(1+o_{N}(1))\cdot N\cdot
J_{q}(x)\big{)},$ (10)

where the $o_{N}(1)$ term goes to $0$ as $N\to\infty$. Since conditionally on
its size the cluster $\mathcal{C}(1)$ is uniformly distributed among the
subsets of $[n]$ of that size containing the vertex 1, we deduce using (9) and
Lemma 2.1 that

$\begin{split}\mathbb{P}\Big{(}\sum_{v\in\mathcal{C}(1)}X_{v}\geq a\log
n\Big{)}&\leq\sum_{s=a\log n}^{(a/q)\log
n}\mathbb{P}(|\mathcal{C}(1)|=s)\cdot\mathbb{P}(\text{Bin}(s,q)\geq a\log
n)+\mathbb{P}(|\mathcal{C}(1)|\geq(a/q)\cdot\log n)\\\ &\leq\sum_{s=a\log
n}^{(a/q)\log n}\exp\left(-\left(I_{\lambda}+J_{q}\left(\frac{a\log
n}{s}\right)\right)\cdot s\right)+n^{-I_{\lambda}\cdot\,a/q}\\\
&\leq\mathcal{O}(\log n)\cdot
n^{-\inf_{b\in(a,a/q]}b(I_{\lambda}+J_{q}(a/b))},\end{split}$ (11)

and observing that

$\inf_{b\in(a,a/q]}b(I_{\lambda}+J_{q}(a/b))=a\cdot\rho(q,\lambda),$ (12)

concludes the proof of the upper bound.

Now, we concentrate on the lower bound. To start with, we extend $J_{q}$ to a
continuous function on the interval $[q,1]$ by defining $J_{q}(1)=\log(1/q)$,
and let $b_{*}$ be the smallest real number realizing the infimum of the
function $b\mapsto b(I_{\lambda}+J_{q}(a/b))$ over the interval $[a,a/q]$.
Recall that $\log$ is a concave function, so by Jensen’s inequality the
function $J_{q}$ is non-negative. Then, together with the fact that $a\leq
1/\rho(q,\lambda)$ by hypothesis, (12) shows that

$b_{*}=\frac{a\cdot\rho(q,\lambda)}{I_{\lambda}+J_{q}(a/b_{*})}\leq\frac{a\cdot\rho(q,\lambda)}{I_{\lambda}}\leq\frac{1}{I_{\lambda}}.$

Thus, by using Lemma 2.2 and (10), we get

$\displaystyle\mathbb{P}\Big{(}\sum_{v\in\mathcal{C}(1)}X_{v}\geq a\log
n\Big{)}$ $\displaystyle\geq\;\mathbb{P}(|\mathcal{C}(1)|\geq b_{*}\log
n)\cdot\mathbb{P}(\text{Bin}(b_{*}\log n,q)\geq a\log n)$
$\displaystyle\geq\;n^{-(1+o(1))b_{*}\cdot I_{\lambda}}\cdot
n^{-(1+o(1))b_{*}\cdot
J_{q}(a/b_{*})}=n^{-(1+o(1))a\,\cdot\,\rho(q,\lambda)},$

which concludes the proof of the lower bound.

Finally, the proof of the upper bound on the variance is mutatis mutandis the
same as the proof of Lemma 2.4, in particular, the same argument leads to

$\text{Var}[\widetilde{Z}_{a\log n}]\leq
n\cdot\mathbb{E}\left[\left(\sum_{v\in\mathcal{C}(1)}X_{v}\right)\cdot\mathds{1}_{\\{\sum_{v\in\mathcal{C}(1)}X_{v}\,\geq\,a\log
n\\}}\right],$

which combined with (11) yields the desired upper bound. ∎

######  Remark 2.12.

A close look at the previous proof shows that the upper bound on the mean is
in fact valid for all $a>0$.

######  Corollary 2.13.

Let $a=a(q,\lambda)=\frac{1}{\rho(q,\lambda)}>0$. Then,

$\frac{\max_{u\in[n]}\sum_{v\in\mathcal{C}(u)}X_{v}}{\log
n}\xrightarrow[n\to\infty]{\mathbb{P}}a.$

###### Proof.

If $h>a(q,\lambda)$, then by Markov’s inequality and Lemma 2.11 (see also
Remark 2.12) we get

$\mathbb{P}\left(\max_{u\in[n]}\sum_{v\in\mathcal{C}(u)}X_{v}\geq h\log
n\right)=\mathbb{P}(\widetilde{Z}_{h\log n}\geq
1)\leq\mathbb{E}[\widetilde{Z}_{h\log n}]=o(1).$

Conversely, if $h<a(q,\lambda)$, then again Lemma 2.11 together with the
Cauchy-Schwarz inequality gives

$\mathbb{P}\left(\max_{u\in[n]}\sum_{v\in\mathcal{C}(u)}X_{v}\geq h\log
n\right)=\mathbb{P}(\widetilde{Z}_{h\log n}\geq
1)\geq\frac{\mathbb{E}[\widetilde{Z}_{h\log
n}]^{2}}{\mathbb{E}[\widetilde{Z}_{h\log
n}]^{2}+\text{Var}[\widetilde{Z}_{h\log n}]}=1-o(1).$

∎

##  3 Proofs of the main results

This section is devoted to the proofs of Theorem 1.1 and Proposition 1.2. We
first prove Part (i) of the theorem together with the proposition in Section
3.1, then Part (ii) of the theorem in Section 3.2, and finally Part (iii) in
Section 3.3.

###  3.1 Proofs of Theorem 1.1 (i) and Proposition 1.2

The proofs of these two results are based on the well-known local convergence
of ER random graphs to BGW trees with Poisson offspring distribution. Recall
that in the standard setting of uncolored graphs, the local _weak_ convergence
states the following: denoting by $\mathcal{V}_{L}(u)$ the $L$-neighborhood of
a vertex $u$ in $G$ (as defined in (1)) or in the BGW tree with
$\text{Po}(\Lambda)$ offspring distribution, for every bounded function
$(u,H)\mapsto\varphi(u,H)$ defined on pairs $(u,H)$ where $H$ is a finite
graph and $u$ a vertex of $H$, one has

$\frac{1}{n}\sum_{u\in[n]}\mathbb{E}[\varphi(u,\mathcal{V}_{L}(u))]\xrightarrow[n\to\infty]{}\mathbb{E}[\varphi(\varnothing,\mathcal{V}_{L}(\varnothing))],$

see e.g. Theorem 6 in [2]. It is straightforward to see that the same
convergence holds in our setting of colored graphs. The difference is that
now, edges are endowed with a label encoding its set of colors. As a
consequence, the limiting graph is a BGW tree with $\text{Po}(\Lambda)$
offspring distribution, denoted hereafter by $\textbf{GW}(\Lambda)$, where
each edge is colored in a single color and independently of other edges, and
where color $i$ is attributed with probability $\lambda_{i}/\Lambda$ (see the
proof of Proposition 3.1 below).

Moreover, using that finite neighborhoods of two given points are mostly
independent (in particular, they are unlikely to intersect), it is possible to
strengthen the previous convergence in expectation into a convergence in
probability, see e.g. [12, Theorem 2.19] in the case of uncolored graphs. In
our case, we obtain the following result, which is our main tool for proving
Theorem 1.1 (i) and Proposition 1.2. Although the proof is standard, we
briefly sketch the argument for reader’s convenience. A similar result is
derived in the proof of Proposition 4.1.7 in [10].

######  Proposition 3.1.

Let $\varphi$ be a bounded function on the set of finite rooted graphs whose
edges are endowed with a label encoding its set of colors. Then, for any
$L\geq 1$,

$\frac{1}{n}\sum_{u\in[n]}\varphi(u,\mathcal{V}_{L}(u))\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{E}[\varphi(\varnothing,\mathcal{V}_{L}(\varnothing))],$
(13)

where $\mathcal{V}_{L}(\varnothing)$ is the $L$-neighborhood of the root
$\varnothing$ in the colored graph $\emph{{GW}}(\Lambda)$ defined above.

###### Proof.

As already mentioned, the convergence in expectation is a straightforward
consequence of the well-known local weak convergence of $G$. Note that
conditionally on being present in $G$, an edge has color $i$ with probability

$\frac{\lambda_{i}/n}{1-\prod_{j=1}^{k}(1-\lambda_{j}/n)}=(1+o(1))\frac{\lambda_{i}}{\Lambda}.$

In particular, since $(\lambda_{i}/\Lambda)_{i=1}^{k}$ sum up to 1, a.s. every
edge in the limit has only one color.

To prove convergence in probability, we use Chebyshev’s inequality and bound
the variance of the random variable appearing on the left-hand side of (13).
Assume without loss of generality that $\varphi$ is non-negative and bounded
by one. Then, on the one hand, for every $u\in[n]$ and every fixed $L\geq 1$,

$\displaystyle\sum_{v\in[n]}\mathbb{E}[\varphi(u,\mathcal{V}_{L}(u))$
$\displaystyle\varphi(v,\mathcal{V}_{L}(v))\cdot\mathds{1}_{\\{v\in\mathcal{V}_{2L}(u)\\}}]\leq\mathbb{E}[|\mathcal{V}_{2L}(u)|]\leq
1+\dots+\Lambda^{2L}=\mathcal{O}(1).$ (14)

On the other hand, conditionally on the event that
$v\notin\mathcal{V}_{2L}(u)$, or equivalently that
$\mathcal{V}_{L}(u)\cap\mathcal{V}_{L}(v)=\emptyset$, and
$|\mathcal{V}_{L}(u)|=m$ for some $m\geq 1$, $\mathcal{V}_{L}(v)$ is
distributed as the $L$-neighborhood of $v$ in a colored ER random graph with
$n-m$ vertices and parameter $1-\prod_{i=1}^{k}(1-\tfrac{\lambda_{i}}{n})$,
denoted hereafter by $G_{n-m}^{\prime}$. Thus, denoting also by
$\mathbb{E}_{n-m}$ the expectation with respect to the distribution of
$G_{n-m}^{\prime}$, one has

$\displaystyle\mathbb{E}[\varphi(u,\mathcal{V}_{L}(u))\varphi(v,\mathcal{V}_{L}(v))\cdot\mathds{1}_{\\{v\notin\mathcal{V}_{2L}(u)\\}}]$
$\displaystyle=$ $\displaystyle\sum_{m\geq
1}\mathbb{E}\left[\varphi(u,\mathcal{V}_{L}(u))\cdot\mathbb{E}[\varphi(v,\mathcal{V}_{L}(v))\mathds{1}_{\\{\mathcal{V}_{L}(u)\cap\mathcal{V}_{L}(v)=\emptyset\\}}\mid\mathcal{V}_{L}(u)]\cdot\mathds{1}_{\\{|\mathcal{V}_{L}(u)|=m\\}}\right]$
$\displaystyle\leq$ $\displaystyle\sum_{m\geq
1}\mathbb{E}\left[\varphi(u,\mathcal{V}_{L}(u))\cdot\mathds{1}_{\\{|\mathcal{V}_{L}(u)|=m\\}}\right]\cdot\mathbb{E}_{n-m}[\varphi(v,\mathcal{V}_{L}(v))].$

Now, the set $\mathcal{V}_{L}(v)$ on $G_{n-m}^{\prime}$ is the same as on $G$
unless there is at least one edge between one vertex of this set and one of
the $m$ additional vertices which are present in $G$ but not in
$G_{n-m}^{\prime}$. Conditionally on the size of $\mathcal{V}_{L}(v)$ in
$G_{n-m}^{\prime}$, this holds with probability bounded from above by
$m|\mathcal{V}_{L}(v)|\tfrac{\Lambda}{n}$. Therefore,

$\mathbb{E}_{n-m}[\varphi(v,\mathcal{V}_{L}(v))]\leq\mathbb{E}_{n}[\varphi(v,\mathcal{V}_{L}(v))]+2m\mathbb{E}_{n-m}[|\mathcal{V}_{L}(v)|]\cdot\tfrac{\Lambda}{n}=\mathbb{E}_{n}[\varphi(v,\mathcal{V}_{L}(v))]+\mathcal{O}\bigg{(}\frac{m}{n}\bigg{)}.$

As a consequence, using that
$\mathbb{E}[\varphi(u,\mathcal{V}_{L}(u))\cdot|\mathcal{V}_{L}(u)|]\leq\mathbb{E}[|\mathcal{V}_{L}(u)|]$,
which is bounded uniformly in $n$, we get

$\mathbb{E}[\varphi(u,\mathcal{V}_{L}(u))\varphi(v,\mathcal{V}_{L}(v))\cdot\mathds{1}_{\\{v\notin\mathcal{V}_{2L}(u)\\}}]-\mathbb{E}[\varphi(u,\mathcal{V}_{L}(u))]\mathbb{E}[\varphi(v,\mathcal{V}_{L}(v))]=\mathcal{O}\bigg{(}\frac{1}{n}\bigg{)}.$

Together with (14), and summing over all pairs of vertices $u,v\in[n]$, this
gives

$\text{Var}\left(\frac{1}{n}\sum_{u\in[n]}\varphi(u,\mathcal{V}_{L}(u))\right)=\mathcal{O}\bigg{(}\frac{1}{n}\bigg{)},$

proving the desired concentration result. This concludes the (sketch of) proof
of the proposition. ∎

We can now give the proof of our main results.

###### Proof of Theorem 1.1 (i).

Assume first that $\lambda_{1}^{*}\leq 1$. In this case, it is well-known that
the size of the largest connected component of $G^{1}$ divided by $n$
converges in probability to zero, and thus a fortiori the same must hold for
the largest CA-component.

Assume now that $\lambda_{1}^{*}>1$. In this case, a.a.s. each of
$G^{1},\ldots,G^{k}$ contains a unique giant component denoted by
$\mathcal{C}_{\max}^{1},\ldots,\mathcal{C}_{\max}^{k}$, respectively. When
this is not the case for some $i\in[k]$, we define $\mathcal{C}_{\max}^{i}$ to
be an arbitrarily chosen largest component in $G^{i}$. Let also $\mu_{i}$ be
the asymptotic proportion of vertices in $\mathcal{C}_{\max}^{i}$. Since
a.a.s. every non-giant connected component in $G^{1},\ldots,G^{k}$ has size
$\mathcal{O}(\log n)$ (which follows by combining Lemma 2.1 with Theorem 4.15
in [11]), it is sufficient to show that the size of
$\bigcap_{i=1}^{k}\mathcal{C}_{\max}^{i}$ divided by $n$ converges to a
positive constant in probability.

Firstly, note that by (7) one has
$\mu_{i}=\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|=\infty)$, where we keep the
notation $\mathcal{C}^{i}(u)$ for the connected component of a vertex $u$ in
$\textbf{GW}(\Lambda)$ after removal of all edges in color $i$. Thus, for
every $i\in[k]$,

$\frac{|\mathcal{C}^{i}_{\max}|}{n}=\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{u\in\mathcal{C}^{i}_{\max}\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|=\infty).$

On the other hand, for every $L\geq 1$, by Proposition 3.1 one has

$\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|\mathcal{C}^{i}(u)|\,\geq\,L\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|\geq
L),$

since the event of having a connected component of size at least $L$ is a
measurable function of the $L$-neighborhood. Taking the difference between the
terms in the last two displays, we deduce that for every $i\in[k]$ and every
$L\geq 1$,

$\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|\mathcal{C}^{i}(u)|\,\geq\,L\text{
and
}u\notin\mathcal{C}^{i}_{\max}\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}(L\leq|\mathcal{C}^{i}(\varnothing)|<\infty).$
(15)

Since the probability on the right-hand side goes to $0$ as $L\to\infty$, for
every $\varepsilon>0$ one can find $L$ such that for all $i\in[k]$,

$\limsup_{n\to\infty}\
\mathbb{P}\Big{(}\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|\mathcal{C}^{i}(u)|\,\geq\,L\text{
and }u\notin\mathcal{C}^{i}_{\max}\\}}\geq\frac{\varepsilon}{k}\Big{)}=0,$

which by summation over $i$ gives

$\limsup_{n\to\infty}\
\mathbb{P}\Big{(}\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{\exists
i\in[k]:\,|\mathcal{C}^{i}(u)|\,\geq\,L\text{ and
}u\notin\mathcal{C}^{i}_{\max}\\}}\geq\varepsilon\Big{)}=0.$ (16)

Moreover, using Proposition 3.1 again yields

$\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|\mathcal{C}^{i}(u)|\,\geq\,L\text{
for all
}i\in[k]\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|\geq
L\text{ for all }i\in[k]).$

Then, letting $L\to\infty$ together with (16) implies that

$\frac{|\bigcap_{i=1}^{k}\mathcal{C}^{i}_{\max}|}{n}=\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{u\in\mathcal{C}^{i}_{\max}\text{
for all
}i\in[k]\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|=\infty\text{
for all }i\in[k]).$

To conclude the proof of Theorem 1.1 (i), we show that the above limit is
positive. For every $L\geq 1$ and a fixed vertex $u\in[n]$, the events
$\\{|\mathcal{C}^{i}(u)|\geq L\\}$ are increasing, so by the FKG inequality
(see Theorem 3.1 in [4])

$\mathbb{P}(|\mathcal{C}^{i}(u)|\geq L\text{ for all
}i\in[k])\geq\prod_{i=1}^{k}\mathbb{P}(|\mathcal{C}^{i}(u)|\geq L).$

Then, letting $n\to\infty$ and using the local convergence of $G$ towards
$\mathbf{GW}(\Lambda)$ implies that

$\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|\geq L\text{ for all
}i\in[k])\geq\prod_{i=1}^{k}\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|\geq L).$

Finally, letting $L\to\infty$ shows that

$\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|=\infty\text{ for all
}i\in[k])\geq\prod_{i=1}^{k}\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|=\infty)>0,$

as desired. ∎

###### Proof of Proposition 1.2.

Firstly, we recall the notion of CA-connectivity in $\textbf{GW}(\Lambda)$
from [10]. Two vertices $u$ and $v$ are declared to be CA-connected if for
every $i\in[k]$, either $u$ and $v$ are connected in the subgraph of
$\textbf{GW}(\Lambda)$ obtained by removing edges in color $i$, which we
denote by $\textbf{GW}^{i}(\Lambda)$, or if their connected components in this
graph are both infinite. We denote by $\widetilde{\mathcal{C}}(\varnothing)$
the CA-component of the root.

Now, we define $I=\\{i:\lambda_{i}^{*}>1\\}$, and $J=[k]\setminus I$. Then,
for $L\geq 1$, $M\geq 1$, and $u\in[n]$, we define

$\widetilde{\mathcal{C}}_{L,M}(u)=\Big{(}\bigcap_{i\in
J}\Big{\\{}v:u\xleftrightarrow{G^{i}\cap\mathcal{V}_{L}(u)}v\Big{\\}}\Big{)}\cap\Big{(}\bigcap_{i\in
I}\
\Big{\\{}v\in\mathcal{V}_{L}(u):u\xleftrightarrow{G^{i}\cap\mathcal{V}_{L}(u)}v\
\text{or}\ \min(|\mathcal{C}^{i}(u)|,|\mathcal{C}^{i}(v)|)\geq
M\Big{\\}}\Big{)},$

with the notation from the proof of Theorem 1.1 (i), and

$\widetilde{\mathcal{C}}_{L}(u)=\Big{(}\bigcap_{i\in
J}\Big{\\{}v\in\mathcal{V}_{L}(u):u\xleftrightarrow{G^{i}\cap\mathcal{V}_{L}(u)}v\Big{\\}}\Big{)}\cap\Big{(}\bigcap_{i\in
I}\
\Big{\\{}v\in\mathcal{V}_{L}(u):u\xleftrightarrow{G^{i}\cap\mathcal{V}_{L}(u)}v\
\text{or both}\ u,v\in\mathcal{C}^{i}_{\max}\Big{\\}}\Big{)}.$

Note that on the a.a.s. event
$|\mathcal{C}_{\max}^{i}|\geq\tfrac{\mu_{i}}{2}n$ and for all sufficiently
large $n$, every vertex $u$ such that
$|\widetilde{\mathcal{C}}_{L}(u)|<|\widetilde{\mathcal{C}}_{L,M}(u)|$ is at
distance at most $L$ from the set

$\mathcal{S}_{M}=\bigcup_{i\in I}\\{v\in G:|\mathcal{C}^{i}(v)|\geq M\text{
and }v\notin\mathcal{C}^{i}_{\max}\\}.$

However, by the Cauchy-Schwarz inequality, the expected number of such sites
divided by $n$ is at most

$\mathbb{E}\left[\frac{1}{n}\sum_{v\in[n]}|\mathcal{V}_{L}(v)|\mathds{1}_{\\{v\in\mathcal{S}_{M}\\}}\right]=\mathbb{E}\left[|\mathcal{V}_{L}(1)|\mathds{1}_{\\{1\in\mathcal{S}_{M}\\}}\right]\leq\mathbb{E}[|\mathcal{V}_{L}(1)|^{2}]^{1/2}\cdot\mathbb{P}(1\in\mathcal{S}_{M})^{1/2}.$

Moreover, by (15), $\mathbb{P}(1\in\mathcal{S}_{M})\to 0$ as $M\to\infty$
uniformly in $n$, and a straightforward computation shows that for fixed
$\Lambda$ and $L$, the second moment of $|\mathcal{V}_{L}(1)|$ is uniformly
bounded in $n$ (using e.g. that it is stochastically dominated by the size of
the $L$-neighborhood of the root in a BGW tree with
$\text{Bin}(n,\tfrac{\Lambda}{n})$ offspring distribution). Therefore,
Markov’s inequality implies that for every $\varepsilon>0$ and every $L$, one
can find $M$ large enough so that

$\limsup_{n\to\infty}\
\mathbb{P}\left(\frac{1}{n}\sum_{v\in[n]}|\mathcal{V}_{L}(v)|\mathds{1}_{\\{v\in\mathcal{S}_{M}\\}}\geq\varepsilon\right)\leq\varepsilon,$

and in particular,

$\limsup_{n\to\infty}\ \mathbb{P}\left(\frac{|\\{u\in
G:|\widetilde{\mathcal{C}}_{L}(u)|<|\widetilde{\mathcal{C}}_{L,M}(u)|\\}|}{n}\geq\varepsilon\right)\leq\limsup_{n\to\infty}\mathbb{P}\left(\exists
i\in[k]:|\mathcal{C}_{\max}^{i}|\leq\frac{\mu_{i}n}{2}\right)+\varepsilon=\varepsilon.$
(17)

Similarly, we define

$\widetilde{\mathcal{C}}_{L,M}(\varnothing)=\Big{(}\bigcap_{i\in
J}\Big{\\{}v\in\mathcal{V}_{L}(\varnothing)\cap\mathcal{C}^{i}(\varnothing)\Big{\\}}\Big{)}\cap\Big{(}\bigcap_{i\in
I}\
\Big{\\{}v\in\mathcal{V}_{L}(\varnothing):v\in\mathcal{C}^{i}(\varnothing)\
\text{or}\ \min(|\mathcal{C}^{i}(\varnothing)|,|\mathcal{C}^{i}(v)|)\geq
M\Big{\\}}\Big{)},$

and

$\widetilde{\mathcal{C}}_{L}(\varnothing)=\Big{(}\bigcap_{i\in
J}\Big{\\{}v\in\mathcal{V}_{L}(\varnothing)\cap\mathcal{C}^{i}(\varnothing)\Big{\\}}\Big{)}\cap\Big{(}\bigcap_{i\in
I}\
\Big{\\{}v\in\mathcal{V}_{L}(\varnothing):v\in\mathcal{C}^{i}(\varnothing)\
\text{or}\
|\mathcal{C}^{i}(\varnothing)|=|\mathcal{C}^{i}(v)|=\infty\Big{\\}}\Big{)},$

which is the decreasing limit of $\widetilde{\mathcal{C}}_{L,M}(\varnothing)$
as $M\to\infty$. Moreover,

$\displaystyle\mathbb{P}\Big{(}|\widetilde{\mathcal{C}}_{L}(\varnothing)|<|\widetilde{\mathcal{C}}_{L,M}(\varnothing)|\Big{)}\leq\mathbb{E}\Big{[}|\widetilde{\mathcal{C}}_{L,M}(\varnothing)|-|\widetilde{\mathcal{C}}_{L}(\varnothing)|\Big{]}\leq\sum_{i\in
I}\mathbb{E}\left[\sum_{v\in\mathcal{V}_{L}(\varnothing)}\mathds{1}_{\\{v\notin\mathcal{C}^{i}(\varnothing),\,M\,\leq\,|\mathcal{C}^{i}(v)|\,<\,\infty\\}}\right].$

Fix $i\in I$. For every edge $e\in\textbf{GW}(\Lambda)$, let us denote by
$e^{+}$ the endvertex of $e$ which is farther from the root. Then, for every
vertex $v\in\textbf{GW}(\Lambda)$ such that
$\mathcal{C}^{i}(\varnothing)\neq\mathcal{C}^{i}(v)$, the (unique) path
between $\varnothing$ and $v$ in $\textbf{GW}(\Lambda)$ contains an edge in
color $i$. Considering the closest such edge to $v$, we get

$\sum_{v\in\mathcal{V}_{L}(\varnothing)}\mathds{1}_{\\{v\notin\mathcal{C}^{i}(\varnothing),\,M\,\leq\,|\mathcal{C}^{i}(v)|\,<\,\infty\\}}\leq\sum_{e\in\mathcal{V}_{L}(\varnothing),\,\text{$e$
in color
$i$}}|\mathcal{C}^{i}(e^{+})\cap\mathcal{V}_{L}(e^{+})|\cdot\mathds{1}_{\\{M\,\leq\,|\mathcal{C}^{i}(e^{+})|\,<\,\infty\\}}.$

Since for any edge $e$ in color $i$, the component $\mathcal{C}^{i}(e^{+})$ is
contained in the subtree of the descendants of $e^{+}$, and is thus
independent of the remainder of $\textbf{GW}(\Lambda)$, we have

$\mathbb{E}\left[\sum_{v\in\mathcal{V}_{L}(\varnothing)}\mathds{1}_{\\{v\notin\mathcal{C}^{i}(\varnothing),\,M\,\leq\,|\mathcal{C}^{i}(v)|\,<\,\infty\\}}\right]\leq\mathbb{E}[|\mathcal{V}_{L}(\varnothing)|]\cdot\mathbb{E}\left[|\mathcal{V}_{L}(\varnothing)|\cdot\mathds{1}_{\\{M\,\leq\,|\mathcal{C}^{i}(\varnothing)|\,<\,\infty\\}}\right].$

Then, using Cauchy-Schwarz inequality as before, we get that

$\mathbb{P}(|\widetilde{\mathcal{C}}_{L}(\varnothing)|<|\widetilde{\mathcal{C}}_{L,M}(\varnothing)|)\xrightarrow[M\to\infty]{}0.$
(18)

The next step is to notice that since the sets
$\widetilde{\mathcal{C}}_{L,M}(u)$ are measurable with respect to the
$(L+M)$-neighborhood of a vertex $u$, for every $\ell\geq 1$, Proposition 3.1
implies that

$\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|\widetilde{\mathcal{C}}_{L,M}(u)|\,=\,\ell\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}(|\widetilde{\mathcal{C}}_{L,M}(\varnothing)|=\ell).$

We remark that this last step is reminiscent of a similar convergence in Lemma
5.2.4 in [10]. Together with (17) and (18), by letting $M\to\infty$ we get
that for any $L\geq 1$,

$\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|\widetilde{\mathcal{C}}_{L}(u)|\,=\,\ell\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}(|\widetilde{\mathcal{C}}_{L}(\varnothing)|=\ell).$
(19)

Finally, to conclude the proof of (3), it amounts to consider the $L\to\infty$
limit in the last display. For the right-hand side, we just observe that the
CA-component of the root is the increasing limit of the sets
$\widetilde{\mathcal{C}}_{L}(\varnothing)$ as $L\to\infty$, from which it
follows that for any $\ell\geq 1$,

$\mathbb{P}(|\widetilde{\mathcal{C}}_{L}(\varnothing)|=\ell,|\widetilde{\mathcal{C}}(\varnothing)|>\ell)\xrightarrow[L\to\infty]{}0,$

which yields for any $\ell\geq 1$,

$\mathbb{P}(|\widetilde{\mathcal{C}}_{L}(\varnothing)|=\ell)\xrightarrow[L\to\infty]{}\mathbb{P}(|\widetilde{\mathcal{C}}(\varnothing)|=\ell).$
(20)

It remains to show the corresponding convergence for a typical vertex of $G$.
We distinguish two cases. If the set $J$ is nonempty (or equivalently if
$\lambda_{1}^{*}\leq 1$), then we claim that for any vertex $u\in[n]$, we have

$\\{\widetilde{\mathcal{C}}_{L}(u)\neq\widetilde{\mathcal{C}}(u)\\}\
\subseteq\ \left(\bigcup_{i\in J}\\{|\mathcal{C}^{i}(u)|\geq
L\\}\right)\cup\left(\bigcup_{i\in I}\\{|\mathcal{C}^{i}(u)|\geq L\text{ and
}u\notin\mathcal{C}_{\max}^{i}\\}\right).$ (21)

Indeed, for the event on the left-hand side of (21) to hold, either there is a
vertex in $\widetilde{\mathcal{C}}(u)\setminus\mathcal{V}_{L}(u)$, which
together with $\widetilde{\mathcal{C}}(u)\subseteq\mathcal{C}^{1}(u)$ implies
that $|\mathcal{C}^{1}(u)|\geq L$, or there is a vertex $v$ in
$\widetilde{\mathcal{C}}(u)\cap\mathcal{V}_{L}(u)$ outside
$\widetilde{\mathcal{C}}_{L}(u)$, which means that there is $i\in[k]$ such
that $u$ and $v$ are connected by a path in $G^{i}$ exiting
$\mathcal{V}_{L}(u)$, and if $i\in I$, additionally
$\mathcal{C}^{i}(u)\neq\mathcal{C}^{i}_{\max}$. Now, given $\varepsilon>0$,
one can choose $L$ large enough so that
$\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|\geq L)\leq\tfrac{\varepsilon}{2k}$
for all $i\in J$ and
$\mathbb{P}(L\leq|\mathcal{C}^{i}(\varnothing)|<\infty)\leq\tfrac{\varepsilon}{2k}$
for all $i\in I$, and then using Proposition 3.1, we get that

$\begin{split}&\limsup_{n\to\infty}\ \mathbb{P}\left(\frac{|\\{u\in
G:|\widetilde{\mathcal{C}}_{L}(u)|<|\widetilde{\mathcal{C}}(u)|\\}|}{n}\geq\varepsilon\right)\\\
\leq\;&\sum_{i\in J}\limsup_{n\to\infty}\ \mathbb{P}\left(\tfrac{|\\{u\in
G\,:\,|\mathcal{C}^{i}(u)|\,\geq\,L\\}|}{n}\geq\frac{\varepsilon}{k}\right)+\sum_{i\in
I}\limsup_{n\to\infty}\ \mathbb{P}\left(\tfrac{|\\{u\in
G\,:\,L\,\leq\,|\mathcal{C}^{i}(u)|\,<\,\infty\\}|}{n}\geq\frac{\varepsilon}{k}\right)=0.\end{split}$
(22)

We consider now the slightly more difficult case when $J$ is empty. Let
$A=\bigcap_{i=1}^{k}\mathcal{C}^{i}_{\max}$. One has

$\big{\\{}|\widetilde{\mathcal{C}}_{L}(u)|=\ell,|\widetilde{\mathcal{C}}(u)|>\ell\big{\\}}\
\subseteq\ \Big{\\{}|\widetilde{\mathcal{C}}_{L}(u)|=\ell,u\in
A\Big{\\}}\cup\left(\bigcup_{i=1}^{k}\\{|\mathcal{C}^{i}(u)|\geq
L,\mathcal{C}^{i}(u)\neq\mathcal{C}^{i}_{\max}\\}\right)$ (23)

since either $u\in A$, or there is a vertex $v$ and $i\in[k]$ such that
$u,v\notin\mathcal{C}^{i}_{\max}$ but $u$ and $v$ are connected by a path in
$G^{i}$ exiting $\mathcal{V}_{L}(u)$. Moreover, note that if $u\in A$, then
$\widetilde{\mathcal{C}}(u)=A$, and thus

$\Big{\\{}|\widetilde{\mathcal{C}}_{L}(u)|=\ell,u\in A\Big{\\}}\ \subseteq\
\Big{\\{}\big{|}A\cap\mathcal{V}_{L}(u)\big{|}=\ell,|\mathcal{V}_{L}(u)|\geq
L\Big{\\}}\cup\\{|A|=\ell\\}.$

Indeed, if $u\in A$ and $|A|\geq\ell+1$, then $A$ must necessarily contain a
vertex outside $\mathcal{V}_{L}(u)$, which means that
$|\mathcal{V}_{L}(u)|\geq L$. Note that Theorem 1.1 (i) implies that
$\mathbb{P}(|A|=\ell)\to 0$ as $n\to\infty$, so we concentrate on the first
event in the union above. For $M\geq 1$, define

$A_{M}=\\{v:|\mathcal{C}^{i}(v)|\geq M\text{ for all }i\in[k]\\},$

where for convenience we see $A_{M}$ as a vertex subset of both $G$ or
$\textbf{GW}(\Lambda)$. By a similar argument as for (17), we know that for
every $\varepsilon>0$, there exists $M$ such that

$\limsup_{n\to\infty}\
\mathbb{P}\left(\Big{|}\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|A\cap\mathcal{V}_{L}(u)|\,=\,\ell,\,|\mathcal{V}_{L}(u)|\,\geq\,L\\}}-\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|A_{M}\cap\mathcal{V}_{L}(u)|\,=\,\ell,\,|\mathcal{V}_{L}(u)|\,\geq\,L\\}}\Big{|}\geq\varepsilon\right)=0.$

However, by Proposition 3.1 one has for any $L\geq 1$ and $M\geq 1$,

$\frac{1}{n}\sum_{u\in[n]}\mathds{1}_{\\{|A_{M}\cap\mathcal{V}_{L}(u)|\,=\,\ell,\,|\mathcal{V}_{L}(u)|\,\geq\,L\\}}\xrightarrow[n\to\infty]{\mathbb{P}}\mathbb{P}\big{(}|A_{M}\cap\mathcal{V}_{L}(\varnothing)|=\ell,|\mathcal{V}_{L}(\varnothing)|\geq
L\big{)},$

which goes to $0$ as $L\to\infty$ for any fixed $M\geq 1$. Indeed, this can be
seen by exploring $\mathcal{V}_{L}(u)$ in several steps. At each step, we fix
a vertex $v$ at the boundary of the already explored set and explore the
successors of $v$ at distance at most $M$ from $v$. Note that the probability
that $v$ belongs to $A_{M}$ is bounded from below by a positive constant,
which is independent of the previous steps. Furthermore, as $L\to\infty$ and
on the event $\\{|\mathcal{V}_{L}(\varnothing)|\geq L\\}$, the number of steps
goes almost surely to infinity, and thus the probability of the event
$\\{|A_{M}\cap\mathcal{V}_{L}(\varnothing)|=\ell\\}$ tends to 0 for every
fixed $\ell$. Then, by using also (16) again to handle the second union in
(23), we deduce that for every fixed $\varepsilon>0$ and $\ell\geq 1$, there
is a sufficiently large $L$ so that,

$\limsup_{n\to\infty}\mathbb{P}\left(\frac{|\\{u\in
G:|\widetilde{\mathcal{C}}_{L}(u)|=\ell,|\widetilde{\mathcal{C}}(u)|>\ell\\}|}{n}\geq\varepsilon\right)=0.$

Together with (19), (20) and (LABEL:eq:caseJnonempty), this proves (3).

The last piece of the proof of the proposition is to show that for any
$\ell\geq 2$,
$\nu_{\ell}=\mathbb{P}(|\widetilde{\mathcal{C}}(\varnothing)|=\ell)$ is
positive if and only if $\lambda_{k}^{*}>1$, and that the constant $a_{1}$
appearing in Part (i) of Theorem 1.1 is equal to the probability that the CA-
component of the root is infinite. This part bears close resemblance to the
proof of Proposition 2.18 (ii) from [10]. For the first part, assume that
$\lambda_{k}^{*}>1$, and let $\ell\geq 1$ be given. Then, with positive
probability one can have altogether $|\mathcal{C}_{k}(\varnothing)|=\ell$, all
vertices of $\mathcal{C}_{k}(\varnothing)$ are connected to infinity in
$\textbf{GW}^{k}(\Lambda)$, and $|\mathcal{C}^{i}(\varnothing)|<\infty$ for
all values of $i$ different from $k$. If the last events hold simultaneously,
one can observe that the CA-component of the root is precisely
$\mathcal{C}_{k}(\varnothing)$, and thus it has size $\ell$. Conversely, if
$\lambda_{k}^{*}\leq 1$, then it is well-known that all the components
$\mathcal{C}^{i}(\varnothing)$ are a.s. finite, and since edges have a.s. a
unique color, this implies that the CA-component of the root is necessarily
reduced to a single vertex.

For the last part, note that on the one hand, if
$|\widetilde{\mathcal{C}}(\varnothing)|=\infty$, then
$|\mathcal{C}^{i}(\varnothing)|=\infty$ for all $i\in[k]$, so

$a_{1}=\mathbb{P}(|\mathcal{C}^{i}(\varnothing)|=\infty\text{ for all
$i\in[k]$})\geq\mathbb{P}(|\widetilde{\mathcal{C}}(\varnothing)|=\infty).$

The proof of the reverse inequality appears as Lemma 5.1.1 in [10]; we provide
it for completeness. First, notice that if $a_{1}=0$, there is nothing to
prove. Thus, we may assume that $a_{1}>0$, which by Part (i) of Theorem 1.1 is
equivalent to $\lambda_{1}^{*}>1$. Suppose that each of the components
$\mathcal{C}^{i}(\varnothing)$ for $i\in[k]$ is infinite. We prove that in
this case, the CA-component of the root is also a.s. infinite. To begin with,
the well-known Kesten-Stigum theorem [6] implies that on the event
$\\{|\mathcal{C}^{1}(\varnothing)|=\infty\\}$, the number of vertices in
generation $L$ in the tree $\mathcal{C}^{1}(\varnothing)$ goes to infinity
almost surely as $L\to\infty$. However, conditionally on the vertices
$v_{1},\dots,v_{N}$ in the $L$-th generation of that tree, the subtrees
$T_{1},\dots,T_{N}$ of $\textbf{GW}(\Lambda)$ emanating from the vertices
$v_{1},\dots,v_{N}$, respectively, are all independent. Thus, the probability
that for at least $a_{1}N/2$ of them, the connected components of their root
are infinite in each of $\textbf{GW}^{i}(\Lambda)$ for $i\in[k]$, goes to one
as $N\to\infty$. Moreover, all such vertices are in the CA-component of
$\varnothing$. But as already mentioned, on the event
$\\{|\mathcal{C}^{1}(\varnothing)|=\infty\\}$ we have that $N=N(L)\to\infty$
almost surely as $L\to\infty$, so the result follows. ∎

###  3.2 Proof of Theorem 1.1 (ii) and Proposition 1.3

The proof starts with the following general lemma that will also be used for
the proof of Theorem 1.1 (iii) in the next section. For $I\subset[k]$, write
$\lambda_{I}^{*}=\Lambda-\sum_{i\in I}\lambda_{i}$.

######  Lemma 3.2.

For every $j\in[k]$ and $I\subseteq[k]\setminus\\{j\\}$ such that
$\max(\lambda_{I}^{*},\lambda_{j}^{*})<1$, one has uniformly in $n$,

$\lim_{M\to\infty}\mathbb{P}\big{(}\exists u\neq
v:u\xleftrightarrow{G^{I}}v,\,u\xleftrightarrow{G^{j}}v,\,u\stackrel{{\scriptstyle
G^{I\cup\\{j\\}}}}{{\centernot\longleftrightarrow}}v,\,\max(|\mathcal{C}^{I}(u)|,|\mathcal{C}^{j}(u)|)\geq
M\big{)}=0.$

###### Proof.

Fix $\varepsilon>0$ and a set $I\subseteq[k]\setminus\\{j\\}$ with
$\max(\lambda_{I}^{*},\lambda_{j}^{*})<1$. For every $u,v\in[n]$, define the
event

$\mathcal{A}_{u,v}:=\big{\\{}u\xleftrightarrow{G^{I}}v,\,u\xleftrightarrow{G^{j}}v,\,u\stackrel{{\scriptstyle
G^{I\cup\\{j\\}}}}{{\centernot\longleftrightarrow}}v\big{\\}}.$

Then, on the event $\mathcal{A}_{u,v}$, there exists a path $P$ connecting $u$
and $v$ not using color $j$. Since $u$ and $v$ are not connected in
$G^{I\cup\\{j\\}}$, $P$ must contain at least one edge which is not in
$G^{I}$. In particular, $P$ must exit the graph $\mathcal{C}^{I}(u)$ at some
point. Consequently, on the event $\mathcal{A}_{u,v}$, there must exist
$w_{1},w_{2}\in\mathcal{C}^{I}(u)$ which are connected in
$G^{j}\setminus\mathcal{C}^{I}(u)$ (where by this, we mean the subgraph of
$G^{j}$ with vertex set $[n]$ obtained by removing only the edges of
$\mathcal{C}^{I}(u)$). Moreover, note that conditioning on
$\mathcal{C}^{I}(u)$ only forces edges in $G\setminus\mathcal{C}^{I}(u)$ with
at least one endvertex in $\mathcal{C}^{I}(u)$ to have a color in $I$, while
it does not reveal any information for the remaining edges. Thus, for every
fixed graph $H$ containing $u$, one has

$\mathbb{P}\Big{(}w_{1}\xleftrightarrow{G^{j}\setminus
H}w_{2}\mid\mathcal{C}_{I}(u)=H\Big{)}\leq\mathbb{P}\Big{(}w_{1}\xleftrightarrow{G^{j}\setminus
H}w_{2}\Big{)}\leq\mathbb{P}(w_{1}\xleftrightarrow{G^{j}}w_{2})=\mathcal{O}\left(\frac{1}{n}\right),$

where for the last equality we use Corollary 2.3 together with the fact that
$G^{j}$ is stochastically dominated by $G(n,\lambda_{j}^{*}/n)$ (and that
$\lambda_{j}^{*}<1$ by hypothesis). As a consequence, on the event
$\\{v\in\mathcal{C}^{I}(u)\\}$,

$\mathbb{P}\Big{(}u\xleftrightarrow{G^{j}}v,\,u\stackrel{{\scriptstyle
G^{I\cup\\{j\\}}}}{{\centernot\longleftrightarrow}}v\mid\mathcal{C}^{I}(u)\Big{)}\leq\sum_{w_{1},w_{2}\in\mathcal{C}^{I}(u)}\mathbb{P}\Big{(}w_{1}\xleftrightarrow{G^{j}\setminus\mathcal{C}^{I}(u)}w_{2}\mid\mathcal{C}^{I}(u)\Big{)}=\mathcal{O}\left(\frac{|\mathcal{C}^{I}(u)|^{2}}{n}\right).$

Therefore,

$\displaystyle\mathbb{P}\big{(}\mathcal{A}_{u,v},\,|\mathcal{C}^{I}(u)|\geq
M\big{)}$
$\displaystyle=\mathcal{O}\left(\frac{1}{n}\sum_{t\,\geq\,M}t^{2}\cdot\mathbb{P}(v\in\mathcal{C}^{I}(u)\mid|\mathcal{C}^{I}(u)|=t)\cdot\mathbb{P}(|\mathcal{C}^{I}(u)|=t)\right)$
$\displaystyle=\mathcal{O}\left(\frac{1}{n^{2}}\sum_{t\,\geq\,M}t^{3}\cdot\mathbb{P}(|\mathcal{C}^{I}(u)|=t)\right)=\mathcal{O}\left(\frac{M^{3}\,\mathrm{e}^{-M\cdot
I_{\lambda_{I}}}}{n^{2}}\right),$ (24)

where we use (6) for the second equality and Lemma 2.1 for the last one. Also,
by a similar argument

$\mathbb{P}\big{(}\mathcal{A}_{u,v},\,|\mathcal{C}^{j}(u)|\geq
M\big{)}=\mathcal{O}\left(\frac{M^{3}\,\mathrm{e}^{-M\cdot
I_{\lambda_{j}}}}{n^{2}}\right).$ (25)

A union bound by summing (24) and (25) over all possible pairs of vertices
$\\{u,v\\}$ of $G$, and letting $M\to\infty$ finishes the proof. ∎

We call a set _connected_ if its vertices belong to the same connected
component.

######  Lemma 3.3.

Suppose that $\lambda_{k-1}^{*}<1$. Then, uniformly in $n$,

$\lim_{M\to\infty}\mathbb{P}(\exists S\subseteq[n]:|S|\geq M,\text{$S$ is
connected in each of $G^{1},\dots,G^{k-1}$ but not in $G_{k}$})=0.$

###### Proof.

Fix $S\subseteq[n]$ of size at least $M$, and assume that $S$ is connected in
each of the graphs $G^{1},\dots,G^{k-1}$. If $S$ is not connected in $G_{k}$,
it means that one can find two distinct vertices $u,v\in S$ which are not
connected in $G_{k}$. Let $I$ be a maximal subset of $[k-1]$ such that $u$ and
$v$ are connected in $G^{I}$. Since $u$ and $v$ are not connected in $G_{k}$,
$I\neq[k-1]$, and hence there exists $j\in[k-1]\setminus I$ such that $u$ and
$v$ are not connected in $G^{I\cup\\{j\\}}$. However, using that
$\max(\lambda_{I}^{*},\lambda_{j}^{*})<1$ and $|\mathcal{C}^{j}(u)|\geq|S|\geq
M$, Lemma 3.2 ensures that this event happens with probability converging to 0
as $M\to\infty$, uniformly in $n$. ∎

We are ready conclude the proofs of Theorem 1.1 (ii) and Proposition 1.3.

###### Proof of Proposition 1.3.

Denote by $\widetilde{\mathcal{C}}_{\max}$ the largest CA-component in $G$. As
the vertices of $\widetilde{\mathcal{C}}_{\max}$ form a connected set in
$G^{i}$ for every $i\in[k-1]$, by Lemma 3.3 we have that uniformly in $n$,

$\lim_{M\to\infty}\ \mathbb{P}(|\widetilde{\mathcal{C}}_{\max}|\geq
M,\text{$\widetilde{\mathcal{C}}_{\max}$ is not connected in $G_{k}$})=0.$
(26)

On the other hand, if $\widetilde{\mathcal{C}}_{\max}$ is connected in
$G_{k}$, it is obtained by intersecting a connected component in $G^{k}$ and
one in $G_{k}$. Moreover, by definition the probability of having an edge
present in $G^{k}$ is
$1-\prod_{i=1}^{k-1}(1-\frac{\lambda_{i}}{n})\leq\tfrac{\lambda_{k}^{*}}{n}=\tfrac{1}{n}$.
Thus, $G^{k}$ is stochastically dominated by $G(n,1/n)$. However, it is well-
known that the size of the largest component in $G(n,1/n)$ is a.a.s. of order
$n^{2/3}$ (see Proposition 5.2 in [11]), in particular it is a.a.s. smaller
than $n^{3/4}$, say. On the other hand, by a similar argument as in (6) one
has that for any $n>\ell\geq M\geq 2$ and any distinct vertices
$v_{1},\dots,v_{M}\in[n]$,

$\mathbb{P}\big{(}v_{M}\in\mathcal{C}^{k}(v_{1})\mid|\mathcal{C}^{k}(v_{1})|=\ell,v_{2},\dots,v_{M-1}\in\mathcal{C}^{k}(v_{1})\big{)}=\frac{\ell-(M-1)}{n-(M-1)}\leq\frac{\ell}{n},$

and the same holds with $\mathcal{C}_{k}(v_{1})$ instead of
$\mathcal{C}^{k}(v_{1})$. Thus, for any $M\geq 2$ and any distinct
$v_{1},\dots,v_{M}\in[n]$,

$\displaystyle\mathbb{P}\big{(}v_{1},\dots,v_{M}\text{ are connected in
}G^{k},|\mathcal{C}^{k}_{\max}|\leq n^{3/4}\big{)}$
$\displaystyle\leq\sum_{\ell=M}^{n^{3/4}}\bigg{(}\frac{\ell}{n}\bigg{)}^{M-1}\cdot\mathbb{P}(|\mathcal{C}^{k}(v_{1})|=\ell)$
$\displaystyle=\frac{\mathbb{E}[|\mathcal{C}^{k}(v_{1})|^{M-1}\cdot\mathds{1}_{\\{|\mathcal{C}^{k}(v_{1})|\leq
n^{3/4}\\}}]}{n^{M-1}}$ $\displaystyle\leq n^{-\frac{M-1}{4}}.$

Likewise, we know by (5) that a.a.s. the size of the largest connected
component in $G_{k}$ is at most $\tfrac{2}{I_{\lambda_{k}}}\log n$, and as
above one has

$\mathbb{P}\big{(}v_{1},\dots,v_{M}\text{ are connected in
}G_{k},|\mathcal{C}_{k}(v_{1})|\leq\tfrac{2}{I_{\lambda_{k}}}\log
n\big{)}=\mathcal{O}\bigg{(}\frac{(\log n)^{M-1}}{n^{M-1}}\bigg{)}.$

Summing over all possible vertices $v_{1},\dots,v_{M}\in[n]$ and using
independence between $G^{k}$ and $G_{k}$, we deduce that

$\displaystyle\mathbb{P}(\exists v_{1},\dots,v_{M}\text{ connected in both
}G_{k}\text{ and }G^{k})$
$\displaystyle\leq\mathbb{P}\bigg{(}\max_{u\in[n]}|\mathcal{C}^{k}(u)|\geq
n^{3/4}\bigg{)}+\mathbb{P}\bigg{(}\max_{u\in[n]}|\mathcal{C}_{k}(u)|\geq\tfrac{2}{I_{\lambda_{k}}}\log
n\bigg{)}+\mathcal{O}\bigg{(}\frac{(\log
n)^{M-1}}{n^{\frac{M-5}{4}}}\bigg{)}=o(1),$

where the last equality holds as soon as $M\geq 6$. Together with (26), this
concludes the proof of the proposition. ∎

###### Proof of Theorem 1.1 (ii).

Recall that now $\lambda_{k}^{*}>1>\lambda_{k-1}^{*}$, and in particular, all
graphs $G^{i}$ with $i\leq k-1$ are subcritical while $G^{k}$ is
supercritical. Firstly, we observe that there exists $\varepsilon>0$ such that
a.a.s. the largest CA-component has size larger than $\varepsilon\log n$.
Indeed, we know by (5) that a.a.s. there exists a connected component in
$G_{k}$ of size at least $\log n/(2I_{\lambda_{k}})$, and hence (7) and Lemma
2.10 imply together that a.a.s. its intersection with the giant component of
$G^{k}$ has size at least $\mu_{\lambda_{k}^{*}}\log n/(4I_{\lambda_{k}})$
(recall that $G^{k}$ and $G_{k}$ are independent).

Next, let $\widetilde{\mathcal{C}}_{\max}$ be the largest CA-component. By
definition its vertices are connected in all the graphs $G^{1},\dots,G^{k-1}$,
and thus by Lemma 3.3 a.a.s. they are also connected in $G_{k}$. This means
that $\widetilde{\mathcal{C}}_{\max}$ is in fact obtained as the intersection
of a connected component of $G_{k}$ with one of $G^{k}$. However, it is well-
known that a.a.s. all connected components in a supercritical ER random graph
but the largest one have size $\mathcal{O}(\log n)$ (see e.g. Section 4.4.1 in
[11]). Thus, by the same argument as in the proof of Proposition 1.3, we
deduce that the probability of having three vertices connected in $G_{k}$ and
participating in the same non-giant component of $G^{k}$ is
$\mathcal{O}(n^{3}\cdot\frac{(\log n)^{4}}{n^{4}})=o(1)$. Hence, a.a.s. every
CA-component of size at least 3 (and $\widetilde{\mathcal{C}}_{\max}$ in
particular) is contained in the giant in $G^{k}$.

Finally, by Lemma 2.10 and Corollary 2.13 we conclude that, with the notation
of Corollary 2.13,

$\frac{|\widetilde{\mathcal{C}}_{\max}|}{\log
n}\xrightarrow[n\to\infty]{\mathbb{P}}a(\mu_{\lambda_{k}^{*}},\lambda_{k}),$

which finishes the proof. ∎

###  3.3 Proof of Theorem 1.1 (iii)

We assume throughout this section that $\lambda_{k}^{*}<1$.

We call _support_ of a CA-component the subgraph of $G$ obtained as the union
of all paths in $G^{1},\ldots,G^{k}$ between any pair of distinct vertices of
the CA-component. The main observation of the proof is the following lemma.

######  Lemma 3.4.

A.a.s. every CA-component is supported by either a single vertex, a single
edge or a cycle of $G$. In particular, a.a.s. every CA-component has size at
most $k$.

###### Proof.

Consider a CA-component $\widetilde{\mathcal{C}}$ and assume that it is not
reduced to a single vertex. Let $u$ and $v$ be two different vertices of
$\widetilde{\mathcal{C}}$. Assume first that
$|\mathcal{C}^{i}(u)|\geq\frac{c_{1}(\Lambda)}{k}\log n$ for some $i\in[k]$,
with the notation of Remark 2.7. By the second point of this remark, and since
$\lambda_{i}^{*}<1$ by hypothesis, we know that a.a.s. $\mathcal{C}^{i}(u)$ is
a tree with no repeated edge. In other words, $u$ and $v$ are connected by a
unique path $P$ in $G^{i}$, and since $P$ contains no repeated edges, $u$ and
$v$ cannot be connected in $G^{\\{i,j\\}}$ for any color $j$ in $P$. However,
Lemma 3.2 applied for $I=\\{i\\}$ shows that a.a.s. this situation does not
happen. Thus, we may assume that
$|\mathcal{C}^{i}(u)|\leq\frac{c_{1}(\Lambda)}{k}\log n$ for all $i$, and by
summation over $i$ we may as well assume that $\mathcal{C}(u)$, the connected
component of $u$ in $G$, has size at most $c_{1}(\Lambda)\log n$. Then, using
the first result from Remark 2.7, we know that a.a.s. either $\mathcal{C}(u)$
contains no cycles and at most one repeated edge or no repeated edges and at
most one cycle. Moreover, note that for every pair of vertices $u$ and $v$ in
$\widetilde{\mathcal{C}}$, $u$ and $v$ cannot be disconnected in $G$ by
deleting an edge with a single color in $\mathcal{C}(u)$. Thus, the unique
cycle or repeated edge necessarily supports $\widetilde{\mathcal{C}}$, which
concludes the proof of the first part.

For the second part, just observe that when $|\widetilde{\mathcal{C}}|\geq 3$,
the vertices in $\widetilde{\mathcal{C}}$ divide its supporting cycle into
paths without common colors, so there are at most $k$ such paths. ∎

For a positive integer $\ell$, we say that a cycle in $G$ is _separated into
$\ell$ parts_ if it can be divided into $\ell$ consecutive paths that use
disjoint sets of colors. We say that it is separated into _exactly_ $\ell$
parts if it is separated into $\ell$ parts but not into $\ell+1$ parts. The
following fact follows directly from the previous definition.

######  Lemma 3.5.

Every cycle in $G$ supports at most one CA-component of size more than $1$.
Moreover, a CA-component supported by a cycle has size $\ell$ if and only if
its supporting cycle is separated into exactly $\ell$ parts.

###### Proof.

Suppose that $\widetilde{\mathcal{C}}_{1}$ and $\widetilde{\mathcal{C}}_{2}$
are two distinct CA-components of sizes $\ell_{1},\ell_{2}\geq 2$,
respectively, which are supported by the same cycle, say $C$. Then,
$\widetilde{\mathcal{C}}_{1}$ and $\widetilde{\mathcal{C}}_{2}$ must be
disjoint. Moreover, the vertices of $\mathcal{C}_{1}$ separate $C$ into
$\ell_{1}$ parts, and the ones of $\mathcal{C}_{2}$ separate $C$ into
$\ell_{2}$ parts. It follows that the vertices of
$\mathcal{C}_{1}\cup\mathcal{C}_{2}$ separate $C$ into $\ell_{1}+\ell_{2}$
parts, and so $\mathcal{C}_{1}\cup\mathcal{C}_{2}$ is a CA-component itself, a
contradiction.

Thus, one cycle can support at most one CA-component. At the same time, if it
supports a CA-component of size $\ell\geq 2$, it cannot be divided into
$\ell+1$ parts as otherwise it would also support a CA-component of size more
than $\ell$, which finishes the proof. ∎

The last important piece towards the proof of Theorem 1.1 (iii) is the
following lemma.

######  Lemma 3.6.

For every $m\in\\{2,\dots,k\\}$, denote by $Y_{m}$ the number of cycles in $G$
that are separated into exactly $m$ parts. Then, there are positive constants
$\widetilde{\beta}_{2}$ and $\beta_{3},\ldots,\beta_{k}$, such that

$(Y_{2},\ldots,Y_{k})\xrightarrow[n\to\infty]{d}\mathrm{Po}(\widetilde{\beta}_{2})\otimes\bigotimes_{m=3}^{k}\mathrm{Po}(\beta_{m}).$

###### Proof of Lemma 3.6.

For every $m\in\\{2,\ldots,M\\}$, denote by $Y_{m,M}$ the number of cycles in
$G$ that are separated into exactly $m$ parts and having length at most $M$.

The first step of the proof is to show that for every $m\in\\{2,\dots,k\\}$,
uniformly in $n$,

$\mathbb{E}[Y_{m}-Y_{m,M}]\xrightarrow[M\to\infty]{}0.$ (27)

To show this, note that a cycle of $G$ is separated into (at least) two parts
if and only if there exists a nonempty subset $I\subseteq[k]$ different from
$[k]$ such that one part of the cycle is contained in $G_{I}$ while the other
part of the cycle is contained in $G^{I}$. For every $\ell\geq 3$, set
$C_{2,\ell}$ to be the number of cycles of length $\ell$ in $G$ which are
separated into (at least) two parts.

Then, using that to form a cycle of length $\ell$, one may choose its vertices
in $\binom{n}{\ell}$ ways and order them in $\frac{(\ell-1)!}{2}$ ways, we
have

$\mathbb{E}[C_{2,\ell}]\leq\binom{n}{\ell}\frac{(\ell-1)!}{2}\sum_{I\subseteq[k]}\sum_{m=1}^{\ell-1}\left(\frac{\sum_{i\in
I}\lambda_{i}}{n}\right)^{m}\left(\frac{\sum_{i\in[k]\setminus
I}\lambda_{i}}{n}\right)^{\ell-m}\leq 2^{k}\cdot(\lambda_{k}^{*})^{\ell}.$
(28)

It follows that

$\mathbb{E}\left[Y_{m}-Y_{m,M}\right]\leq\sum_{\ell=M+1}^{n}\mathbb{E}[C_{2,\ell}]\leq
2^{k}\sum_{\ell=M+1}^{\infty}(\lambda_{k}^{*})^{\ell},$

which goes to $0$ as $M\to\infty$ uniformly in $n$ since $\lambda_{k}^{*}<1$
by hypothesis, thus proving (27).

The second step of the proof is to show that for every fixed $M\geq k$, one
has

$(Y_{2,M},\ldots,Y_{k,M})\xrightarrow[n\to\infty]{d}\bigotimes_{m=2}^{k}\mathrm{Po}(\beta_{m,M})$
(29)

for some positive constants $(\beta_{m,M})_{m=2}^{k}$. For $m\leq k$, denote
by $p_{m,\ell}$ the probability that a cycle of length $\ell$ in $G$ is
separated into exactly $m$ parts. Let also $\widetilde{Y}_{m,\ell}$ denote the
number of cycles of length $\ell$ which are separated into exactly $m$ parts.
In particular,

$Y_{m,M}=\sum_{\ell=\max(m,3)}^{M}\widetilde{Y}_{m,\ell}.$

Adopting the notation of Lemma 2.8, observe also that for every $m\leq k$,
conditionally on $G$,

$\widetilde{Y}_{m,\ell}\ \mathop{=}^{d}\ \text{Bin}(C_{\ell},p_{m,\ell}).$

Moreover, recall that $G$ is distributed as an Erdós-Renyi random graph with
parameters $n$ and $p=(1+o(1))\cdot\tfrac{\Lambda}{n}$, so Lemma 2.8 shows
that

$(C_{3},\dots,C_{M})\xrightarrow[n\to\infty]{d}\bigotimes_{\ell=3}^{M}Z_{\ell}$

where for every $\ell\in\\{3,\dots,M\\}$, $Z_{\ell}$ is a Poisson random
variable with parameter $\gamma_{\ell}=\tfrac{\Lambda^{\ell}}{2\ell}$. It
follows that for every fixed $\ell$, (still writing with a slight abuse of
notation $p_{m,\ell}$ for the limiting value of this probability as
$n\to\infty$, see Remark 3.7 for an explicit expression when $m=k$),

$(\widetilde{Y}_{2,\ell},\dots,\widetilde{Y}_{k,\ell})\xrightarrow[n\to\infty]{d}\Big{(}\text{Bin}(Z_{\ell},p_{2,\ell}),\dots,\text{Bin}(Z_{\ell},p_{k,\ell})\Big{)},$

which by the thinning property of the Poisson distribution (see e.g. Section
5.3 in [9]) is a vector of independent Poisson variables with parameters
$(p_{m,\ell}\cdot\gamma_{\ell})_{m=2}^{\ell}$. Summing over $\ell$ and using
the independence of the variables $(Z_{\ell})_{\ell=3}^{M}$, we deduce that
(29) holds with

$\beta_{m,M}=\sum_{\ell=\max(m,3)}^{M}p_{m,\ell}\cdot\gamma_{\ell}.$

The final step is to show that for every $m\in\\{2,\dots,k\\}$, the sequence
$(\beta_{m,M})_{M\geq 3}$ is a bounded non-decreasing sequence, which
therefore converges as $M\to\infty$ to some positive and finite constant. The
fact that it is non-decreasing is straightforward by definition. On the other
hand, by (28) we deduce that for every $m\in\\{2,\dots,k\\}$ and $M\geq 1$,

$\beta_{m,M}\leq\liminf_{n\to\infty}\
\mathbb{E}[Y_{m,M}]\leq\liminf_{n\to\infty}\
\mathbb{E}\left[\sum_{\ell=3}^{M}C_{2,\ell}\right]\leq\frac{2^{k}}{1-\lambda_{k}^{*}},$

showing that the sequence $(\beta_{m,M})_{M\geq 3}$ is bounded, which
completes the proof. ∎

To finish the proof of Theorem 1.1 (iii), note that by Lemma 3.4 a.a.s. for
every $m\geq 3$ we have $N_{m}=Y_{m}$, while $N_{2}$ is the sum of $Y_{2}$ and
the repeated edges in $G$. Thus, using the notation of Lemma 3.6 and Corollary
2.9, Theorem 1.1 (iii) follows with the constants
$\beta_{2}=\widetilde{\beta}_{2}+\gamma_{2}$ and $(\beta_{m})_{m=3}^{k}$.
$\square$

######  Remark 3.7.

We note that while it is possible to provide explicit expressions for
$\beta_{2},\dots,\beta_{k}$ in terms of $\lambda_{1},\dots,\lambda_{k}$, they
tend to be more and more complicated as $\ell$ decreases from $k$ to $2$.
However, one can provide a simple formula for $\beta_{k}$. We do this in the
case $k\geq 3$; in fact, with the notation of Corollary 2.9, in the case $k=2$
one simply needs to add $\gamma_{2}$ to the final result to account for the
number of repeated edges.

By the previous proof, one has

$\beta_{k}=\sum_{\ell\geq k}p_{k,\ell}\cdot\gamma_{\ell},$

where $p_{k,\ell}$ is the limit (as $n\to\infty$) of the probability that a
cycle of length $\ell$ in $G$ is separated into exactly $k$ parts, and
$\gamma_{\ell}=\tfrac{\Lambda^{\ell}}{2\ell}$. To compute $p_{k,\ell}$, one
needs to decide the lengths $s_{1},\dots,s_{k}\geq 1$ of the portions of the
cycle in colors $1,\dots,k$, respectively (with the constraint that
$s_{1}+\dots+s_{k}=\ell$). Then, one needs to choose the starting vertex of
the path colored in color $1$ (say when turning clockwise), for which there
are $\ell$ choices, and the order of appearance of the other colors, for which
there are $(k-1)!$ choices. Finally, note that as $n\to\infty$, the
probability that an edge is colored in color $i$ tends to
$\lambda_{i}/\Lambda$, which in total yields the formula

$p_{k,\ell}=\ell(k-1)!\cdot\sum_{s_{1}+\dots+s_{k}=\ell}\prod_{i=1}^{k}\left(\frac{\lambda_{i}}{\Lambda}\right)^{s_{i}}.$

Altogether this gives

$\beta_{k}=\sum_{\ell\geq
k}p_{k,\ell}\cdot\gamma_{\ell}=\frac{(k-1)!}{2}\sum_{\ell\geq
k}\sum_{s_{1}+\dots+s_{k}=\ell}\prod_{i=1}^{k}\lambda_{i}^{s_{i}}=\frac{(k-1)!}{2}\prod_{i=1}^{k}\Bigg{(}\sum_{j=1}^{\infty}\lambda_{i}^{j}\Bigg{)}=\frac{(k-1)!}{2}\prod_{i=1}^{k}\frac{\lambda_{i}}{1-\lambda_{i}},$

remembering for the third equality that the sum runs over indices
$\\{s_{i}\\}_{i\in[k]}$ larger than or equal to $1$.

For completeness, let us mention another slightly different way to compute
$\beta_{k}$. Note first that since CA-components are supported by cycles or
single edges, the expected number of CA-components of size $k$, or
equivalently of cycles which are separated in exactly $k$ parts, is equal to

$\frac{1+o(1)}{2}\sum_{i_{1},\dots,i_{k}\in[k]}\sum_{u_{1},\dots,u_{k}\in[n]}\mathbb{P}(u_{1}\xleftrightarrow{G_{i_{1}}}u_{2},\dots,u_{k}\xleftrightarrow{G_{i_{k}}}u_{1}),$

where the two sums run over $k$-tuples of ordered pairwise distinct elements
of $[k]$ and $[n]$, respectively, with $i_{1}=1$ (the factor $1/2$ coming from
the fact that there are two possible ways to orient a cycle). Now, recall that
for any pair of distinct vertices $u,v\in[n]$ and any $i\in[k]$, by (6) one
has that

$\mathbb{P}(v\in\mathcal{C}_{i}(u))=\frac{\mathbb{E}[|\mathcal{C}_{i}(u)|-1]}{n-1}.$

Thus, by induction we get that for any $(i_{1},\dots,i_{k})$,

$\displaystyle\sum_{u_{1},\dots,u_{k}}\mathbb{P}(u_{1}\xleftrightarrow{G_{i_{1}}}u_{2},\dots,u_{k}\xleftrightarrow{G_{i_{k}}}u_{1})$
$\displaystyle=\frac{\mathbb{E}[|\mathcal{C}_{i_{k}}(1)|-1]}{n-1}\cdot\sum_{u_{1},\dots,u_{k}}\mathbb{P}(u_{1}\xleftrightarrow{G_{i_{1}}}u_{2},\dots,u_{k-1}\xleftrightarrow{G_{i_{k-1}}}u_{k})$
$\displaystyle=n(n-1)\dots(n-k+1)\prod_{i=1}^{k}\frac{\mathbb{E}[|\mathcal{C}_{i}(1)|-1]}{n-1}$
$\displaystyle=(1+o(1))\prod_{i=1}^{k}\mathbb{E}[|\mathcal{C}_{i}(1)|-1],$

where for the second equality we use that the number of choices for the
sequence $(u_{1},\dots,u_{k})$ is $n(n-1)\dots(n-k+1)$. The formula follows
since there are $(k-1)!$ ways to choose $i_{2},\dots,i_{k}$, and with the
notation of Section 3.1

$\mathbb{E}[|\mathcal{C}_{i}(1)|-1]=(1+o(1))\cdot\mathbb{E}[|\mathbf{GW}(\lambda_{i})|-1]=(1+o(1))\cdot\frac{\lambda_{i}}{1-\lambda_{i}},$

where the last equality is derived from the fact that for every $d\geq 1$, the
expected number of vertices at distance exactly $d$ from the root in
$\mathbf{GW}(\lambda_{i})$ is $\lambda_{i}^{d}$.

##  4 Conclusion

In this paper, we characterized precisely the size of the largest CA-component
in randomly colored Erdős-Rényi random graphs in the entire supercritical and
subcritical regimes, and in part of the intermediate regime as well. The most
obvious open question that we leave concerns the size of the largest CA-
component when $\lambda_{k-1}^{*}\geq 1>\lambda_{1}^{*}$. The additional
difficulty this point presents compared to the second part of Theorem 1.1 is
that in general, one cannot obtain the largest CA-component as an intersection
of two independent random graphs. Nevertheless, we conjecture that an analogue
of Theorem 1.1 (ii) holds in this case as well. Unfortunately, confirming this
fact seems to be out of reach with our present techniques even in the simplest
case when $k=3$. We remark that when $\lambda_{m}^{*}<1$, by a statement
similar to Lemma 3.3 (that is also proved in a similar way) one may reduce the
problem to the case of $k-m+1$ colors where $G^{2},\ldots,G^{k-m+1}$ are all
supercritical graphs while $G^{1}$ is subcritical.

In the critical case when $\lambda_{1}^{*}=1<\lambda_{2}^{*}$, we suspect that
the size of the largest CA-component divided by $n^{2/3}$ converges in
distribution towards a non-degenerate random variable. The reason is that in
$G^{1}$, the size of the largest component divided by $n^{2/3}$ converges in
distribution, and the largest components in $G^{2},\ldots,G^{k}$ are of linear
order. However, the lack of independence makes it difficult to turn this
heuristic into a rigorous proof.

Another possible direction could be to explore the case of other classical
random graphs, or the closely related model of randomly vertex-color-avoiding
random graph, which was initially considered in the literature [7, 8] (and in
which, as its name suggests, we color the vertices of the graph instead of the
edges). In particular, as suggested in [7], it could be interesting to study
the effect of clustering (typical for random graphs with power law degree
distributions, for example), as it arises in numerous recently introduced
real-world networks models. Indeed, in this case, removing vertices with large
degree could have a dramatic effect on the connectivity properties of the
graph.

Acknowledgments. We thank Dieter Mitsche for enlightening discussions, and to
Balázs Ráth for several comments and corrections on a first version of this
paper.

## References

  * [1] B. Bollobás.  Random Graphs.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2nd edition, 2001.
  * [2] N. Curien.  Random graphs: the local convergence point of view.  Unpublished lecture notes. Available at https://www.math.u-psud.fr/{̃}curien/cours/cours-RG-V3.pdf, 2017.
  * [3] A. Dembo and O. Zeitouni.  Large deviations techniques and applications, volume 38.  Springer Science & Business Media, 2009.
  * [4] G. R. Grimmett.  The random-cluster model, volume 333.  Springer Science & Business Media, 2006.
  * [5] A. Kadović, S. M. Krause, G. Caldarelli, and V. Zlatic.  Bond and site color-avoiding percolation in scale-free networks.  Physical Review E, 98(6):062308, 2018.
  * [6] H. Kesten and B. P. Stigum.  A limit theorem for multidimensional galton-watson processes.  The Annals of Mathematical Statistics, 37(5):1211–1223, 1966.
  * [7] S. M. Krause, M. M. Danziger, and V. Zlatić.  Hidden connectivity in networks with vulnerable classes of nodes.  Physical Review X, 6(4):041022, 2016.
  * [8] S. M. Krause, M. M. Danziger, and V. Zlatić.  Color-avoiding percolation.  Physical Review E, 96(2):022313, 2017.
  * [9] G. Last and M. Penrose.  Lectures on the Poisson process, volume 7.  Cambridge University Press, 2017.
  * [10] B. Ráth, K. Varga, P. T. Fekete, and R. Molontay.  Color-avoiding percolation in edge-colored Erdős-Rényi graphs.  _arXiv: 2208.12727_ , 2022.
  * [11] R. van der Hofstad.  Random graphs and complex networks, Volume I, volume 43.  Cambridge university press, 2016.
  * [12] R. van der Hofstad.  Random graphs and complex networks, volume II.  Book in preparation. Preliminary version available at https://www.win.tue.nl/~rhofstad/, 2022.