# Upper tail of the spectral radius of sparse Erdős-Rényi graphs

Anirban Basak  Anirban Basak, International Centre for Theoretical Sciences,
Tata Institute of Fundamental Research, Bangalore, India
<EMAIL_ADDRESS>
###### Abstract.

We consider an Erdős-Rényi graph $\mathbb{G}(n,p)$ on $n$ vertices with edge
probability $p$ such that

$\sqrt{\frac{\log n}{\log\log n}}\ll np\leqslant n^{1/2-o(1)},$

and derive the upper tail large deviations of the largest eigenvalue of the
adjacency matrix. Within this regime we show that, for $p\gg n^{-2/3}$ the
$\log$-probability of the upper tail of the largest eigenvalue equals to that
of planting a clique of an appropriate size (upon ignoring smaller order
terms), while for $p\ll n^{-2/3}$ the same is given by that of the existence
of a high degree vertex.

In the regime $\log(np)\gtrsim\log n$ the large deviations of the spectral
radius is derived from that of homomorphism counts of cycles of even length. A
similar dichotomy, as above, arises for the homomorphism counts of cycles of
length $2t$, with the threshold depending on $t$.

This, in particular, identifies a sparsity regime, both in the context of the
largest eigenvalue and homomorphism counts of even cycles, where the large
deviation is due to the presence of a non-planted localized structure. It
further demonstrates that in a certain sparsity regime the large deviation
rate functions for the homomorphism and subgraph counts differ from each
other, while the large deviation speeds continue to be the same, even when the
expected value of the former is $1+o(1)$ times that of the latter.

Our results also identify the typical behavior of $\mathbb{G}(n,p)$
conditioned on the upper tail events of the spectral radius and homomorphism
counts of even cycles in certain sub-regimes of $p$.

###### Key words and phrases:

Erdős-Rényi graph, large deviations, largest eigenvalue, cycle homomorphism
counts.

###### 2010 Mathematics Subject Classification:

05C80, 60B20, 60C05, 60F10.

##  1\. Introduction and main results

Study of spectral statistics of large random matrices are of significant
interest. There is a host of results regarding the typical behavior of
spectral observables of random matrices. However, results on atypical
behaviors, such as large deviations, of spectral observables, e.g. extreme
eigenvalues, the esd (empirical spectral distribution), are few and far
between. Using the explicit formula for the joint density of the eigenvalues
large deviations of the largest eigenvalue and the empirical measure of the
eigenvalues of goe (Gaussian orthogonal ensemble) matrices were obtained in
[11, 12]. Beyond such exactly solvable models of random matrices, the first
breakthrough was due to Bordenave and Caputo [18], where they derived large
deviations of the esd of Wigner matrices with entires with stretched
exponential tails. There they showed that the large deviation event is created
by a relatively few large entries. This was later extended for the largest
eigenvalue by Augeri [4]. Very recently, Guionnet and Husson [26], using
asymptotics of spherical integrals, derived the large deviations for the
largest eigenvalue for Wigner matrices with entries possessing a sharp sub-
Gausian tail (e.g. Rademacher distribution), and this has been extended to the
case of entries with sub-Gaussian tails, see [6].

The results mentioned thus far are in the context of dense random matrices.
The goal of this article is to derive the large deviations of the largest
eigenvalue of a class of sparse random matrices, namely, the adjacency
matrices of Erdős-Rényi graphs. An Erdős-Rényi graph $\mathbb{G}(n,p)$ on $n$
vertices is the random graph obtained by joining the edge between each pair of
vertices with probability $p=p(n)\in(0,1)$, and independently of every other
pair. Here we consider the case $p\to 0$ as $n\to\infty$.

Over the last decade or so there have been extensive research on understanding
large deviation phenomena in random graph models. Chatterjee and Varadhan [21]
first successfully considered the problem of upper tail large deviations of
triangle counts in dense $\mathbb{G}(n,p)$, i.e. $p\asymp 1$ (see Section 1.5
for the notations used in this paper). To tackle this problem [21] introduced
a general framework for large deviation principle that uses Szemerédi’s
regularity lemma [35] and the theory of graph limits [19, 31, 32]. They
expressed the large deviation rate function as the solution of a mean-field
variational problem, and obtained the structure of the random graph
conditioned on the large deviation event in the replica symmetry region. Later
this was extended by Lubetzky and Zhao [33] for nice graph parameters, e.g.
regular subgraph densities and the spectral radius. They also identified the
phase boundary between the replica symmetry and symmetry breaking regimes.

In a breakthrough work Chatterjee and Dembo [20] proposed a new framework of
nonlinear large deviations that can be applied to a host of problems,
including, in particular, the upper tail large deviations of subgraph counts
in sparse $\mathbb{G}(n,p)$. Similar to the dense setting, here also the large
deviation rate function is given by the solution of an appropriate mean-field
variational problem, which was solved in [17]. The results of [20] have been
extended and improved by [5, 22, 24].

The recent work [22], in addition to the large deviations of homomorphism
densities, derives the large deviation of the upper tail of the spectral
radius of an Erdős-Rényi graph where the rate function is again shown to be
the solution of some mean-field variational problem. The solution to this
variational problem was identified in [15]. These two results together imply
that

(1.1)
$\lim_{n\to\infty}-\frac{\log\mathbb{P}(\lambda(\mathbb{G}(n,p))\geqslant(1+\delta)np)}{n^{2}p^{2}\log(1/p)}=\min\left\\{\frac{(1+\delta)^{2}}{2},\delta(1+\delta)\right\\},\quad\text{
for }n^{-1/2}\ll p\ll 1,$

and $\delta>0$, where $\lambda(\mathbb{G}(n,p))$ denotes the largest
eigenvalue of the adjacency matrix of $\mathbb{G}(n,p)$. On the other hand, in
[16], using a completely different approach, it has been shown that

(1.2)
$\lim_{n\to\infty}-\frac{\log\mathbb{P}(\lambda(\mathbb{G}(n,p)\geqslant(1+\delta)\sqrt{\mathfrak{L}_{p}})}{\log
n}=2\delta+\delta^{2},$

for $\delta>0$ and $p$ such that

$\log n\gg\log(1/np)\quad\text{ and }\quad np\ll\sqrt{\frac{\log n}{\log\log
n}},$

where

$\mathfrak{L}_{p}:=\frac{\log n}{\log\log n-\log(np)}$

(they derive both upper and lower tail large deviations for the joint
distribution of an $O(1)$ extreme eigenvalues).

Before moving further let us add that the typical behavior of the spectral
radius of $\mathbb{G}(n,p)$ was established by Krivelevich and Sudakov [29]:

$\lambda(\mathbb{G}(n,p))=(1+o(1))\max\left\\{\sqrt{\Delta(\mathbb{G}(n,p))},np\right\\},\quad\text{
almost surely},$

where for a graph ${\sf G}$ the notation $\Delta({\sf G})$ is used to denote
its maximum degree (the typical behavior of extreme eigenvalues has been
extended to the inhomogeneous setting by [13, 14]). This together with results
on the typical value of $\Delta(\mathbb{G}(n,p))$ (cf. [16, Lemma 2.2])
demonstrates that there is a change of behavior of the typical value of the
spectral radius of $\mathbb{G}(n,p)$ depending on whether $np\ll\sqrt{\log
n/\log\log n}/n$ or $np\gg\sqrt{\log n/\log\log n}/n$. In the former regime,
$\lambda(\mathbb{G}(n,p))=(1+o(1))\sqrt{\mathfrak{L}_{p}}$, while in the
latter regime $\lambda(\mathbb{G}(n,p))=(1+o(1))np$, almost surely. This
explains the difference between the description of the upper tail events in
(1.1) and (1.2).

In this paper we will derive large deviations of the spectral radius in the
intermediate regime of sparsity, i.e. for $p$ such that

(1.3) $\sqrt{\frac{\log n}{\log\log n}}\ll np\lesssim n^{1/2-o(1)}.$

Therefore, the results of this paper together with [15, 16, 22] resolve the
upper tail large deviations for the spectral radius of eigenvalues in the
entire sparse regime, except for a couple of boundary cases. Let us now
highlight some of the key consequences, and similarities and differences with
(1.1) and (1.2), of the large deviations results obtained in this article.

Towards this end, let us point out to the reader that one can conclude from
(1.1) that the large deviations probability of the upper tail event for
$\lambda(\mathbb{G}(n,p))$, in the regime $n^{-1/2}\ll p\ll 1$, equals,
asymptotically, to that of planting either a clique or a hub of appropriate
sizes. It is widely believed that conditioned on the upper tail event of
$\lambda(\mathbb{G}(n,p))$ the graph $\mathbb{G}(n,p)$ should typically
contain either an almost clique or an almost hub (the reader is referred to
[27, Section 1.3] for a precise definition of these structures). Since
localized structures (i.e. subgraphs that are “microscopic” in size) are
responsible for the large deviation event, in the literature this is termed as
the localization phenomenon. On the contrary, in (1.2) the upper tail large
deviation of $\lambda(\mathbb{G}(n,p))$ is given by the same for
$\Delta(\mathbb{G}(n,p))$. Moreover, it follows from [16, Eqn. (3.6)] that
conditioned on the upper tail event of $\lambda(\mathbb{G}(n,p))$, typically
one has that
$\Delta(\mathbb{G}(n,p))\geqslant(1+\delta)^{2}\mathfrak{L}_{p}(1-o(1))$.

In this paper we see a large deviation phenomenon which can be described as an
amalgamation of the above two behaviors. In particular, for $p$ such that
(1.3) holds and $np\gg n^{1/3}$ we derive that the $\log$-probability of the
upper tail of the spectral radius is same as, upon ignoring smaller order
terms, equals to that of planting a clique on $\lceil(1+\delta)np\rceil$
vertices, while if $np\ll n^{1/3}$ and (1.3) hold then the same equals to that
of the existence of a vertex with degree greater than
$(1+\delta)^{2}n^{2}p^{2}$. See Theorem 1.1 below.

Perhaps, at the very first glance, the transition of this large deviation
behavior at $p\asymp n^{-2/3}$ may seem surprising. However, it may be
observed the $\log$-large deviation probability should be at least as large as
the maximum of the $\log$-probabilities of the two events described above (in
Theorem 1.1 we show that this is also the upper bound, upon ignoring smaller
order terms). For $p\ll n^{-2/3}$ the probability of the second event
dominates that of the first, and hence the phenomenon described above. It is
also worth noting that the second event ceases to be a viable option if $p\gg
n^{-1/2}$ and therefore one does not see it appearing in (1.1).

The reader may be tempted to interpret the second scenario (described above)
as planting a high degree vertex. However, the Erdős-Rényi model being a
probability measure on the set of edges the localized structure responsible
for the large deviation should be viewed as the star graph formed by the one
neighborhood of the high degree vertex. Since that star graph depends on the
configuration of $\mathbb{G}(n,p)$, and thus random, this localized structure
is a non-planted structure. Thus we see the emergence of a non-planted
localized structure for $p$ such that $np\ll n^{1/3}$ and (1.3) hold. See
section 1.2 for a precise formulation of the notions of planted and non-
planted structures.

Let us also add that whenever $\log(np)\gtrsim\log n$, a large atypical value
of the spectral radius produces the same for the homomorphism counts of
$C_{2t}$, the cycle graph on $2t$ vertices, for large $t$. Using this
observation, we derive the upper bound on the large deviation probability in
that range of $p$. Therefore, in the light of the above discussion, it is not
surprising that we also observe a transition from planted localized structure
to a non-planted one. However, this time the threshold depends on $t$, see
Theorem 1.5. It is worth mentioning that Theorem 1.5 together with [8] show
that in a certain regime of sparsity the large deviation rate functions for
the upper tail of subgraph counts and homomorphism counts for $C_{2t}$ differ
but the large deviation speeds of these two events remain the same. This
difference in the rate function is probably due to lack of low complexity of
the gradient of the homomorphism count function in the above mentioned regime
of $p$. See Section 1.2 for further discussions.

###  1.1. Main results

The following is the main result on the upper tail large deviations of
$\lambda(\mathbb{G}(n,p))$.

######  Theorem 1.1.

Fix $\delta>0$.

  1. (a)

Let $p\in(0,1)$ be such that

(1.4) $np\gg\sqrt{\frac{\log n}{\log\log n}}\quad\text{ and
}\quad\log(np)\ll\log(1/p).$

Then

(1.5)
$\lim_{n\to\infty}-\frac{\log\mathbb{P}\left(\lambda(\mathbb{G}(n,p))\geqslant(1+\delta)np\right)}{n^{2}p^{2}\log(np)}=(1+\delta)^{2}.$

  2. (b)

Let $p\in(0,1)$ be such that

(1.6) $\lim_{n\to\infty}\frac{\log(1/p)}{\log n}=\alpha\in({1/2},1).$

Then

(1.7)
$\lim_{n\to\infty}-\frac{\log\mathbb{P}\left(\lambda(\mathbb{G}(n,p))\geqslant(1+\delta)np\right)}{n^{2}p^{2}\log(1/p)}=\min\left\\{\frac{(1-\alpha)}{\alpha},\frac{1}{2}\right\\}\cdot(1+\delta)^{2}.$

######  Remark 1.2.

The assumption (1.6) is chosen in Theorem 1.1(b) for a neater representation
of the large deviation bound. In fact, we will prove that

(1.8)
$-\log\mathbb{P}\left(\lambda(\mathbb{G}(n,p))\geqslant(1+\delta)np\right)=(1+o(1))\min\left\\{\frac{1}{2}(1+\delta)^{2}n^{2}p^{2}\log(1/p),(1+\delta)^{2}n^{2}p^{2}\log(np)\right\\},$

for $p$ satisfying

(1.9) $\log(np)\gtrsim\log n\qquad\text{ and }\qquad np\leqslant n^{1/2}(\log
n)^{-\omega(1)}.$

Notice that if $\alpha<2/3$ then the second term in the rhs of (1.7) achieves
the minimum, while for $\alpha>2/3$ the first term achieves the minimum. This
demonstrates the dichotomy of the large deviation behavior of
$\lambda(\mathbb{G}(n,p))$ mentioned above.

From the proof of (1.5) we can also derive the typical structure of
$\mathbb{G}(n,p)$ conditioned on the atypical event that its largest
eigenvalue is large. In particular, we obtain the following result. For ease
in writing, let us introduce the following notation: For $\delta,\xi>0$ we set

${\rm
UT}_{\lambda}(\delta):=\\{\lambda(\mathbb{G}(n,p))\geqslant(1+\delta)np\\}\quad\text{
and }\quad{\rm UT}_{\Delta}(\xi):=\\{\Delta(\mathbb{G}(n,p))\geqslant\xi
n^{2}p^{2}\\}$

######  Corollary 1.3.

Let $p$ satisfy (1.4). Then for any $\delta>0$ and $\chi\in(0,1)$ we have that

(1.10) $\mathbb{P}\left({\rm UT}_{\Delta}((1+\delta)^{2}(1-\chi))\mid{\rm
UT}_{\lambda}(\delta)\right)\to 1,\text{ as }n\to\infty.$

Observe that Corollary 1.3 treats the sparsity regime (1.4) and shows that in
that regime the upper tail large deviation event of the largest eigenvalue is
(primarily) due to the presence of a very large degree. We expect that an
appropriate analogue of Corollary 1.3 should hold for the entire regime (1.3).
See Section 1.3.

The proof of Theorem 1.1(b) hinges on understanding the upper tail large
deviations of the homomorphism counts of even cycles in Erdős-Rényi graphs.
First let us provide necessary definitions.

######  Definition 1.4 (Homomorphism counts and labelled copies).

Given graphs $H$ and ${\sf G}$ we write ${\rm Hom}(H,{\sf G})$ to denote the
number of homomorphisms of $H$ into ${\sf G}$. That is,

(1.11) ${\rm Hom}(H,{\sf G}):=\sum_{\varphi:V(H)\mapsto V({\sf
G})}\prod_{{\bm{e}}=(x,y)\in E(H)}a^{\sf G}_{\varphi(x),\varphi(y)},$

where the sum runs over all maps $\varphi$ from $V(H)$ to $V({\sf G})$ and
$\\{a^{\sf G}_{u,v}\\}$ are the entries of the adjacency matrix of ${\sf G}$.

There is a closely related notion to the homomorphism counts, known as the
number labelled copies of $H$ in ${\sf G}$, which is defined as follows:

$N(H,{\sf G}):=\sum_{\varphi:V(H)\hookrightarrow V({\sf
G})}\prod_{{\bm{e}}=(x,y)\in E(H)}a^{\sf G}_{\varphi(x),\varphi(y)}.$

Here the sum is over all injective maps.

Below is the result on the upper tail large deviations of homomorphism counts
of $C_{2t}$ in $\mathbb{G}(n,p)$.

######  Theorem 1.5.

Fix $t\geqslant 3$ and let $p$ be such that

(1.12) $n^{t+1}p^{t}\ll n^{2t}p^{2t}.$

Then

$\mathbb{E}[{\rm Hom}(C_{2t},\mathbb{G}(n,p))]=(1+o(1))n^{2t}p^{2t}.$

If additionally $p$ satisfies (1.6) then, for any $\widehat{\delta}>0$ we have

(1.13) $\lim_{n\to\infty}-\frac{\log\mathbb{P}\left({\rm
Hom}(C_{2t},\mathbb{G}(n,p))\geqslant(1+\widehat{\delta})n^{2t}p^{2t}\right)}{n^{2}p^{2}\log(1/p)}=\frac{1}{2}\widehat{\delta}^{1/t}\cdot\min\left\\{2^{1-1/t}\cdot\frac{1-\alpha}{\alpha},1\right\\}.$

The case $t=2$ is excluded from Theorem 1.5, as for $t=2$ there is no $p$
satisfying (1.12). Let us also add that, similar to (1.7), one also sees a
dichotomous large deviations behavior (1.13).

Although we do not investigate whether the large deviations probabilities in
Theorems 1.1 and 1.5 admit mean-field approximations. It seems plausible to
predict that this should be the case. See Section 1.2 for a further discussion
on this.

######  Remark 1.6.

While proving Theorem 1.5 we will work with a slightly more general assumption
than the one in (1.6). In particular, we will show that for any $p$ such that

(1.14) $n^{t+1}p^{t}\ll n^{2t}p^{2t}\quad\text{ and }\quad p\leqslant
n^{-1/2}(\log n)^{-\omega(1)},$

and any $t\geqslant 3$ fixed, we have

(1.15) $-\log\mathbb{P}\left({\rm
Hom}(C_{2t},\mathbb{G}(n,p))\geqslant(1+\widehat{\delta})n^{2t}p^{2t}\right)\\\
=(1+o(1))\min\left\\{\frac{1}{2}\widehat{\delta}^{1/t}n^{2}p^{2}\log(1/p),\left(\frac{\widehat{\delta}}{2}\right)^{1/t}n^{2}p^{2}\log(np)\right\\}.$

From this, under the additional assumption (1.6) the large deviations result
in (1.13) is immediate.

The next result identifies the typical behavior of $\mathbb{G}(n,p)$
conditioned on the upper tail of ${\rm Hom}(C_{2t},\mathbb{G}(n,p))$.

######  Corollary 1.7.

Consider the same setup as in Theorem 1.5. Additionally, assume that $\alpha$
in (1.6) is such that $2^{1-1/t}\cdot(1-\alpha)/\alpha<1$. Then, for any
$\chi>0$,

$\mathbb{P}\left({\rm UT}_{\Delta}((\widehat{\delta}/2)^{1/t}(1-\chi))\mid{\rm
UT}_{t}(\widehat{\delta})\right)\to 0,\quad\text{ as }n\to\infty,$

where, for any $\delta^{\prime}>0$,

${\rm UT}_{t}(\delta^{\prime}):=\left\\{{\rm
Hom}(C_{2t},\mathbb{G}(n,p))\geqslant(1+\delta^{\prime})n^{2t}p^{2t}\right\\}.$

###  1.2. Connection to the Naïve mean-field approximation

For a function $h:\\{0,1\\}^{N}\mapsto\mathbb{R}$ and the uniform measure
$\mu$ on ${\sf C}_{N}:=\\{0,1\\}^{N}$, the Gibbs variational principle states
that

(1.16) $Z_{h}:=\log\int e^{h}d\mu=\sup_{\nu}\left\\{\int hd\nu-
D_{KL}(\nu\|\mu)\right\\},$

where $D_{KL}(\cdot\|\cdot)$ denotes the Kulback-Leibler divergence and the
supremum in (1.16) is taken over all probability measures $\nu$ on ${\sf
C}_{N}$. If the supremum in (1.16) is replaced by product measures on ${\sf
C}_{N}$, in statistical mechanics, the approximation is termed as the naïve
mean-field approximation. Over the past ten years there have been several
works, in different settings, attempting to find sufficient conditions on
$h(\cdot)$, e.g. appropriate low-complexity conditions on the (discrete)
gradient of $h(\cdot)$, such that the mean-field approximation is
asymptotically tight for the log-partition function $Z_{h}$ (see [5, 7, 9, 20,
24, 36]).

A related problem, which is probably the motivation of the seminal work [20],
is to derive asymptotics of the probability
$\\{f\geqslant(1+\delta)\mathbb{E}_{\mu_{p}}[f]\\}$, where
$f:[0,1]^{N}\mapsto\mathbb{R}$ and $\mu_{p}$ is the product of $N$ i.i.d.
$\operatorname{Ber}(p)$ measures, with $p\to 0$ as $N\to\infty$. For this
setup, under the low-complexity gradient assumption, the mean-field
approximation leads to the following conclusion:

(1.17)
$\log\mathbb{P}(f\geqslant(1+\delta)\mathbb{E}_{\mu_{p}}[f])=-(1+o(1))\Phi_{p}(f,\delta),$

where

(1.18)
$\Phi_{p}(f,\delta):=\inf\left\\{I_{p}({\bm{\xi}}):{\bm{\xi}}\in[0,1]^{N}\text{
and }f({\bm{\xi}})\geqslant(1+\delta)\mathbb{E}_{\mu_{p}}[f]\right\\},$
$I_{p}({\bm{\xi}}):=\sum_{i=1}^{N}I_{p}(\xi_{i}),\quad{\bm{\xi}}:=(\xi_{1},\xi_{2},\ldots,\xi_{N}),\quad\text{and}\quad
I_{p}(x):=x\log\frac{x}{p}+(1-x)\log\frac{1-x}{1-p}\text{ for }x\in[0,1],$

with the convention $0\log 0=0$. Functions that are of interests and fit into
this framework include $N({\sf H},\mathbb{G}(n,p))$ and ${\rm Hom}({\sf
H},\mathbb{G}(n,p))$, for ${\sf H}\subset K_{n}$, and
$\lambda(\mathbb{G}(n,p))$ (set $N=\binom{n}{2}$ and identify $\binom{n}{2}$
possible edges of $\mathbb{G}(n,p)$ to $[N]$).

Once (1.17) has been established the task then boils down to analyzing the
minimizer of the variational problem in (1.18). This two-step scheme has been
successfully employed to derive large deviations for Homomorphism counts and
the largest eigenvalue in sparse $\mathbb{G}(n,p)$, where (1.17) has been
shown to hold in [5, 20, 22, 23, 24], for various ranges of sparsity, and
related variational problems have been solved in [15, 17, 34]. It has been
further observed that, in the sparsity regime considered there, any minimizer
${\bm{\xi}}_{\star}$ of these variational problems satisfy
${\bm{\xi}}_{\star}\in\\{p,1\\}^{N}$. Therefore, such ${\bm{\xi}}_{\star}$ are
also the minimizers of the following simpler version of the variational
problem (1.18):

(1.19) $\widehat{\Phi}_{p}(f,\delta):=\inf\left\\{e({\sf G})\log(1/p):{\sf
G}\subset K_{n}\text{ and }\mathbb{E}_{\sf
G}[f]\geqslant(1+\delta)\mathbb{E}_{\mu_{p}}[f]\right\\},$

where $\mathbb{E}_{{\sf
G}}[f]=\mathbb{E}_{\mu_{p}}[f({\bm{\zeta}})|\zeta_{\upalpha}=1;\upalpha\in
E({\sf G})]$ and $E({\sf G})$ is given by
$\mathscr{P}_{\bm{\xi}}:=\\{\upalpha\in[N]:\xi_{\upalpha}=1\\}$.

This leads us to the definition of planted structures. Note that for
${\bm{\xi}}\in[0,1]^{N}$ the probability measure
$\mu_{\bm{\xi}}:=\otimes_{i=1}^{N}\operatorname{Ber}(\xi_{i})$ can be
naturally associated to the inhomogeneous Erdős-Rényi graph
$\mathbb{G}(n,{\bm{\xi}})$ with edge probabilities given by $\xi_{\upalpha}$
for $\upalpha\in[N]$. Therefore, the edges $\mathscr{P}_{\bm{\xi}}$ are
present with probability one, and hence planted, in
$\mathbb{G}(n,{\bm{\xi}})$. This motivates the nomenclature ‘planted’ and the
structure, such as the clique and the hub, is determined by the set of edges
$\mathscr{P}_{\bm{\xi}}$.

On the other hand, if for a ${\bm{\xi}}$ the set of edges
$\mathscr{P}_{\bm{\xi}}=\varnothing$ (or of ‘insignificant’ cardinality) then
we term such a ${\bm{\xi}}$, or equivalently $\mathbb{G}(n,{\bm{\xi}})$, to be
‘non-planted’, and the (random) structure associated to such a random graph
will be said to be determined by the edge set
$\\{\upalpha:\xi_{\upalpha}>p\\}$. To illustrate this let consider
$\widehat{\bm{\xi}}$ such that $\widehat{\xi}_{1,j}=p+\uptau np^{2}$, for some
$\uptau>0$, and $\widehat{\xi}_{i,j}=p$ for the rest of the indices ($p\ll
n^{-1/2}$). Observe that the random structure associated to
$\widehat{\bm{\xi}}$ is the random star graph formed by the one-neighborhood
of vertex one. Moreover, it can be verified that
$\mathbb{E}_{\mu_{\widehat{\bm{\xi}}}}[f]\geqslant(1+\delta)\mathbb{E}_{\mu_{p}}[f]$
for $f={\rm Hom}(C_{2t},\mathbb{G}(n,p))$ and $\lambda(\mathbb{G}(n,p))$ with
$\uptau=(\delta/2)^{1/t}$ and $(1+\delta)^{2}$, respectively. Further notice
that, with the above choice of $\uptau$, $I_{p}(\widehat{\xi})$ equals the
second terms in the rhs-s of (1.8) and (1.15) (set $\widehat{\delta}=\delta$).
Therefore, it does not rule out that the rhs-s of (1.8) and (1.15) equal to
the solution of the following variational problem

(1.20)
$\Psi_{p}(f,\delta):=\inf\left\\{I_{p}({\bm{\xi}}):{\bm{\xi}}\in[0,1]^{N}\text{
and
}\mathbb{E}_{\mu_{\bm{\xi}}}[f]\geqslant(1+\delta)\mathbb{E}_{\mu_{p}}[f]\right\\}.$

Let us also make the following two observations:

  1. (i)

From the proof of [15, Theorem 1.2] it follows that for
$f=\lambda(\mathbb{G}(n,p))$ and $p$ such that $np\gg 1$ the first term in the
rhs of (1.8) equals $(1+o(1))\Phi_{p}(f,\delta)$.

  2. (ii)

If $np\ll n^{1/3}$ then the second term in (1.8) is strictly smaller than the
first term. Therefore, in that regime $-\log\mathbb{P}({\rm
UT}_{t}(\delta))>(1+o(1))\Phi_{p}(f,\delta)$. Similar comments apply for
$f={\rm Hom}(C_{2t},\mathbb{G}(n,p))$.

These observations may suggest that in the sparsity regime described above the
mean-field approximation to the large deviation probability no longer holds.
However, in the absence of ‘low-complexity gradient’ criterion, the right
formulation should probably be to replace $\Phi_{p}(f,\delta)$ by
$\Psi_{p}(f,\delta)$ in (1.17).

###  1.3. Extensions and open problems

In the light of the discussion in Section 1.2 it is plausible to speculate
that the rhs-s of (1.8) and (1.15) equal to $(1+o(1))\Psi_{p}(f,\delta)$ for
$f=\lambda(\mathbb{G}(n,p))$ and ${\rm Hom}(C_{2t},\mathbb{G}(n,p))$ (with
$\widehat{\delta}=\delta$), respectively. This would then validate that the
mean-field approximation continues to hold in the sparsity regime (1.3) and
(1.14), respectively.

Another natural question would be to extend Theorem 1.5 for all regular
graphs. It would be interesting to check if there is a sparsity regime where
the large deviation rate functions for the upper tails of ${\rm
Hom}(H,\mathbb{G}(n,p))$ and $N(H,\mathbb{G}(n,p))$ are different, but the
speed is the same. We expect this behavior to depend on whether $H$ is
bipartite or not. For example, preliminary computations show that $H=C_{2t+1}$
upper tails of ${\rm Hom}(H,\mathbb{G}(n,p))$ and $N(H,\mathbb{G}(n,p))$ share
the same large deviation speed and rate function for all $p$ such that
$np\geqslant(\log n)^{C}$, for some $C<\infty$. It remains to be investigated
whether the same should hold in the entire ‘localized regime’.

Observe that Theorem 1.1 leaves out two boundary cases. If $np\asymp\sqrt{\log
n/\log\log n}$ it is natural to predict the large deviation speed to be $\log
n$ and the rate function should be some combination of the rate function in
Theorem 1.1(a) and [16, Theorem 1.1]. We expect Theorem 1.1(b) to extend for
$p$ such that $n^{-1/2-o(1)}\leqslant np\ll n^{1/2}$. It seems that one can
combine the ideas of Lemma 3.6 and those in [27, Section 7] to treat this
regime. However, for the sake of brevity and clarity of the presentation we
have not attempted this here. Next, in the regime $p\asymp n^{-1/2}$ one is
expected to encounter some integrality issue, as was seen in [27, Theorem
1.7].

Corollary 1.3 provides a description of the typical behavior of
$\mathbb{G}(n,p)$ conditioned on ${\rm UT}_{\lambda}(\delta)$ in the regime
(1.4). The same behavior should extend for $np\ll n^{1/3}$. See Remark 4.4. It
is expected that in the regime $n^{1/3}\ll np\ll n^{1/2}$ the graph
$\mathbb{G}(n,p)$, conditioned on ${\rm UT}_{\lambda}(\delta)$, should
typically contain an almost-clique of an appropriate size. Same is believed to
hold for ${\rm Hom}(C_{2t},\mathbb{G}(n,p))$ for $p$ in the regime not covered
in Corollary 1.7. This would require analyzing the near-minimizers of (1.18)
(or (1.19)). See the discussion in [27, Section 10] in this regard.

Another related problem is the large deviations of the largest eigenvalue of
diluted Wigner matrices, i.e. matrices of the form $W_{n}\circ B_{n}$, where
$W_{n}$ is a Wigner matrix and $B_{n}$ is a symmetric matrix with i.i.d.
$\operatorname{Ber}(p)$ entries on the diagonal and above the diagonal
positions, and $p\to 0$ with $n\to\infty$. The case of $p\asymp 1/n$ and the
entries of $W_{n}$ are standard Gaussian was recently dealt in [25]. This
problem is closely related to the problem of studying large deviations of the
second largest eigenvalue of the adjacency matrix $\mathbb{G}(n,p)$. This is a
work in progress with Fanny Augeri.

###  1.4. Outline of the proof

Proofs of Theorem 1.1(a) and (b) proceed via two completely different
approaches. To prove Theorem 1.1(a) we split the random graph
$\mathbb{G}(n,p)$ into vertices of high, moderate, and low degrees (see
Definition 2.3). At a high level, such a decomposition of $\mathbb{G}(n,p)$ is
similar to those in [16, 29]. However, the threshold used to define such
subsets of vertices, as well as the arguments employed here to prove Theorem
1.1(a) are completely different from those in [16, 29]. For example, the key
ideas in [16] are to show that (i) there are no ‘large’ cycles, and (ii) any
vertex is not incident to too many edge disjoint ‘small’ cycles, at the large
deviation scale. These do not hold for the entirety of the regime (1.4).
Hence, we need to use other ideas.

Bounding the spectral radius of different parts of $\mathbb{G}(n,p)$ require
different approaches. Let us highlight some of them. In Lemma 2.8 we show that
it is unlikely, at the large deviations scale, to have a connected component
${\sf G}$ of $\mathbb{G}(n,p)$ such that all its vertices are of moderate
degree and $v({\sf G})\gg np\log(np)$. Using this and the fact that
$\lambda({\sf G})\leqslant\sqrt{2e({\sf G})}$ we then argue that the subgraph
of $\mathbb{G}(n,p)$ consisting of moderate degree vertices has a negligible
spectral radius.

To bound the spectral radius of a certain subgraph of $\mathbb{G}(n,p)$ such
that all its vertices are of low degree (see the proof of Theorem 1.1(a) for a
precise definition of this subgraph) we employ the following ‘bootstrap’
strategy: using a bound on the number of high degree vertices (see Lemma 2.7)
we first show that for such a graph, say $\widetilde{\sf G}$, at the large
deviations scale, one must have that $e(\widetilde{\sf G})\leqslant(np)^{C}$,
for some absolute constant $C<\infty$. Then, we argue that if
$\lambda(\widetilde{\sf G})$ is non-negligible (i.e. $\gtrsim np$) then, upon
excluding an event of negligible probability, one can procure a subgraph
$\widetilde{\sf G}^{\prime}\subset\widetilde{\sf G}$ such that
$e(\widetilde{\sf G}^{\prime})\leqslant(np)^{C-1}$ and $\lambda(\widetilde{\sf
G}^{\prime})$ is still non-negligible (see Lemma 2.9). We iterate this
argument to finally obtain a subgraph $\widetilde{\sf
G}_{0}\subset\widetilde{\sf G}$, with minimum degree two, such that
$e(\widetilde{\sf G}_{0})\leqslant n^{2}p^{2}$ and $\lambda(\widetilde{\sf
G}_{0})\gtrsim np$. Applying Binomial tail probability bound we then deduce
that the number of excess edges of $\widetilde{\sf G}_{0}$ (i.e.
$e(\widetilde{\sf G}_{0})-v(\widetilde{\sf G}_{0})$) should not be large, see
Lemma 2.6. By Lemma 2.2(viii) this upper bound then yields that
$\lambda(\widetilde{\sf G}_{0})/np$ must be small.

To treat the spectral radius of the bipartite subgraph of $\mathbb{G}(n,p)$
with vertex bipartition consisting of moderate and low degree vertices we use
the following idea: we apply estimates on the number of moderate degree
vertices in the two-neighborhood of any given vertex (see Lemma 2.4) and a
bound on the spectral radius of a bipartite graph (see Lemma 2.2(vii)) to
deduce that the spectral radius to be non-negligible there must be two sets of
vertices of small sizes containing too many edges between them. By the
standard bound on Binomial tail probability, and a union bound, this event
turns out to be unlikely at the large deviations scale. To treat the rest of
the parts of $\mathbb{G}(n,p)$ we employ estimates that are already mentioned
above, i.e. Lemmas 2.4, and 2.6-2.9. See Section 2 for further details.

Let us now move to describe the main ideas of the proof of Theorem 1.5. From
this Theorem 1.1(b) follows upon letting $t\to\infty$. To derive Theorem 1.5
we follow the general strategy developed in [27, 8]. However, [27, 8] deal
with the upper tail large deviations of $N(C_{2t},\mathbb{G}(n,p))$ (in fact
they cover all regular graphs), while here we are interested in that of ${\rm
Hom}(C_{2t},\mathbb{G}(n,p))$. As the large deviation results in these two
cases differ, in the sparsity regime we consider, the argument require
considerable modifications. As in [27, 8], in the first step we apply Markov’s
inequality to deduce that conditioned on ${\rm UT}_{t}(\widehat{\delta})$ the
random graph $\mathbb{G}(n,p)\supset{\sf G}$ for some ${\sf G}\subset K_{n}$
such that $e({\sf G})\lesssim n^{2}p^{2}\log(1/p)$ and the conditional
expectation of ${\rm Hom}(C_{2t},\mathbb{G}(n,p))$ given ${\sf
G}\subset\mathbb{G}(n,p)$ is at least $\widehat{\delta}(1-o(1))n^{2t}p^{2t}$,
holds with probability $1-o(1)$. The class of such graphs ${\sf G}$ will be
called pre-seed graphs (see Definition 3.1). This step allows us to reduce the
configuration space to a smaller one that is ‘responsible’ for the large
deviation event.

The next step is to reduce the configuration space further to the set
$\mathbb{G}(n,p)\supset{\sf G}$ where ${\sf G}$ runs over the set of all core
graphs (see Definition 3.5). This step was almost trivial in [8]. However, as
$\varphi$ in (1.11) is allowed to be non-injective some of the edges of
$C_{2t}$ may get mapped to the same edge in $\mathbb{G}(n,p)$, and thus the
number of independent edges at our disposal may decrease. To overcome this
challenge we introduce a notion of generating and non-generating edges and
vertices (see Definition 3.12) and perform a combinatorial analysis. See
Section 3.1.

Next, we split the set of core graphs into two further subsets: $e({\sf G})\gg
n^{2}p^{2}$ and $e({\sf G})=O(n^{2}p^{2})$. Using a simple combinatorial
argument the first subset can be shown to be unlikely at the large deviations
scale. Applying pigeonhole principle and the fact that $x\mapsto
x^{1/t}+(1-x)^{1/t},x\in[0,1],t\geqslant 2$, is strictly concave we further
deduce that there exists a splitting for any core graph ${\sf G}$ belonging to
the second subset (upon excluding a negligible number of edges) to ${\sf
G}^{\prime}$ and ${\sf G}^{\prime\prime}$ such that the number of
homomorphisms of $C_{2t}$ in at least one of them is at least
$\widehat{\delta}(1-o(1))n^{2t}p^{2t}$. Furthermore, all the vertices of ${\sf
G}^{\prime}$ are of moderately large degrees, while ${\sf G}^{\prime\prime}$
is a bipartite graph with parts $U_{1}$ and $U_{2}$ such that $\max_{u\in
U_{1}}\deg_{{\sf G}^{\prime\prime}}(u)=O(1)$, and $\min_{u\in U_{2}}\deg_{{\sf
G}^{\prime\prime}}(u)\gtrsim n^{2}p^{2}$. Using a lower bound on $e({\sf
G}^{\prime})$ and $e({\sf G}^{\prime\prime})$, and an upper bound on the
number of such graphs we complete the argument.

To prove Corollary 1.7 we need to strengthen some of the above steps. In fact,
we argue that under the set up of Corollary 1.7, conditioned on ${\rm
UT}_{t}(\widehat{\delta})$, the number of homomorphisms of $C_{2t}$ in ${\sf
G}^{\prime\prime}$ is $\widehat{\delta}(1\pm o(1))n^{2t}p^{2t}$, and $e({\sf
G}^{\prime\prime})-|U_{1}|\ll n^{2}p^{2}$, with probability $1-o(1)$. This
shows that almost all the excess homomorpshims in $\mathbb{G}(n,p)$ is due to
the stars centered at vertices of $U_{2}$, i.e. vertices with degree $\gtrsim
n^{2}p^{2}$. From this the conclusion of Corollary 1.7 follows by yet another
use of the estimate on Binomial tail probability.

###  1.5. Notation

For $x\in\mathbb{R}$ we use the standard notations $\lceil
x\rceil:=\min\\{n\in\mathbb{Z}:n\geqslant x\\}$ and $\lfloor
x\rfloor:=\max\\{n\in\mathbb{Z}:n\leqslant x\\}$. For $a,b\in\mathbb{R}$ we
let $a\vee b:=\max\\{a,b\\}$ and $a\wedge b:=\min\\{a,b\\}$. For
$N\in\mathbb{N}$ we let $[N]:=\\{1,2,\ldots,N\\}$. Given two sequences of
positive reals $\\{a_{n}\\}$ and $\\{b_{n}\\}$ we write $a_{n}\lesssim b_{n}$
to denote $\limsup_{n\to\infty}a_{n}/b_{n}<\infty$. The notation $a_{n}\gtrsim
b_{n}$ will be used to denote $\liminf_{n\to\infty}a_{n}/b_{n}>0$. We write
$a_{n}\asymp b_{n}$ if $a_{n}\lesssim b_{n}$ and $a_{n}\gtrsim b_{n}$. We
further write $a_{n}\ll b_{n}$, $b_{n}=\omega(a_{n})$, and $b_{n}\gg a_{n}$ to
denote $\lim_{n\to\infty}a_{n}/b_{n}=0$. Let $\\{a_{n}\\}$ be a sequence of
reals and $\\{b_{n}\\}$ be a sequence of positive reals then we write
$a_{n}=O(b_{n})$ if $|a_{n}|\lesssim b_{n}$, and write $a_{n}=o(b_{n})$ if
$|a_{n}|\ll b_{n}$.

The notation $K_{n}$ will denote the complete graph on $[n]$. For a graph
${\sf G}$ we write $V({\sf G})$ and $E({\sf G})$ to denote its vertex and edge
sets, respectively. We let $v({\sf G}):=|V({\sf G})|$ and $e({\sf G}):=|E({\sf
G})|$, where $|\cdot|$ is the cardinality of a set. Unless otherwise
mentioned, the set $V({\sf G})$ will be assumed to consist only non-isolated
vertices. The notation $\deg_{\sf G}(v)$ will be used to denote the degree of
a vertex $v$ in the graph ${\sf G}$. When the choice of the graph is clear
from the context, to lighten the notation we will write $\deg(v)$ instead of
$\deg_{\sf G}(v)$. We will use $\Delta({\sf G})$ and $\updelta({\sf G})$ to
denote the largest and the smallest degrees in ${\sf G}$, respectively. We
will write ${\sf G}^{\prime}\subset{\sf G}$ to denote that $V({\sf
G}^{\prime})\subset V({\sf G})$ and $E({\sf G}^{\prime})\subset E({\sf G})$.
The notation $K_{n}$ will be used to denote the complete graph on $n$
vertices. For two graphs ${\sf G},{\sf G}^{\prime}\subset K_{n}$ the graph
${\sf G}\backslash{\sf G}^{\prime}$ will be the graph induced by the edges
$E({\sf G})\backslash E({\sf G}^{\prime})$. Moreover for $S\subset V({\sf G})$
we write ${\sf G}[S]$ to denote the subgraph indued by the edges with both end
points belonging to $S$. For two disjoint subsets $U,V\subset V({\sf G})$ we
further use ${\sf G}[U,V]$ to denote the bipartite subgraph induced by edges
with one end point belonging to $U$ and the other in $V$. We will use the
shorthands $e(S):=e({\sf G}[S])$ and $e(U,V):=e({\sf G}[U,V])$. For two
vertices $u,v\in V({\sf G})$ we write $u\sim v$ to denote that they are
neighbors.

For a graph ${\sf G}$ on $\mathfrak{n}$ vertices we let $\lambda_{1}({\sf
G})\geqslant\lambda_{2}({\sf
G})\geqslant\cdots\geqslant\lambda_{\mathfrak{n}}({\sf G})$ be the eigenvalues
of its adjacency matrix arranged in a non-increasing order. To ease up the
notation, whenever there is no scope of confusion, we will write $\lambda({\sf
G})$ instead of $\lambda_{1}({\sf G})$. By a slight abuse of terminology we
will often refer $\lambda({\sf G})$ as the top/largest eigenvalue of ${\sf
G}$.

For two random variables $Y_{1}$ and $Y_{2}$ we write
$Y_{1}\stackrel{{\scriptstyle d}}{{=}}Y_{2}$ to denote that they have the same
distribution. For an event $\mathcal{A}$ the notation
$\mathcal{A}^{\complement}$ will denote its complement.

### Organization of the paper

In Section 2 we prove Theorem 1.1(a) and Corollary 1.3. Proofs of all
auxiliary estimates are in Section 2.1. In Section 3 we introduce necessary
definitions, e.g. pre-seed graphs, core graphs, etc, and state a few relevant
lemmas. Using these results we complete the proofs of Theorems 1.5 and 1.1(b).
Section 3.1 is devoted to the proof of Lemma 3.6 which allows us to move from
pre-seed graphs to core graphs. In Sections 3.2 and 3.3 we deal with core
graphs with edges $\gg n^{2}p^{2}$ and $O(n^{2}p^{2})$, respectively. Section
4 provides the proof of Corollary 1.7. In Appendix A we provide the proofs of
some non-standard bounds on the spectral radius of a graph. Finally, in
Appendix B we provide some results on core graphs that are used in Section 3.

### Acknowledgments

The author thanks Fanny Augeri for helpful discussions. This research was
carried out in part as a member of the Infosys-Chandrasekharan Virtual Center
for Random Geometry, supported by a grant from the Infosys Foundation. The
author acknowledges the support of the Department of Atomic Energy, Government
of India, under project no. RTI4001. The research was also partially supported
by a MATRICS Grant (MTR/2019/ 001105) and a Start-up Research Grant
(SRG/2019/001376) from Science and Engineering Research Board of Govt. of
India, and an Infosys–ICTS Excellence Grant.

##  2\. Proof of Theorem 1.1(a)

In this section we prove Theorem 1.1 for all $p$ satisfying (1.4). First let
us derive the large deviation lower bound. This will be straightforward. To
derive that bound we will need estimates on the binomial upper tail
probability. We use the following result.

######  Lemma 2.1 ([3, Lemma 4.7.2]).

Let $X\stackrel{{\scriptstyle d}}{{=}}\operatorname{Bin}(N,s)$ for some
$N\in\mathbb{N}$ and $s\in(0,1)$. Fix any $\uplambda\in(s,1)$. Then

$\frac{\exp(-NI_{s}(\uplambda))}{\sqrt{8N\uplambda(1-\uplambda)}}\leqslant\mathbb{P}(X\geqslant\uplambda
N)\leqslant\exp(-NI_{s}(\uplambda)),$

where $I_{s}(\cdot)$ is the binary relative entropy function. That is,

(2.1)
$I_{s}(\uplambda):=\uplambda\log\frac{\uplambda}{s}+(1-\uplambda)\log\frac{1-\uplambda}{1-s}.$

For any $\gamma>0$ such that $(1+\gamma)s\leqslant 1$ one can also derive from
above the following well known Chernoff bound.

(2.2)
$\mathbb{P}(\operatorname{Bin}(N,s)\geqslant(1+\gamma)Ns)\leqslant\exp\left(-\frac{\gamma^{2}}{2+\gamma}Ns\right).$

The following lemma provides bounds on the top eigenvalue of a graph in terms
of various graph parameters. It will be used in the proof of Theorem 1.1, for
the lower bound and more extensively for the upper bound.

######  Lemma 2.2.

Let ${\sf G}$ be a graph with ${\bm{e}}$ edges, maximum degree $\Delta$, and
minimum degree $\updelta$. Then the following bounds hold for the top
eigenvalue $\lambda({\sf G})$ of the adjacency matrix of ${\sf G}$.

  1. (i)

$\sqrt{\Delta}\leqslant\lambda({\sf
G})\leqslant\min\\{\Delta,\sqrt{2{\bm{e}}}\\}.$

  2. (ii)

If $E({\sf G})=\cup_{i}E({\sf G}_{i})$ then $\lambda({\sf
G})\leqslant\sum_{i}\lambda({\sf G}_{i})$. Additionally, if the collection of
graphs $\\{{\sf G}_{i}\\}$ are vertex disjoint then $\lambda({\sf
G})=\max_{i}\lambda({\sf G}_{i})$.

  3. (iii)

If ${\sf G}$ is a forest then $\lambda({\sf G})\leqslant 2\sqrt{\Delta-1}$.

  4. (iv)

If ${\sf G}$ is a star then $\lambda({\sf G})=\sqrt{\Delta}$.

  5. (v)

If ${\sf G}$ is a bipartite graph such that the degrees on both sides of the
bipartition are bounded by $\Delta_{1}$ and $\Delta_{2}$ respectively, then
$\lambda({\sf G})\leqslant\sqrt{\Delta_{1}\Delta_{2}}$.

  6. (vi)

Let ${\sf G}^{\prime}\subset{\sf G}$ then $\lambda({\sf
G}^{\prime})\leqslant\lambda({\sf G})$.

  7. (vii)

Let ${\sf G}$ be a bipartite graph with vertex bipartition $V_{1}$ and
$V_{2}$. That is, all its edges are between $V_{1}$ and $V_{2}$. Then

$\lambda({\sf G})\leqslant\min_{i\in\\{1,2\\}}\max_{v\in
V_{i}}\sqrt{\sum_{u:u\sim v}\deg_{\sf G}(u)}.$

  8. (viii)

If ${\sf G}$ is a graph with $\updelta\geqslant 2$ then we have

$\lambda({\sf G})\leqslant\sqrt{2({\bm{e}}-{\bm{v}})+\Delta+2},$

where ${\bm{v}}$ is the number of vertices in ${\sf G}$.

Most of the bounds in Lemma 2.2 are well known. The proofs of the rest are
provided in Appendix A.

###### Proof of Theorem 1.1 (lower bound) for $p$ satisfying (1.4).

By Lemma 2.2(i) we have that

(2.3) $\mathbb{P}({\rm UT}_{\lambda}(\delta))\geqslant\mathbb{P}({\rm
UT}_{\Delta}((1+\delta)^{2}))\geqslant\mathbb{P}(\deg_{\mathbb{G}(n,p)}(v)\geqslant(1+\delta)^{2}n^{2}p^{2}),$

where $v\in[n]$ is an arbitrarily chosen vertex. Now the desired lower bound
follows upon noting that

(2.4)
$I_{s}(\uplambda)=\uplambda\log\frac{\uplambda}{s}\cdot(1+o(1)),\quad\text{
for }0<s\ll\uplambda\ll 1,$

where $I_{s}(\uplambda)$ is as in (2.1). ∎

The rest of this section is devoted to the proof of the upper bound. As
outlined in Section 1.4 this will require us to split the graph appropriately
and show that the spectral radius of the random subgraph obtained upon
removing the one neighborhoods of high degree vertices is small in the large
deviations scale.

######  Definition 2.3 (Decomposition of the graph).

Fix $\eta,\varepsilon\in(0,1/4)$. Given any graph ${\sf G}$ (possibly random)
with vertex set $V({\sf G})\subset[n]$ we define the vertices of high, low,
and moderate degrees, to be denoted by $V_{H}({\sf G}),V_{L}({\sf G})$, and
$V_{M}({\sf G})$, respectively, as follows:

$V_{H}({\sf G}):=\left\\{v\in V({\sf G}):\deg_{\sf
G}(v)\geqslant\varpi_{n}\right\\},$

where

(2.5) $\varpi_{n}:=\left\\{\begin{array}[]{ll}np\cdot\sqrt{\frac{\log
n}{\log\log n}},&\mbox{ if }\sqrt{\frac{\log n}{\log\log n}}\ll
np\leqslant(\log n)^{1-\eta/2},\\\ (np)^{1+\eta}&\mbox{ if }(\log
n)^{1-\eta/2}\leqslant np\mbox{ and }\log np\ll\log n,\end{array}\right.$
$V_{L}({\sf G}):=\left\\{v\in V({\sf G}):\deg_{\sf
G}(v)\leqslant(1+\delta(1-\varepsilon))np\right\\},$

and $V_{M}({\sf G}):=V({\sf G})\backslash(V_{H}\cup V_{L})$. When the graph is
clear from the context we suppress the dependence in ${\sf G}$ and write
$V_{H},V_{M}$, and $V_{L}$. We then let $V_{{L}_{1}}$ to be the subset of
$V_{L}$ that are connected to $V_{H}$. That is,

$V_{{L}_{1}}:=\left\\{v\in V_{L}:\exists\,u\in V_{H}\text{ such that }(u,v)\in
E({\sf G})\right\\}.$

Denote $V_{{L}_{2}}:=V_{L}\backslash V_{{L}_{1}}$. Now we describe the
necessary decomposition of the graph ${\sf G}$:

  * •

We let ${\sf G}_{H}:={\sf G}[V_{H}]$, ${\sf G}_{M}:={\sf G}[V_{M}]$, ${\sf
G}_{{L}_{1}}:={\sf G}[V_{L_{1}}]$, and ${\sf G}_{{L}_{2}}:={\sf
G}[V_{L_{2}}]$.

  * •

Define ${\sf G}_{{HM}}:={\sf G}[V_{H},V_{M}]$. Similarly define ${\sf
G}_{{L}_{1}{L}_{2}}$ and ${\sf G}_{ML}$.

  * •

Denote $\widehat{\sf G}_{{L_{1}L_{2}}}$ and $\widehat{\sf G}_{L_{1}}$ be the
two cores of ${\sf G}_{L_{1}L_{2}}$ and ${\sf G}_{L_{1}}$, respectively. Set
${\sf F}_{{L_{1}L_{2}}}:={\sf G}_{{L_{1}L_{2}}}\backslash\widehat{\sf
G}_{{L_{1}L_{2}}}$ and ${\sf F}_{L_{1}}:={\sf G}_{L_{1}}\backslash\widehat{\sf
G}_{L_{1}}$. Note that by definition ${F}_{{L_{1}L_{2}}}$ and ${\sf
F}_{L_{1}}$ are forests.

  * •

Similarly as above we define ${\sf G}_{{H}{L}_{1}}$, $\widehat{\sf
G}_{{H}{L}_{1}}$, and ${\sf F}_{{H}{L}_{1}}$.

  * •

We further decompose the forest ${\sf F}_{{H}{L}_{1}}$ into two subgraphs. We
let $\widetilde{\sf F}_{{H}{L}_{1}}$ to be the subgraph spanned by the edges
that are incident to vertices $u\in V_{L_{1}}$ that have degree one in ${\sf
F}_{HL_{1}}$. Note that by construction $\widetilde{\sf F}_{HL_{1}}$ is a
vertex disjoint union of stars with center vertices belonging to $V_{H}$.
Finally set $\widehat{\sf F}_{HL_{1}}:={\sf F}_{HL}\backslash\widetilde{\sf
F}_{HL_{1}}$.

Equipped with the above decomposition of a graph we now state a few lemmas
that help us to prove the large deviations upper bound. The first lemma yields
a bound on the number of moderate and high degree vertices in the two
neighborhood of any given vertex. To state this lemma let us introduce the
following notation.

For any $v\in[n]$ we let

$\mathcal{N}_{M}(v,{\sf G}):=\\{u\in[n]:(u,v)\in E({\sf G})\mbox{ and }u\in
V_{M}({\sf G})\\}$

and

$\mathcal{N}_{M}^{(2)}(v,{\sf G}):=\\{u\in[n]:{\rm dist}_{\sf G}(u,v)\leqslant
2\text{ and }u\in V_{M}({\sf G})\\},$

where ${\rm dist}_{\sf G}(\cdot,\cdot)$ denotes the graph distance. We
similarly define $\mathcal{N}_{H}(v,{\sf G})$ and
$\mathcal{N}_{H}^{(2)}(v,{\sf G})$. When ${\sf G}=\mathbb{G}(n,p)$ (which will
be the case in the most of this section that follows), to ease the notation,
we will drop the dependence on ${\sf G}$ and write $\mathcal{N}_{M}(v)$,
$\mathcal{N}_{H}(v)$ etc. This convention will be adopted also for other
notations throughout this section.

######  Lemma 2.4.

Let $p$ satisfy (1.4). Then for any $\delta>0$ there exists $C_{1}<\infty$,
depending only on $\delta$, such that

(2.6) $\mathbb{P}(\exists v\in[n]:|\mathcal{N}_{M}^{(2)}(v)|\geqslant
C_{1}np\log(np))\leqslant\exp(-2(1+\delta)^{2}n^{2}p^{2}\log(np))$

and

(2.7) $\lim_{n\to\infty}\frac{\log\mathbb{P}(\exists
v\in[n]:|\mathcal{N}_{H}^{(2)}(v)|\geqslant(np)^{1-\eta/2})}{n^{2}p^{2}\log(np)}=-\infty.$

######  Remark 2.5.

Note that by definition $\mathcal{N}_{M}(v)\subset\mathcal{N}_{M}^{(2)}(v)$
and $\mathcal{N}_{H}(v)\subset\mathcal{N}_{H}^{(2)}(v)$. Therefore, the bounds
(2.6) and (2.7) continue to hold when $\mathcal{N}_{M}^{(2)}(v)$ and
$\mathcal{N}_{H}^{(2)}(v)$ are replaced by $\mathcal{N}_{M}(v)$ and
$\mathcal{N}_{H}(v)$, respectively.

Next, fix $C_{2}<\infty$ and $\gamma>0$. Let

$\mathcal{A}_{1}:=\left\\{\exists S\subset[n]:|S|\leqslant n^{2}p^{2},\text{
and }e(S)\geqslant|S|+\gamma n^{2}p^{2}\right\\}$

and

$\mathcal{A}_{2}:=\left\\{\exists
S\subset[n]:n^{2}p^{2}\leqslant|S|\leqslant(np)^{C_{2}}\text{ and
}e(S)\geqslant(1+\gamma)|S|\right\\}.$

The following lemma shows that both $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$
are unlikely at the large deviations scale.

######  Lemma 2.6.

Let $p$ satisfy (1.4). For any $\gamma>0$ and $C_{2}<\infty$ we have that

$\max\\{\mathbb{P}(\mathcal{A}_{1}),\mathbb{P}(\mathcal{A}_{2})\\}\leqslant\exp\left(-\frac{\gamma}{2}n^{2}p^{2}\log
n\right),$

for all $n$ sufficiently large.

The next lemma provides a bound on the number of high degree vertices.

######  Lemma 2.7.

Let $p$ satisfy (1.4). Then

$\lim_{n\to\infty}\frac{\log\mathbb{P}\left(|V_{H}|\geqslant(np)^{1-\eta/2}\right)}{n^{2}p^{2}\log(np)}=-\infty.$

In the following lemma we will show that any connected component of ${\sf
G}_{M}$ (the underlying graph is again $\mathbb{G}(n,p)$) cannot have too many
vertices. This will require some further notation. Fix $C_{3}<\infty$ and let

$\mathcal{M}:=\left\\{\exists S\subset V_{M}:|S|\geqslant
C_{3}np\log(np)\text{ and }{\sf G}[S]\text{ is connected}\right\\}.$

######  Lemma 2.8.

Let $p$ satisfy (1.4). There exists $C_{3}<\infty$, depending only on
$\delta$, such that

$\mathbb{P}(\mathcal{M})\leqslant\exp(-2(1+\delta)^{2}n^{2}p^{2}\log(np)).$

The goal of the next lemma will be to show that $\lambda({\sf
G}_{L_{1}}\cup{\sf G}_{L_{1}L_{2}})=o(np)$ at the large deviations scale. As
mentioned above the argument will involve an iterative pruning procedure. To
state the result we will need to introduce a couple more notation.

Fix $L\in\mathbb{N}$ and $\alpha\in(0,1)$. For $\ell\in[L-1]$ set

$\mathscr{C}_{\ell}:=\\{{\sf G}\subset K_{n}:\updelta({\sf G})\geqslant
2,\Delta({\sf G})\leqslant(1+\delta)np,v({\sf G})\leqslant(np)^{L-\ell+1}\\}$

and

$\mathcal{C}_{\ell}:=\left\\{\exists{\sf G}\subset\mathbb{G}(n,p):{\sf
G}\in\mathscr{C}_{\ell}\text{ and }\lambda({\sf
G})\geqslant\frac{\alpha}{2^{\ell-1}}np\right\\}.$

######  Lemma 2.9.

Let $p$ satisfy (1.4). Then for any $\ell\in[L-2]$

$\mathbb{P}(\mathcal{C}_{\ell})\leqslant\mathbb{P}(\mathcal{C}_{\ell+1})+\exp\left(-\frac{\alpha^{2}}{C(1+\delta)2^{2\ell}}n^{2}p^{2}\log
n\right),$

where $C<\infty$ is some absolute constant.

The proofs of these lemmas are postponed to Section 2.1. Below, using these
lemmas, we complete the proof of the large deviations upper bound.

###### Proof of Theorem 1.1 (upper bound) for $p$ satisfying (1.4).

Fix $\varepsilon>0$ sufficiently small. We will show that
$\lambda(\mathbb{G}(n,p)\backslash\widetilde{\sf
F}_{HL_{1}}(\mathbb{G}(n,p)))\geqslant\varepsilon np$ with a negligible
probability at the large deviations scale. This will yield the upper bound.

Step 1. We claim that

(2.8) $\mathbb{P}\left(\max\\{\lambda({\sf G}_{H}),\lambda({\sf
G}_{HM})\\}\geqslant\frac{\varepsilon\delta}{15}np\right)\leqslant
2\exp\left(-2(1+\delta)^{2}n^{2}p^{2}\log(np)\right).$

By Lemma 2.2(i) and (v)

$\lambda({\sf G}_{H})\leqslant\max_{v\in V_{H}}|\mathcal{N}_{H}(v)|\quad\text{
and }\quad\lambda({\sf G}_{HM})\leqslant\sqrt{\max_{v\in
V_{M}}|\mathcal{N}_{H}(v)|\cdot\max_{u\in V_{H}}|\mathcal{N}_{M}(v)|}.$

Therefore, (2.8) is now immediate from Lemma 2.4 (see also Remark 2.5).

Step 2. We next claim that

(2.9) $\mathbb{P}\left(\lambda({\sf
G}_{M})\geqslant\frac{\varepsilon\delta}{15}np\right)\leqslant
2\exp\left(-2(1+\delta)^{2}n^{2}p^{2}\log(np)\right).$

Since the top eigenvalue of a graph is the maximum of the top eigenvalues of
its connected components we obtain that

(2.10) $\mathbb{P}\left(\lambda({\sf
G}_{M})\geqslant\frac{\varepsilon\delta}{15}np\right)\leqslant\mathbb{P}\left(\exists
S\subset V_{M}:{\sf G}[S]\text{ is connected and }\lambda({\sf
G}[S])\geqslant\frac{\varepsilon\delta}{15}np\right)\\\
\leqslant\mathbb{P}\left(\exists S\subset[n]:|S|\leqslant
C_{3}np\log(np)\text{ and }\lambda({\sf
G}[S])\geqslant\frac{\varepsilon\delta}{15}np\right)+\mathbb{P}(\mathcal{M}).$

Now note that, for any $c_{\star}>0$, upon taking a union bound,

(2.11) $\mathbb{P}\left(\exists S\subset[n]:|S|\leqslant C_{3}np\log(np)\text{
and }e(S)\geqslant c_{\star}n^{2}p^{2}\right)\leqslant\sum_{w\geqslant
c_{\star}n^{2}p^{2}}\sum_{s\leqslant
C_{3}np\log(np)}\binom{n}{s}\binom{s^{2}}{w}p^{w}\\\ \leqslant\sum_{w\geqslant
c_{\star}n^{2}p^{2}}\sum_{s\leqslant C_{3}np\log(np)}\exp\left(s\log
n+w\log(2es)-w\log(1/p)\right)\\\ \leqslant O(np\log(np))\sum_{w\geqslant
c_{\star}n^{2}p^{2}}\exp\left(-\frac{w}{2}\log n\right)\leqslant
n^{3}\exp\left(-\frac{c_{\star}}{2}n^{2}p^{2}\log
n\right)\leqslant\exp\left(-\frac{c_{\star}}{4}n^{2}p^{2}\log n\right),$

where in the second inequality we used Stirling’s approximation, and the third
inequality is due to the facts that $s=O(np\log(np))$, $\log(np)\ll\log n$,
$np\gg 1$, and $w\geqslant c_{\star}n^{2}p^{2}$.

Upon setting $c_{\star}=\varepsilon\delta/450$, we observe that (2.9) follows
from the fact that $\lambda({\sf G})\leqslant\sqrt{2e({\sf G})}$ (see the
upper bound in Lemma 2.2(i)), (2.10)-(2.11), and Lemma 2.8.

Step 3. We aim to show that

(2.12) $\mathbb{P}\left(\lambda({\sf G}_{L_{1}}\cup{\sf
G}_{L_{1}L_{2}})\geqslant\frac{\varepsilon\delta}{15}np\right)\leqslant\exp\left(-2(1+\delta)^{2}n^{2}p^{2}\log(np)\right),$

for all large $n$.

To this end, we begin by noting that

(2.13) $\mathbb{P}(\Delta(\mathbb{G}(n,p))\geqslant(np)^{2+\eta/3})\leqslant
n\mathbb{P}(\operatorname{Bin}(n-1,p)\geqslant(np)^{2+\eta/3})\leqslant\exp\left(-\frac{1}{2}(np)^{2+\eta/3}\log(np)\right),$

which is negligible at the large deviations scale. As every vertex in
$V_{L_{1}}$ must be connected to some vertex in $V_{H}$ we observe that on the
event

$\Omega_{0}:=\left\\{\Delta:=\Delta(\mathbb{G}(n,p))\leqslant(np)^{2+\eta/3}\right\\}\cap\left\\{|V_{H}|\leqslant(np)^{1-\eta/2}\right\\}$

we have that $|V_{L_{1}}|\leqslant\Delta\cdot|V_{H}|\leqslant(np)^{3-\eta/6}$.
By a same reasoning, on the event $\Omega_{0}$, we also have that

$\left|\left\\{u\in V_{L_{2}}:(u,v)\in E(\mathbb{G}(n,p))\text{ for some }v\in
V_{L_{1}}\right\\}\right|\leqslant\left[\max_{v\in
V_{L_{1}}}\deg(v)\right]\cdot|V_{L_{1}}|\leqslant(np)^{4-\eta/12}.$

Thus, on the event $\Omega_{0}$, we have that $v({\sf G}_{L_{1}}\cup{\sf
G}_{L_{1}L_{2}})\leqslant(np)^{4}$. Therefore, setting $L=4$ and
$\alpha=\varepsilon\delta/30$, and applying Lemma 2.9 we derive that

(2.14) $\mathbb{P}\left(\lambda(\widehat{\sf G}_{L_{1}}\cup\widehat{\sf
G}_{L_{1}L_{2}})\geqslant\frac{\varepsilon\delta}{30}np\right)\leqslant\mathbb{P}(\Omega_{0}^{c})+\mathbb{P}(\mathcal{C}_{1})\leqslant\mathbb{P}(\Omega_{0}^{c})+\mathbb{P}(\mathcal{C}_{3})+2\exp(-c_{1}\varepsilon^{2}n^{2}p^{2}\log
n),$

for some constant $c_{1}>0$, depending only on $\delta$. Observe that, by
(2.13) and Lemma 2.7

(2.15) ${-\log\mathbb{P}(\Omega_{0}^{c})}\gg{n^{2}p^{2}\log(np)}.$

On the other hand, by Lemma 2.2(viii) for any graph ${\sf G}$ with
$\updelta({\sf G})\geqslant 2$ and $\Delta({\sf G})\lesssim np$ we have that

$\lambda({\sf G})\gtrsim np\Rightarrow e({\sf G})-v({\sf G})\gtrsim
n^{2}p^{2}.$

Therefore, $\mathcal{C}_{3}\subset\mathcal{A}_{1}$, for a suitably chosen
$\gamma$, and hence by Lemma 2.6 we deduce that

(2.16) $-\log\mathbb{P}(\mathcal{C}_{3})\gg n^{2}p^{2}\log(np).$

Recall that ${\sf F}_{L_{1}}={\sf G}_{L_{1}}\backslash\widehat{\sf G}_{L_{1}}$
and ${\sf F}_{L_{1}L_{2}}={\sf G}_{L_{1}L_{2}}\backslash\widehat{\sf
G}_{L_{1}L_{2}}$ are forests. Hence, by Lemma 2.2(iii)

$\lambda({\sf F}_{L_{1}L_{2}}\cup{\sf F}_{L_{1}})=O\left(\sqrt{\max_{v\in
V_{L}}\deg(v)}\right)=O(\sqrt{np}).$

This observation together with (2.14)-(2.16) now yield (2.12).

Step 4. Our next goal is to derive that

(2.17) $\mathbb{P}\left(\lambda({\sf
G}_{ML})\geqslant\frac{\varepsilon\delta}{15}np\right)\leqslant\exp\left(-2(1+\delta)^{2}n^{2}p^{2}\log(np)\right).$

Fix any $\widetilde{c}>0$. As ${\sf G}_{ML}$ is a bipartite graph with vertex
bipartition $V_{M}$ and $V_{L}$, Lemma 2.2(vii) implies that

(2.18) $\left\\{\lambda({\sf
G}_{ML})\geqslant\widetilde{c}np\right\\}\subset\left\\{\exists v\in
V_{M},\mathcal{W}\subset V_{L}:w\sim v\,\forall\,w\in\mathcal{W}\text{ and
}\sum_{w\in\mathcal{W}}\deg_{{\sf
G}_{ML}}(w)\geqslant\widetilde{c}^{2}n^{2}p^{2}\right\\}=:\widetilde{\Omega}_{0}.$

Using again that ${\sf G}_{ML}$ is a bipartite graph we also observe that on
the event $\widetilde{\Omega}_{0}$ there exists $\mathcal{U}\subset V_{M}$
(namely the set of neighbors in $V_{M}$ of the vertices in $\mathcal{W}$) such
that
$e(\mathcal{W},\mathcal{U}\cup\\{v\\})\geqslant\widetilde{c}^{2}n^{2}p^{2}$.
Notice that $\mathcal{U}\subset\mathcal{N}_{M}^{(2)}(v)$. Therefore, noting
that $\deg(v)\leqslant\varpi_{n}$ for any $v\in V_{M}$ (see Definition 2.3) we
deduce that

(2.19) $\widetilde{\Omega}_{0}\backslash\left\\{\exists
v^{\prime}\in[n]:|\mathcal{N}_{M}^{(2)}(v^{\prime})|\geqslant
C_{1}np\log(np)\right\\}\\\ \subset\left\\{\exists v\in[n],\mathcal{U}\subset
V_{M},\mathcal{W}\subset V_{L}:|\mathcal{U}|\leqslant
C_{1}np\log(np),|\mathcal{W}|\leqslant\varpi_{n},e(\mathcal{U},\mathcal{W}\cup\\{v\\})\geqslant\widetilde{c}^{2}n^{2}p^{2}\right\\}\\\
=:\widehat{\Omega}_{0},$

where $C_{1}$ is as in Lemma 2.4. By the union bound and Lemma 2.1 (see also
(2.4)) we now obtain that

(2.20)
$\mathbb{P}(\widehat{\Omega}_{0})\leqslant\sum_{\begin{subarray}{c}\mathfrak{u}\leqslant\varpi_{n}\\\
\mathfrak{w}\leqslant
C_{1}np\log(np)\end{subarray}}\sum_{v\in[n]}\sum_{\begin{subarray}{c}\mathcal{U},\mathcal{W}\subset[n]\\\
|\mathcal{U}|=\mathfrak{u},|\mathcal{W}|=\mathfrak{w}\end{subarray}}\mathbb{P}(e(\mathcal{U},\mathcal{W}\cup\\{u\\})\geqslant\widetilde{c}^{2}n^{2}p^{2})\\\
\leqslant n^{2}\cdot\exp\left(\varpi_{n}\log n+O(np\log(np))\log
n-\widetilde{c}^{2}n^{2}p^{2}\log n\cdot(1+o(1))\right)\\\ \leqslant
n^{2}\exp\left(-\frac{\widetilde{c}^{2}}{2}n^{2}p^{2}\log
n\right)\leqslant\exp\left(-\frac{\widetilde{c}^{2}}{4}n^{2}p^{2}\log
n\right),$

where in the second and third steps we used that $\varpi_{n},np\log(np)\ll
n^{2}p^{2}\leqslant n^{o(1)}$, and in the last step we used that $np\gg 1$.
Now, upon choosing $\widetilde{c}=\varepsilon\delta/15$, (2.17) follows from
(2.18)-(2.20) and Lemma 2.4.

Step 5. We will show that

(2.21) $\mathbb{P}\left(\lambda(\widehat{\sf
F}_{HL_{1}})\geqslant\frac{\varepsilon\delta}{15}np\right)\leqslant\exp\left(-2(1+\delta)^{2}n^{2}p^{2}\log(np)\right).$

We claim that

(2.22) $\lim_{n\to\infty}\frac{\log\mathbb{P}(\Delta(\widehat{\sf
F}_{HL_{1}})\geqslant(1+\delta)np)}{n^{2}p^{2}\log(np)}=-\infty.$

Since $\widehat{\sf F}_{HL_{1}}$ is a star, upon applying Lemma 2.2(iii),
(2.21) is immediate from (2.22). By definition $\max_{v\in
V_{L}}\deg(v)<(1+\delta)np$. Therefore, as ${\sf F}_{HL_{1}}$ is a forest not
containing any star that has its center vertex belonging to $V_{H}$, we find
that

$\left\\{\Delta(\widehat{\sf
F}_{HL_{1}})\geqslant(1+\delta)np\right\\}\subset\left\\{\exists
v\in[n]:|\mathcal{N}_{H}^{(2)}(v)|\geqslant(1+\delta)np\right\\}.$

Thus (2.22) follows from Lemma 2.4.

Step 6. Finally we note that

(2.23) $\lambda({\sf G}_{L_{2}}\cup\widetilde{\sf
F}_{HL_{1}})\leqslant\max\left\\{\sqrt{\Delta(\mathbb{G}(n,p))},(1+\delta(1-\varepsilon))np\right\\}.$

This is immediate since ${\sf G}_{L_{2}}$ and $\widetilde{\sf F}_{HL_{1}}$ are
vertex disjoint, and $\widetilde{\sf F}_{HL_{1}}$ is a vertex disjoint union
of stars (apply Lemma 2.2(ii) and (iv)).

We may now complete the proof of the theorem. Indeed, by Lemma 2.2(ii)

(2.24) ${\rm UT}_{\lambda}(\delta)\subset\left\\{\lambda({\sf
G}_{L_{2}}\cup\widetilde{\sf
F}_{HL_{1}})\geqslant(1+\delta(1-\varepsilon/2))np\right\\}\cup\Omega_{\star}\subset{\rm
UT}_{\Delta}((1+\delta(1-\varepsilon/2))^{2})\cup\Omega_{\star},$

where

$\Omega_{\star}:=\left\\{\lambda({\sf G}_{H})+\lambda({\sf
G}_{HM})+\lambda({\sf G}_{M})+\lambda({\sf G}_{ML})+\lambda(\widehat{\sf
F}_{HL_{1}})+\lambda({\sf G}_{L_{1}}\cup{\sf
G}_{L_{1}L_{2}})\geqslant\frac{\varepsilon\delta}{2}np\right\\},$

and the last step in (2.24) follows from (2.23). By (2.8), (2.9), (2.12),
(2.17), and (2.21) we have that

(2.25)
$\mathbb{P}(\Omega_{\star})\lesssim\exp(-2(1+\delta)^{2}n^{2}p^{2}\log(np)).$

This together with Lemma 2.1 and (2.24) now yield that

$\limsup_{n\to\infty}\frac{\log\mathbb{P}({\rm
UT}_{\lambda}(\delta))}{n^{2}p^{2}\log(np)}\leqslant-(1+\delta(1-\varepsilon/2))^{2}.$

Since $\varepsilon>0$ is arbitrary this completes the proof. ∎

We now prove Corollary 1.3 for $p$ such that (1.4) holds. The proof for the
other regime is provided in Section 4.

###### Proof of Corollary 1.3 (first regime).

We see from (2.24) that

${\rm UT}_{\lambda}(\delta)\cap{\rm
UT}_{\Delta}((1+(1-\chi)\delta)^{2})^{\complement}\subset\Omega_{\star},$

for any $\chi>\varepsilon/2$. Therefore, using (2.25) for the numerator, and
(2.3) and the lower bound from Lemma 2.1 for the denominator we deduce that

$\limsup_{n\to\infty}\mathbb{P}\left({\rm
UT}_{\Delta}((1+(1-\chi)\delta)^{2})^{\complement}\big{|}{\rm
UT}_{\lambda}(\delta)\right)\leqslant\limsup_{n\to\infty}\frac{\mathbb{P}(\Omega_{\star})}{\mathbb{P}({\rm
UT}_{\lambda}(\delta))}=0.$

Since $\varepsilon>0$ is arbitrary this completes the proof. ∎

###  2.1. Proofs of Lemmas 2.4 and 2.6-2.9

We start with the proof of Lemma 2.7.

###### Proof of Lemma 2.7.

This is a simple application of the binomial tail probability bound. Indeed,
fix a set $\mathcal{U}\subset[n]$ of cardinality $t$. Observe that

(2.26)
$\mathbb{P}\left(\sum_{u\in\mathcal{U}}\deg(u)\geqslant\varpi_{n}t\right)=\mathbb{P}(2e(\mathcal{U})+e(\mathcal{U},[n]\backslash\mathcal{U})\geqslant\varpi_{n}t)\\\
\leqslant\mathbb{P}(e(\mathcal{U})\geqslant\varpi_{n}t/3)+\mathbb{P}(e(\mathcal{U},[n]\backslash\mathcal{U})\geqslant\varpi_{n}t/3).$

As $\varpi_{n}\gg np$, and

$e(\mathcal{U},[n]\backslash\mathcal{U})\stackrel{{\scriptstyle
d}}{{=}}\operatorname{Bin}(t(n-t),p)\quad\text{ and }\quad
e(\mathcal{U})\stackrel{{\scriptstyle
d}}{{=}}\operatorname{Bin}\left(\binom{t}{2},p\right),$

using Lemma 2.1 (see also (2.4)) we obtain that, there exists some $c>0$,
depending only on $\eta$, such that the lhs of (2.26) is bounded above by
$\exp(-c\varpi_{n}t\log\log n)$. Hence, applying the union bound we now deduce
that

$\mathbb{P}(|V_{H}|\geqslant(np)^{1-\eta/2})\leqslant\sum_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=(np)^{1-\eta/2}\end{subarray}}\mathbb{P}\left(\sum_{u\in\mathcal{U}}\deg(u)\geqslant\varpi_{n}(np)^{1-\eta/2}\right)\\\
\leqslant\exp\left(-(np)^{1-\eta/2}(c\varpi_{n}\log\log n-\log
n)\right)\leqslant\exp\left(-\frac{c}{2}(np)^{1-\eta/2}\varpi_{n}\log\log
n\right)\\\ \leqslant\exp\left(-\frac{c}{2}(np)^{2+\eta/2}\log\log n\right),$

where in the penultimate step we have used that $\varpi_{n}\log\log n\gg\log
n$ (follows from (2.5) and that $np\gg\sqrt{\log n/\log\log n}$) and in the
last step we used that $\varpi_{n}\geqslant(np)^{1+\eta}$. This completes the
proof. ∎

Next we prove Lemma 2.6.

###### Proof of Lemma 2.6.

Fix a set $S\subset[n]$ with $|S|=s\leqslant(np)^{C_{2}}$. Then
$e(S)\stackrel{{\scriptstyle d}}{{=}}\operatorname{Bin}(\binom{s}{2},p)$.
Therefore, by Lemma 2.1 (see also (2.4)), as $\log(np)\ll\log n$, we have that

$\mathbb{P}(e(S)\geqslant(1+\gamma)s)\leqslant\exp\left(-(1+\gamma)s\left\\{\log
n-\log(nps)\right\\}\cdot(1+o(1))\right)\\\
\leqslant\exp\left(-(1+\gamma)s\log n(1+o(1))\right),$

where in the last inequality we used the upper bound on $s$. Now the uper
bound on $\mathbb{P}(\mathcal{A}_{2})$ follows after taking a union over the
choices of $S\subset[n]$ with $n^{2}p^{2}\leqslant|S|\leqslant(np)^{C_{2}}$.

The proof of the upper bound on $\mathbb{P}(\mathcal{A}_{1})$ is similar.
Indeed, fixing $S\subset[n]$ with $|S|=s\leqslant n^{2}p^{2}$, using the
binomial tail probability bound and that $\log(np)\ll\log n$ once more, we
find that

$\mathbb{P}(e(S)\geqslant s+\gamma n^{2}p^{2})\leqslant\exp(-(s+\gamma
n^{2}p^{2})\cdot(1+o(1))\log n).$

Now the proof follows by taking a union over $S\subset[n]$ such that
$|S|\leqslant n^{2}p^{2}$. ∎

Now we proceed to prove Lemma 2.4. Let us add that a similar result was proved
in [29] (see Lemma 2.4 there).

###### Proof of Lemma 2.4.

Fix any $v\in[n]$. We will show that

(2.27) $\mathbb{P}(|\mathcal{N}_{M}^{(2)}(v)|\geqslant
C_{1}np\log(np))\leqslant\exp(-3(1+\delta)^{2}n^{2}p^{2}\log(np)).$

Since $n^{2}p^{2}\log(np)\gg\log n$, an application of the union bound then
yields (2.6).

Turning to prove (2.27) let us fix a set
$\mathcal{U}\subset[n]\backslash\\{v\\}$ of cardinality $\ell$ and
$\mathcal{W}\supset\mathcal{U}\cup\\{v\\}$ such that
$\ell+1\leqslant|\mathcal{W}|\leqslant 2\ell+1$. Fix a collection of edges
$\mathcal{E}$ such that at least one end point of the edges in $\mathcal{E}$
belong to $\mathcal{U}$, and $|\mathcal{E}|=|\mathcal{W}|-1\leqslant 2\ell$.
Let $\\{a_{i,j}\\}_{i<j}$ be i.i.d. $\operatorname{Ber}(p)$ and for $i>j$ set
$a_{i,j}=a_{j,i}$.

We claim that for any $\ell\leqslant n^{2}p^{2}$

(2.28)
$\mathbb{P}\left(\sum_{u\in\mathcal{U}}\deg(u)\geqslant(1+\delta(1-\varepsilon))np\ell\Big{|}a_{i,j}=1\,\forall\,\\{i,j\\}\in\mathcal{E}\right)\\\
\leqslant\mathbb{P}\left(\sum_{\begin{subarray}{c}i,j\in\mathcal{U}\\\
\\{i,j\\}\notin\mathcal{E}\end{subarray}}a_{i,j}+\sum_{\begin{subarray}{c}i\in\mathcal{U},j\notin\mathcal{U}\\\
\\{i,j\\}\notin\mathcal{E}\end{subarray}}a_{i,j}\geqslant(1+\delta(1-2\varepsilon))np\ell\Bigg{|}a_{i,j}=1\,\forall\,\\{i,j\\}\in\mathcal{E}\right)\\\
\leqslant\mathbb{P}\left(2e(\mathcal{U})+e(\mathcal{U},[n]\backslash\mathcal{U})\geqslant(1+\delta(1-2\varepsilon))np\ell\right)\\\
\leqslant\mathbb{P}(\operatorname{Bin}(n\ell,p)\geqslant(1+\delta(1-3\varepsilon))np\ell)+\mathbb{P}(\operatorname{Bin}(\ell^{2}/2,p)\geqslant\delta\varepsilon
np\ell/2)\leqslant\exp(-c_{\delta}np\ell),$

for some $c_{\delta}>0$. The first inequality above follows from that
$|\mathcal{E}|\leqslant 2\ell$ and $np\gg 1$. The second inequality is a
consequence of the fact that the edges in $\mathbb{G}(n,p)$ are independent
and stochastic domination of binomial random variables. The penultimate
inequality follows from a union bound. As $\log(np)\ll\log(1/p)$, the last
inequality in (2.28) follows from Lemma 2.1 (see also (2.2) and (2.4)).

Now note that the event $|\mathcal{N}_{M}^{(2)}(v)|\geqslant\ell$ implies that
there exists a set $\mathcal{U}\subset V_{M}$ with $|\mathcal{U}|=\ell$ such
that

(2.29)
$\sum_{i\in\mathcal{U},j\in[n]}a_{i,j}=\sum_{u\in\mathcal{U}}\deg(u)\geqslant(1+\delta(1-\varepsilon))np\ell.$

Let $\mathcal{W}$ be the set of vertices of the smallest subgraph of
$\mathbb{G}(n,p)$ containing $\mathcal{U}\cup\\{v\\}$ that is connected. Let
$\mathcal{E}$ be the edge set of that subgraph. Since the vertices of
$\mathcal{U}$ are at a distance at most two from $v$ it follows that
$\ell+1\leqslant|\mathcal{W}|\leqslant 2\ell+1$. Furthermore, note that the
smallest connected subgraph being a tree we also have that
$|\mathcal{E}|=|\mathcal{W}|-1$.

Equipped with these observations, to bound the probability that
$|\mathcal{N}_{M}^{(2)}(v)|$ exceeds $\ell$ we first fix
$\mathcal{U},\mathcal{W}$, and $\mathcal{E}$. Then we find a bound on the
probability that (2.29) and the event that $a_{i,j}=1$ for all
$\\{i,j\\}\in\mathcal{E}$ hold. Finally we take a union bound over the choices
of $\mathcal{U}$, $\mathcal{W}$, and $\mathcal{E}$. Carrying out these steps,
by (2.28) and Stirling’s approximation, we obtain that

$\mathbb{P}(|\mathcal{N}_{M}^{(2)}(v)|\geqslant\ell)\leqslant\sum_{w=\ell+1}^{2\ell+1}\sum_{\begin{subarray}{c}\mathcal{U}\subset[n]\\\
|\mathcal{U}|=\ell\end{subarray}}\sum_{\begin{subarray}{c}\mathcal{W}\subset[n]\\\
\mathcal{W}\supset\mathcal{U}\cup\\{v\\}\\\
|\mathcal{W}|=w\end{subarray}}\sum_{\begin{subarray}{c}\mathcal{E}:\mathcal{E}\subset\mathcal{U}\times\mathcal{W}\\\
|\mathcal{E}|=w-1\end{subarray}}\mathbb{P}\left(a_{i,j}=1\,\forall\,\\{i,j\\}\in\mathcal{E}\right)\\\
\qquad\qquad\qquad\cdot\mathbb{P}\left(\sum_{u\in\mathcal{U}}\deg(u)\geqslant(1+\delta(1-\varepsilon))np\ell\Big{|}a_{i,j}=1\,\forall\,\\{i,j\\}\in\mathcal{E}\right)\\\
\leqslant\sum_{w=\ell+1}^{2\ell+1}\binom{n}{\ell}\binom{n-\ell-1}{w-\ell-1}\binom{\ell
w}{w-1}\cdot p^{w-1}\exp(-c_{\delta}np\ell)\\\
\leqslant\sum_{w=\ell+1}^{2\ell+1}(np)^{w}(e\ell)^{w}\cdot\frac{\binom{w}{\ell}}{w!}\cdot
p^{-1}\exp(-c_{\delta}np\ell)\\\ \leqslant 2\ell
n\cdot(3e^{2}np)^{3\ell}\exp(-c_{\delta}np\ell)\leqslant\exp\left(\log
n-\frac{c_{\delta}}{2}np\ell\right),$

where in the penultimate step we used that $p\geqslant n^{-1}$ and in the last
step we used that $np\gg 1$. Now, upon choosing $\ell=C_{1}np\log(np)$, for
some large $C_{1}<\infty$, depending only on $\delta$, as
$n^{2}p^{2}\log(np)\gg\log n$, we obtain (2.27).

The proof of (2.7) being similar to that of (2.6) is omitted. This completes
the proof of the lemma. ∎

Next we prove Lemma 2.8.

###### Proof of Lemma 2.8.

Fix a subset of vertices $\mathcal{T}\subset[n]$ of cardinality $t$, and a
subset $\mathcal{E}\in\binom{\mathcal{T}}{2}$ such that $|\mathcal{E}|=t-1$.
Arguing similarly as in (2.28) we observe that

(2.30)
$\mathbb{P}\left(\sum_{u\in\mathcal{T}}\deg(u)\geqslant(1+\delta(1-\varepsilon))npt\Big{|}a_{i,j}=1\,\forall\,(i,j)\in\mathcal{E}\right)\\\
\leqslant\mathbb{P}\left(\sum_{\begin{subarray}{c}i,j\in\mathcal{T}\\\
\\{i,j\\}\notin\mathcal{E}\end{subarray}}a_{i,j}+\sum_{i\in\mathcal{T},j\notin\mathcal{T}}a_{i,j}\geqslant(1+\delta(1-2\varepsilon))npt\Bigg{|}a_{i,j}=1\,\forall\,(i,j)\in\mathcal{E}\right)\\\
\leqslant\mathbb{P}\left(2e(\mathcal{T})+e(\mathcal{T},[n]\backslash\mathcal{T})\geqslant(1+\delta(1-2\varepsilon))npt\right).$

Now we claim that, there exists some constant $c_{\delta}>0$, depending only
on $\delta$ such that

(2.31)
$\mathbb{P}\left(2e(\mathcal{T})+e(\mathcal{T},[n]\backslash\mathcal{T})\geqslant(1+\delta(1-2\varepsilon))npt\right)\leqslant\mathfrak{p}_{t}:=\left\\{\begin{array}[]{ll}\exp(-c_{\delta}npt)&\mbox{
if }t\leqslant n^{2}p^{2},\\\ \exp(-\varepsilon(\delta\wedge 1)npt/2)&\mbox{
if }n^{2}p^{2}\leqslant t\leqslant\varepsilon(\delta\wedge 1)n,\\\
\exp(-\widehat{c}npt)&\mbox{ if }\varepsilon(\delta\wedge 1)n\leqslant
t\leqslant c_{0}n,\end{array}\right.$

where $c_{0}\in[\varepsilon(\delta\wedge 1),1)$ to be determined below, and
$\widehat{c}>0$ is some constant depending on $\delta,\varepsilon$, and
$c_{0}$. To see this, for $t\leqslant\varepsilon(\delta\wedge 1)n$, by the
triangle inequality, we observe that

$\mathbb{P}\left(2e(\mathcal{T})+e(\mathcal{T},[n]\backslash\mathcal{T})\geqslant(1+\delta(1-2\varepsilon))npt\right)\\\
\leqslant\mathbb{P}\left(\operatorname{Bin}(t(n-t),p)\geqslant(1+\delta(1-6\varepsilon))npt\right)+\mathbb{P}\left(\operatorname{Bin}\left(\binom{t}{2},p\right)\geqslant\binom{t}{2}p+\varepsilon\delta
npt\right),$

By (2.2) it follows that the first term in the rhs is bounded above by
$\exp(-2c_{\delta}npt)$. On the other hand, by Lemma 2.1 and (2.4) we obtain
that the second term in the rhs is bounded above by $\exp(-\varepsilon\delta
npt\log n/2)$ for $t\leqslant n^{2}p^{2}$, while applying the Chernoff bound
(see (2.2)) with $\gamma=2\varepsilon(\delta\wedge 1)n/t$ we find that the
same term is bounded by $\exp(-\varepsilon(\delta\wedge 1)npt/2)$ for
$t\leqslant\varepsilon(\delta\wedge 1)n$. Combining these estimates we obtain
(2.31) for all $t\leqslant\varepsilon(\delta\wedge 1)n$. To prove the
remaining range of $t$ we use triangle inequality again to obtain that

$\mathbb{P}\left(2e(\mathcal{T})+e(\mathcal{T},[n]\backslash\mathcal{T})\geqslant(1+\delta(1-2\varepsilon))npt\right)\\\
\leqslant\mathbb{P}\left(\operatorname{Bin}(t(n-t),p)\geqslant(1+\delta(1-\varepsilon))t(n-t)p\right)+\mathbb{P}\left(\operatorname{Bin}\left(\binom{t}{2},p\right)\geqslant(1+\delta(1-\varepsilon))\binom{t}{2}p\right),$

and then use the Chernoff bound and the fact that $\varepsilon(\delta\wedge
1)n\leqslant t\leqslant c_{0}n$. This proves (2.31).

If $S\subset V_{M}$ then $2e(\mathbb{G}(n,p))\geqslant\sum_{u\in
S}\deg(u)\geqslant(1+\delta(1-\varepsilon))np|S|$. Therefore, for
$c_{0}=c_{0}(\delta,\varepsilon)\in(0,1)$ such that
$c_{0}(1+\delta(1-\varepsilon))\geqslant(1+\delta/2)$, by Chernoff bound, we
find that

(2.32)
$\mathbb{P}(\Omega_{M})\leqslant\mathbb{P}\left(e(\mathbb{G}(n,p))\geqslant(1+\delta/2)\cdot\binom{n}{2}p\right)\leqslant\exp(-\widetilde{c}_{\delta}n^{2}p),$

for some $\widetilde{c}_{\delta}>0$, depending only on $\delta$, where
$\Omega_{M}:=\\{\exists S\subset V_{M}:|S|\geqslant c_{0}n\\}$. For the rest
of the proof we will work with this choice of $c_{0}$.

Equipped with all necessary bounds we now complete the proof of the lemma. To
this end, we notice that on the event $\mathcal{M}\backslash\Omega_{M}$ there
must exists a set of vertices $\mathcal{T}\subset[n]$ such that
$|\mathcal{T}|=t$, where $t\in[C_{3}np\log(np),c_{0}n]$, and ${\sf
G}[\mathcal{T}]$ is connected. This further implies the existence of an
spanning tree $\mathbb{T}$ of $\mathcal{T}$ with edge set
$\mathcal{E}\subset\binom{\mathcal{T}}{2}$ such that $a_{i,j}=1$ for
$(i,j)\in\mathcal{E}$, where $a_{i,j}$’s are as in (2.30).

Hence, using that the number of trees on $t$ vertices is bounded by $t^{t+2}$,
applying (2.30)-(2.31), and a union bound we find that

$\mathbb{P}(\mathcal{M})-\mathbb{P}(\Omega_{M})\leqslant\sum_{t\geqslant
C_{3}np\log(np)}^{c_{0}n}\sum_{\mathcal{T}:|\mathcal{T}|=t}\sum_{\mathcal{E}}p^{t-1}\mathbb{P}\left(\sum_{u\in\mathcal{T}}\deg(u)\geqslant(1+\delta(1-\varepsilon))npt\Big{|}a_{i,j}=1\,\forall\,(i,j)\in\mathcal{E}\right)\\\
\leqslant\sum_{t=C_{3}np\log(np)}^{c_{0}n}\binom{n}{t}t^{t+2}p^{t-1}\mathfrak{p}_{t}\leqslant
n^{3}\sum_{t=C_{3}np\log(np)}^{c_{0}n}(enp)^{t}\mathfrak{p}_{t}\\\ \leqslant
n^{3}\left(\exp\left(-\frac{c_{\delta}C_{3}}{2}n^{2}p^{2}\log(np)\right)+\exp(-c_{\star}n^{3}p^{3})\right),$

for some constant $c_{\star}>0$. Now recalling that $n^{2}p^{2}\log(np)\gg\log
n$ and $n\gg np\log(np)$, the proof completes upon applying (2.32), and
choosing $C_{3}<\infty$ sufficiently large, depending only $\delta$. ∎

We end this section with the proof of Lemma 2.9.

###### Proof of Lemma 2.9.

We begin by noting that, by Lemma 2.2(vii), for any graph ${\sf G}$ with
$\updelta({\sf G})\geqslant 2$ and $\Delta({\sf G})\leqslant(1+\delta)np$, as
$np\gg 1$, the lower bound $\lambda({\sf
G})\geqslant\frac{\alpha}{2^{\ell-1}}np$ implies that

$e({\sf G})-v({\sf G})\geqslant\frac{\alpha^{2}}{2^{2\ell}}n^{2}p^{2},$

for all large $n$.

Therefore, by Lemma 2.6 we have that

(2.33) $\mathbb{P}(\mathcal{C}_{\ell})\\\ \leqslant\mathbb{P}\left(\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf G}\in\mathscr{C}_{\ell},\lambda({\sf
G})\geqslant\frac{\alpha}{2^{\ell-1}}np,\text{ and }v({\sf G})\geqslant
n^{2}p^{2}\right)+\exp\left(-\frac{\alpha^{2}}{2^{2\ell+1}}n^{2}p^{2}\log
n\right)\\\
\leqslant\mathbb{P}(\widetilde{{\mathcal{C}}}_{\ell})+2\exp\left(-\frac{\gamma_{\star}}{8}n^{2}p^{2}\log
n\right),$

where

$\widetilde{{\mathcal{C}}}_{\ell}:=\left\\{\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf G}\in\mathscr{C}_{\ell},\lambda({\sf
G})\geqslant\frac{\alpha}{2^{\ell-1}}np,e({\sf
G})\leqslant\left(1+\frac{\gamma_{\star}}{4}\right)v({\sf G}),\text{ and
}v({\sf G})\geqslant n^{2}p^{2}\right\\}$

and $\gamma_{\star}:=\frac{\alpha^{2}}{(1+\delta)\cdot 9\cdot 2^{2\ell}}$. It
now remains to show that
$\widetilde{\mathcal{C}}_{\ell}\subset\mathcal{C}_{\ell+1}$. This will
complete the proof.

Turning to do this task let us decompose the vertices of ${\sf G}$ as follows:

$V_{1}:=\\{v\in V({\sf G}):\deg_{\sf
G}(v)\geqslant\gamma_{\star}np\\}\quad\text{ and }\quad V_{2}:=V({\sf
G})\backslash V_{1}.$

Define

${\sf G}_{1}:={\sf G}[V_{1}],\quad{\sf G}_{2}:={\sf G}[V_{2}],\quad\text{ and
}{\sf G}_{12}:={\sf G}[V_{1},V_{2}].$

Further let $\widehat{\sf G}_{1}$ be the two core of ${\sf G}_{1}$ and set
${\sf F}_{1}:={\sf G}_{1}\backslash\widehat{\sf G}_{1}$. Note that ${\sf
F}_{1}$ is a forest. Also observe that for any ${\sf G}$ with $\Delta({\sf
G})\leqslant(1+\delta)np$, due to our choice of $\gamma_{\star}$, by Lemma
2.2(i), (iii), and (v) we have that

$\max\\{\lambda({\sf F}_{1}),\lambda({\sf G}_{12}),\lambda({\sf
G}_{2})\\}\leqslant\frac{\alpha}{3\cdot 2^{\ell}}np.$

Thus, by Lemma 2.2(ii)

$\lambda({\sf
G})\geqslant\frac{\alpha}{2^{\ell-1}}np\Longrightarrow\lambda(\widehat{\sf
G}_{1})\geqslant\frac{\alpha}{2^{\ell}}np.$

Moreover, for ${\sf G}$ satisfying the hypotheses of the event
$\widetilde{\mathcal{C}}_{\ell}$, we notice that

$\frac{\gamma_{\star}}{2}np\cdot|V_{1}|\leqslant\sum_{v\in V({\sf
G})}(\deg_{\sf G}(v)-2)=2(e({\sf G})-v({\sf
G}))\leqslant\frac{\gamma_{\star}}{2}v({\sf G}),$

yielding that $v(\widehat{\sf G}_{1})\leqslant(np)^{L-\ell}$. Hence, the
subgraph $\widehat{\sf G}_{1}\subset{\sf G}$ satisfies the hypotheses of the
event $\mathcal{C}_{\ell+1}$. Therefore
$\widetilde{\mathcal{C}}_{\ell}\subset\mathcal{C}_{\ell+1}$, and the proof of
the lemma is now complete. ∎

##  3\. Proofs of Theorems 1.1(b) and 1.5

We start with the proof of Theorem 1.5. We begin with the proof of the lower
bound.

###### Proof of Theorem 1.5 (lower bound).

Fix $\beta>0$. For graphs ${\sf G},{\sf G}^{\prime},{\sf G}^{\prime\prime}$
such that ${\sf G}^{\prime}\subset{\sf G}$ and ${\sf
G}^{\prime\prime}\subset{\sf G}\backslash{\sf G}^{\prime}$ we observe that

${\rm Hom}(C_{2t},{\sf G})\geqslant{\rm Hom}(C_{2t},{\sf G}^{\prime})+{\rm
Hom}(C_{2t},{\sf G}^{\prime\prime}).$

Therefore, denoting $\mathbb{G}_{1}$ to be the random subgraph of
$\mathbb{G}(n,p)$ induced by the edges between $\\{1\\}$ and
$[n]\backslash\\{1\\}$, $\check{\mathbb{G}}_{1}$ to be random subgraph on
$[n]\backslash\\{1\\}$, $\mathbb{G}_{2}$ to be the random subgraph induced by
$[\lceil(\widehat{\delta}+\beta)^{1/(2t)}np\rceil]$, and
$\check{\mathbb{G}}_{2}$ to be the random subgraph induced by the rest of the
vertices, we obtain that

${\rm Hom}(C_{2t},\mathbb{G}(n,p))\geqslant{\rm
Hom}(C_{2t},\mathbb{G}_{1})+{\rm Hom}(C_{2t},\check{\mathbb{G}}_{1})$

and

${\rm Hom}(C_{2t},\mathbb{G}(n,p))\geqslant{\rm
Hom}(C_{2t},\mathbb{G}_{2})+{\rm Hom}(C_{2t},\check{\mathbb{G}}_{2}).$

It is easy to note that

(3.1) $\mathbb{P}({\rm
Hom}(C_{2t},\mathbb{G}_{1})\geqslant(\widehat{\delta}+\beta)n^{2t}p^{2t})\geqslant\mathbb{P}\left(\deg_{\mathbb{G}(n,p)}(1)\geqslant(({\widehat{\delta}+\beta})/{2})^{1/t}n^{2}p^{2}\right)\\\
\geqslant\exp\left(-(1+o(1))\cdot\left(\frac{\widehat{\delta}+\beta}{2}\right)^{1/t}n^{2}p^{2}\log(np)\right)=:\mathfrak{q}_{1},$

where the last step is due to Lemma 2.1 and we have used that $np^{2}\ll 1\ll
np$ . Moreover,

(3.2)
$\mathfrak{q}_{2}:=\exp\left(-\frac{1}{2}\lceil(\widehat{\delta}+\beta)^{1/(2t)}np\rceil^{2}\log(1/p)\right)\leqslant\mathbb{P}\left(K_{[\lceil(\widehat{\delta}+\beta)^{1/(2t)}np\rceil]}\subset\mathbb{G}(n,p)\right)\\\
\leqslant\mathbb{P}\left({\rm
Hom}(C_{2t},\mathbb{G}_{2})\geqslant(1+o(1))\cdot(\widehat{\delta}+\beta)n^{2t}p^{2t}\right).$

Therefore, by the independence of the edges of $\mathbb{G}(n,p)$ we further
deduce that

(3.3) $\mathbb{P}({\rm UT}_{t}(\widehat{\delta}))\\\
\geqslant\max\left\\{\mathfrak{q}_{1}\cdot\mathbb{P}({\rm
Hom}(C_{2t},\check{\mathbb{G}}_{1})\geqslant(1-\beta)n^{2t}p^{2t}),\mathfrak{q}_{2}\cdot\mathbb{P}({\rm
Hom}(C_{2t},\check{\mathbb{G}}_{2})\geqslant(1-\beta/2)n^{2t}p^{2t})\right\\}.$

Since $\check{\mathbb{G}}_{1}$ and $\check{\mathbb{G}}_{2}$ are distributed as
$\mathbb{G}(n^{\prime},p)$ and $\mathbb{G}(n^{\prime\prime},p)$ with
$n^{\prime},n^{\prime\prime}=n(1-o(1))$ and $\beta$ is arbitrary we observe
from (3.1)-(3.3) that, writing $A_{n}$ for the adjacency matrix of
$\mathbb{G}(n,p)$, it suffices to show that

(3.4)
$\mathbb{P}(\operatorname{Tr}(A_{n}^{2t})\leqslant(1-\beta/2)n^{2t}p^{2t})=o(1).$

Turning to prove (3.4) we apply standard concentration inequalities (e.g. [10,
Theorem 1.16]) and the interlacing inequality, upon noting
$\lambda_{1}(\mathbb{E}A_{n})=np(1+o(1))$, to obtain that, for any
$\varepsilon^{\prime}>0$,

$\mathbb{P}(\lambda_{1}(A_{n})\leqslant(1-\varepsilon^{\prime})np)\leqslant\mathbb{P}(\|A_{n}-\mathbb{E}A_{n}\|\geqslant\varepsilon^{\prime}np/2)=o(1).$

From this the claim (3.4) follows and thus the proof of the lower bound is now
complete. ∎

The next few sections are devoted to the proof of the large deviation upper
bound for the upper tail of ${\rm Hom}(C_{2t},\mathbb{G}(n,p))$. As mentioned
in Section 1.4 we will borrow terminologies from [8, 27]. The first notion is
about pre-seed graphs. For ${\sf G}\subset K_{n}$ and a function $f$ we define

$\mathbb{E}_{\sf G}[f(\mathbb{G}(n,p)]=\mathbb{E}[f(\mathbb{G}(n,p))\mid
a_{i,j}^{\mathbb{G}}=1\,\forall(i,j)\in E({\sf G})],$

where $\\{a_{i,j}^{\mathbb{G}}\\}$ is the adjacency matrix of
$\mathbb{G}(n,p)$.

######  Definition 3.1 (Pre-seed graph).

Fix $\varepsilon>0$ sufficiently small and integer $t\geqslant 2$. Let
$\bar{C}:=\bar{C}(\widehat{\delta},t)$ be a sufficiently large constant. A
graph ${\sf G}\subset K_{n}$ is said to be a pre-seed graph if the followings
hold:

  1. (PS1)

$\mathbb{E}_{\sf G}[{\rm
Hom}(C_{2t},\mathbb{G}(n,p))]\geqslant(1+\widehat{\delta}(1-\varepsilon))\mathbb{E}[{\rm
Hom}(C_{2t},\mathbb{G}(n,p)]$.

  2. (PS2)

$e({\sf G})\leqslant\bar{C}n^{2}p^{2}\log(1/p)$.

The choice of $\bar{C}$ will be made precise during the course of the proof.
In the lemma below we show that probability of the upper tail event can be
approximately bounded by that of the existence of pre-seed subgraphs of
$\mathbb{G}(n,p)$.

######  Lemma 3.2.

Let $p$ satisfy (1.14). Then

$\mathbb{P}({\rm
UT}_{t}(\widehat{\delta}))\leqslant(1+o(1))\cdot\mathbb{P}(\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf G}\text{ is a pre-seed graph}).$

The proof of Lemma 3.2 relies on the following result from [27]. For a
function $F(Y)$, where $Y=(Y_{1},Y_{2},\ldots,Y_{N})$ is a random vector, and
$I\subset[N]$, we use the shorthand $\mathbb{E}_{I}[F]$ to denote the
conditional expectation of $F$ given $\\{Y_{i},i\in I\\}$.

######  Lemma 3.3 ([27, Lemma 3.7]).

Let $Y:=(Y_{1},Y_{2},\ldots,Y_{N})$ be a random variable taking values in
$\\{0,1\\}^{N}$ and $F:=F(Y)$ be a nonzero polynomial with nonnegative
coefficient of degree at most $d$. Then for every $\ell\in\mathbb{N}$,
$\widehat{\delta}>0$, and $\varepsilon\in(0,1)$ we have that

$\mathbb{P}\left(F\geqslant(1+\widehat{\delta})\mathbb{E}[F]\text{ and
}Y_{I}=0\text{ for all
}I\in\mathcal{I}\right)\leqslant\left(1-\frac{\varepsilon\widehat{\delta}}{1+\widehat{\delta}}\right)^{\ell},$

where

$\mathcal{I}:=\left\\{I\subset[N]:|I|\leqslant d\ell\text{ and
}\mathbb{E}_{I}[F]\geqslant(1+\widehat{\delta}(1-\varepsilon))\mathbb{E}[F]\right\\}\quad\text{
and }\quad Y_{I}:=\prod_{i\in I}Y_{i}.$

###### Proof of Lemma 3.2.

We set $F={\rm Hom}(C_{2t},\mathbb{G}(n,p))$ and $N=\binom{n}{2}$. Identifying
the set $\\{(i,j),i<j\in[n]\\}$ with $[N]$ we apply Lemma 3.3 with
$\ell=\bar{C}t^{-1}n^{2}p^{2}\log(1/p)$ to deduce that

(3.5) $\mathbb{P}\left({\rm UT}_{t}(\widehat{\delta})\cap\left\\{\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf G}\text{ a pre-seed
graph}\right\\}^{\complement}\right)\leqslant\left(\frac{1}{2}\right)^{\bar{C}t^{-1}n^{2}p^{2}\log(1/p)}\ll\mathbb{P}({\rm
UT}_{t}(\widehat{\delta})),$

where the last step follows upon choosing $\bar{C}$ choosing sufficiently
large, and from the lower bound on the probability of ${\rm
UT}_{t}(\widehat{\delta})$ (proved above). This immediately implies that

$\mathbb{P}({\rm UT}_{t}(\widehat{\delta}))\leqslant o(1)\cdot\mathbb{P}({\rm
UT}_{t}(\widehat{\delta}))+\mathbb{P}\left({\rm
UT}_{t}(\widehat{\delta})\cap\left\\{\exists{\sf G}\subset\mathbb{G}(n,p):{\sf
G}\text{ a pre-seed graph}\right\\}\right),$

which in turn yields the desired upper bound on the probability of ${\rm
UT}_{t}(\widehat{\delta})$. ∎

The condition (PS1) in Definition 3.1 is difficult to work with. Below we will
show that, in the regime (1.14), such graphs admit a nicer description, and
moreover subgraphs of those graphs can be extracted so that each edge of the
subgraph participates in a lot of homomorphism counts. These two sets of
graphs will be termed as seed graphs and core graphs, respectively.

######  Definition 3.4 (Seed graph).

Let $\varepsilon,\widehat{\delta},t$, and $\bar{C}$ be as in Definition 3.1. A
graph ${\sf G}\subset K_{n}$ is said to be a seed graph if the followings
hold:

  1. (S1)

${\rm Hom}(C_{2t},{\sf
G})\geqslant\widehat{\delta}(1-2\varepsilon)n^{2t}p^{2t}$.

  2. (S2)

$e({\sf G})\leqslant\bar{C}n^{2}p^{2}\log(1/p)$.

######  Definition 3.5 (Core graph).

With $\varepsilon,\widehat{\delta},t$, and $\bar{C}$ as in Definition 3.1 we
define a graph ${\sf G}\subset K_{n}$ to be a core graph if

  1. (C1)

${\rm Hom}(C_{2t},{\sf
G})\geqslant\widehat{\delta}(1-3\varepsilon)n^{2t}p^{2t}$,

  2. (C2)

$e({\sf G})\leqslant\bar{C}n^{2}p^{2}\log(1/p)$,

and

  1. (C3)

$\min_{{\bf e}\in E({\sf G})}{\rm Hom}(C_{2t},{\sf G},{\bf
e})\geqslant\widehat{\delta}\varepsilon
n^{2t}p^{2t}/(\bar{C}n^{2}p^{2}\log(1/p))$,

where for an edge ${\bf e}\in E({\sf G})$ the notation ${\rm Hom}(C_{2t},{\sf
G},{\bf e})$ denotes the number of homomorphisms of $C_{2t}$ in ${\sf G}$ that
contain the edge ${\bf e}$.

######  Lemma 3.6.

Let $p$ satisfy (1.14). Then, for all large $n$,

$\left\\{\exists{\sf G}\subset\mathbb{G}(n,p):{\sf G}\text{ is pre-
seed}\right\\}\subset\left\\{\exists{\sf G}\subset\mathbb{G}(n,p):{\sf
G}\text{ is core}\right\\}.$

The proof of Lemma 3.6 is postponed to Section 3.1. Equipped with Lemma 3.6 we
observe that it now suffices to bound the probability of the existence of a
core graph in $\mathbb{G}(n,p)$. We split the set of core graphs into two
subsets: (i) core graphs with a large number of edges and (ii) core graphs
with $O(n^{2}p^{2})$ many edges. We show below that the existence of the first
set of graphs are unlikely at the large deviations scale. To treat the second
set of graphs we extract yet another subgraph of core graphs so that each edge
participates in even a larger number of homomorphism counts. These graphs will
be termed as strong-core graphs.

######  Definition 3.7 (Strong-core graph).

Let $\varepsilon,\widehat{\delta}$, and $t$ be as in Definition 3.1, and
$\bar{C}_{\star}:=\bar{C}_{\star}(\widehat{\delta},t)<\infty$ be a large
constant, depending on $\widehat{\delta}$ and $t$, and the ratio
$\log(np)/\log(1/p)$. We define a graph ${\sf G}\subset K_{n}$ to be a strong-
core graph if

  1. (SC1)

${\rm Hom}(C_{2t},{\sf
G})\geqslant\widehat{\delta}(1-{6}\varepsilon)n^{2t}p^{2t}$,

  2. (SC2)

$e({\sf G})\leqslant\bar{C}_{\star}n^{2}p^{2}$,

and

  1. (SC3)

$\min_{{\bf e}\in E({\sf G})}{\rm Hom}(C_{2t},{\sf G},{\bf
e})\geqslant(\widehat{\delta}\varepsilon/\bar{C}_{\star})\cdot(np)^{2t-2}$.

The choice of $\bar{C}_{\star}$ will also be made precise in the proof. Note
the difference in the lower bounds in (C3) and (SC3) in Definitions 3.5 and
3.7, respectively.

######  Lemma 3.8.

Fix $\varepsilon\in(0,1)$ and $t\in\mathbb{N}$. Then, for $p$ satisfying
(1.14) and $\varepsilon\leqslant 1/(36t)$ we have that

$\limsup_{n\to\infty}\frac{\log\mathbb{P}\left(\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf G}\text{ is core and }e({\sf
G})\geqslant\bar{C}_{\star}n^{2}p^{2}\right)}{n^{2}p^{2}\log(np)}\leqslant-{\frac{\bar{C}_{\star}}{20}}.$

######  Lemma 3.9.

Consider the same setup as in Lemma 3.8. Then, there exists some absolute
constant $\beta<\infty$ such that

$\log\mathbb{P}\left(\exists{\sf G}\subset\mathbb{G}(n,p):{\sf G}\text{ is
strong-core}\right)\leqslant\exp(-\phi_{t}(\widehat{\delta})(1-\beta
t\varepsilon)),$

for all large $n$, where

(3.6)
$\phi_{t}(\widehat{\delta}):=\min\left\\{\frac{1}{2}\widehat{\delta}^{1/t}\log(1/p),\left(\frac{\widehat{\delta}}{2}\right)^{1/t}\log(np)\right\\}n^{2}p^{2}.$

Proofs of Lemmas 3.8 and 3.9 are postponed to Sections 3.2 and 3.3,
respectively. Equipped with Lemmas 3.2, 3.6, 3.8, and 3.9 we now complete the
proof of the large deviation upper bound.

###### Proof of Theorem 1.5 (upper bound).

Using Lemmas 3.2 and 3.6 we derive that

$\mathbb{P}({\rm
UT}_{t}(\widehat{\delta}))\leqslant(1+o(1))\mathbb{P}(\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf G}\text{ is core}).$

Therefore, once we show that

(3.7) $\\{\exists{\sf G}\subset\mathbb{G}(n,p):{\sf G}\text{ is core and
}e({\sf G})\leqslant\bar{C}_{\star}n^{2}p^{2}\\}\subset\\{\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf G}\text{ strong-core}\\},$

application of Lemmas 3.8 and 3.9, with
$\bar{C}_{\star}=C\widehat{\delta}^{1/t}$ for some large absolute constant
$C<\infty$, would yield that

(3.8) $\mathbb{P}({\rm
UT}_{t}(\widehat{\delta}))\leqslant\exp(-\phi_{t}(\widehat{\delta})(1-2\beta
t\varepsilon)),$

for all large $n$. To prove (3.7) we consider the subgraph ${\sf
G}^{\prime}\subset{\sf G}$ obtained by iteratively deleting edges ${\bf e}$ of
${\sf G}$ such that ${\rm Hom}(C_{2t},{\sf G},{\bf
e})\leqslant(\widehat{\delta}\varepsilon/\bar{C}_{\star})\cdot(np)^{t-2}$.
Using triangle inequality it follows that ${\sf G}^{\prime}$ is indeed a
strong-core graph. Thus (3.7) holds and the proof of the theorem is complete.
∎

######  Remark 3.10.

For the rest of the paper we set $\bar{C}_{\star}=C\widehat{\delta}^{1/t}$.

Next, using Theorem 1.5, we prove Theorem 1.1(b).

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

As mentioned in Section 1.1 we will prove the following large deviation bound
for $p$ satisfying (1.14):

(3.9) $-\log\mathbb{P}({\rm
UT}_{\lambda}(\delta))=(1+o(1))\min\left\\{\frac{1}{2}(1+\delta)^{2}n^{2}p^{2}\log(1/p),(1+\delta)^{2}n^{2}p^{2}\log(np)\right\\}.$

From this (1.7) is immediate. First let us prove the large deviation lower
bound. For $m\in\mathbb{N}$, let $K_{[m]}$ denote the clique on $[m]$. Since
$\lambda(K_{[m]})=m-1$, by Lemma 2.2(i) and (vi) we have that

$\left\\{K_{[\lceil(1+\delta)np\rceil+1]}\subset\mathbb{G}(n,p)\right\\}\cup{\rm
UT}_{\Delta}(\delta)\subset{\rm UT}_{\lambda}(\delta).$

Now the desired large deviation lower bound follows from Lemma 2.1 and the
fact that the probability that $\mathbb{G}(n,p)$ contains $K_{[m]}$ is bounded
below by $\exp(-m^{2}/2\log(1/p))$.

Turning to prove the upper bound we note that for any graph ${\sf G}$

(3.10) $\lambda_{1}({\sf G})^{2t}\leqslant\sum_{i}\lambda_{i}({\sf
G})^{2t}={\rm Hom}(C_{2t},{\sf G}).$

Now, as $\log(np)\gtrsim\log n$, there exists $c>0$ such that $np\geqslant
n^{c}$, for all large $n$. Hence, (1.12) holds for all $t>1/c$. This, together
with (3.10) and (3.8) now shows that

(3.11) $-\log\mathbb{P}({\rm
UT}_{\lambda}(\delta))\geqslant\phi_{t}(\widehat{\delta})(1-2t\beta\varepsilon)$

for all $t>1/c$ with $\widehat{\delta}=\widehat{\delta}(t)=(1+\delta)^{2t}-1$.
As $\lim_{t\to\infty}\widehat{\delta}^{1/t}=(1+\delta)^{2}$, given any
$\upepsilon>0$, there exists some $t_{0}>1/c$ such that
$(\widehat{\delta}/2)^{1/t}\geqslant(1+\delta)^{2}(1-\upepsilon)$. Setting
$\varepsilon=\upepsilon t_{0}^{-1}\beta^{-1}$ we therefore find that

$-\log\mathbb{P}({\rm
UT}_{\lambda}(\delta))\geqslant(1-2\upepsilon)\min\left\\{\frac{1}{2}(1+\delta)^{2}n^{2}p^{2}\log(1/p),(1+\delta)^{2}n^{2}p^{2}\log(np)\right\\},$

for all large $n$. Since $\upepsilon$ is arbitrary the desired upper bound now
follows. This completes the proof. ∎

###  3.1. Bounds on expected homomorphism counts

In this section our goal is to derive Lemma 3.6. To prove Lemma 3.6 we will
need a couple of results. The first one provides a necessary bound on
$\mathbb{E}[{\rm Hom}(C_{2t},\mathbb{G}(n,p))]$.

To state the result we need the notion of quotient graphs. For $\pi$ a
partition of $V(H)$ we let $H/\pi$ to be the quotient graph obtained from $H$
by identifying vertices within parts of the partition $\pi$ and deleting
multiple edges (but keeping self-loops). Note that if some part of $\pi$
contain vertices that do not form an independent set of $H$ then the quotient
graph $H/\pi$ possesses self-loops. By an abuse of notation, quotient graphs
that do not possess any self-loops will be termed, for convenience, simple
quotient graphs.

######  Lemma 3.11.

Fix $t\geqslant 2$.

  1. (a)

Let $H=C_{2t}/\pi$ be a simple quotient subgraph of $C_{2t}$. If $H$ is a tree
then $v(H)\leqslant t+1$. Furthermore, the number of simple quotient subgraphs
of $C_{2t}$ that are trees and have (vertex) size $(t+1)$ is
$\binom{2t}{t}/(t+1)$.

  2. (b)

Let $p\in(0,1)$ such that $np\gg 1$. Then

$\mathbb{E}[{\rm
Hom}(C_{2t},\mathbb{G}(n,p))]=(1+o(1))\cdot\left(n^{2t}p^{2t}+\frac{\binom{2t}{t}}{t+1}n^{t+1}p^{t}\right).$

Next, recalling Definitions 3.1 and 3.4 we note that one also needs that
$\mathbb{E}_{\sf G}[{\rm Hom}(C_{2t},\mathbb{G}(n,p))]=(1+o(1)){\rm
Hom}(C_{2t},{\sf G})$. This step is significantly different than the one in
the context of subgraph counts. For the subgraph count the maps
$\varphi:V(C_{2t})\mapsto[n]$ under consideration are injective and therefore
all the edges of $C_{2t}$ that are not mapped to those of ${\sf G}$ retain
their independence.

On the other hand, a homomorphism $\varphi$ not necessarily being an injective
map the edges of $C_{2t}$ that are not mapped to $E({\sf G})$ need not be
mapped to distinct edges of $K_{n}\backslash{\sf G}$, and hence all these
edges may not be “free” and some may get “frozen” via $\varphi$. To tackle
this new difficulty one needs an additional combinatorial analysis. We require
a few definitions to carry out this step.

######  Definition 3.12 (Equivalence classes of maps, and generating and non-
generating edges and vertices).

Let $\varphi:V(C_{2t})\mapsto[n]$ be a map such that no two adjacent vertices
of $C_{2t}$ are mapped to the same element in $[n]$. It naturally induces a
map from $E(C_{2t})$ to $\binom{[n]}{2}$, which, by a slight abuse of
notation, will be continued to be denoted by $\varphi$.

For ${\sf G}\subset K_{n}$ and $H\subset C_{2t}$ we let $\mathcal{S}({H},{\sf
G})$ to be set of all maps $\varphi$ such that $\varphi(E({H}))\subset E({\sf
G})$ and $\varphi(E(\bar{H}))\subset E(\bar{{\sf G}})$, where
$\bar{H}:=C_{2t}\backslash{H}$ and $\bar{\sf G}:=K_{n}\backslash{\sf G}$.

Notice that $\varphi\in\mathcal{S}({H},{\sf G})$ further induces equivalence
classes on $E(\bar{H})$. Namely, $e_{i},e_{j}\in E(\bar{H})$ are said to be
equivalent iff $\varphi(e_{i})=\varphi(e_{j})$. Inside each equivalence class
an arbitrarily chosen edge, e.g. the edge with the smallest index under the
canonical labelling of $E(C_{2t})$ (see Definition 3.13 below), is said to be
generating (or free), while the others are said to be non-generating (or
frozen).

This also allows us to extend the notion of free/frozen for vertices that are
incident to some edge in $E(\bar{H})$: Both end points of a non-generating
edge are set to be non-generating (or frozen), while the rest of the vertices
are termed to be generating (or free).

######  Definition 3.13 (Types of edges).

For convenience, let us put the canonical labelling on $C_{2t}$. That is,
$V(C_{2t})=[2t]$ and $E(C_{2t})=\\{e_{i}\\}_{i=1}^{2t}$, where $e_{i}=(i,i+1)$
for $i\in[2t-1]$ and $e_{2t}=(2t,1)$. For $i\in[2t]$, the vertex $i$ will be
said to be the left end point of the edge $e_{i}$, while the vertex in the
other end of $e_{i}$ will be its right end point.

Fix $H\subset C_{2t}$. We classify the edges of $\bar{H}$ as follows. If both
end points of the edge ${\bf e}\in E(\bar{H})$ are in $V({H})$ then we
classify ${\bf e}$ as a type I edge. If ${\bf e}$ is such that only its left
end point belongs to $V({H})$ then we classify it as a type II edge. When only
the right end point of ${\bf e}$ belongs to $V({\sf H})$ we term that to be a
type III edge. The rest of the edges of $\bar{H}$ are type IV edges.

######  Definition 3.14.

Fix ${\sf G}\subset K_{n}$ and $H\subset C_{2t}$. Define

$\psi(H)=\psi_{\sf G}(H):=\sum_{\varphi\in\mathcal{S}(H,{\sf
G})}\mathbb{E}_{\sf G}\left[\prod_{{\bf e}=(x,y)\in
E(C_{2t})}a^{\mathbb{G}}_{\varphi(x),\varphi(y)}\right].$

Let
${\bm{f}}:=(\mathfrak{f}_{1},\mathfrak{f}_{2},\mathfrak{f}_{3},\mathfrak{f}_{4})$,
where $\mathfrak{f}_{i}\in\mathbb{Z}_{\geqslant}$ for $i=1,\ldots,4$, and
define $\mathcal{S}(H,{\sf G},{\bm{f}})$ to be the subset of all
$\varphi\in\mathcal{S}(H,{\sf G})$ such that the number of frozen edges of
Type $i$ equals $\mathfrak{f}_{i}$ for $i=1,\ldots,4$. Set

(3.12) $\psi(H,{\bm{f}})=\psi_{\sf
G}(H,{\bm{f}}):=\sum_{\varphi\in\mathcal{S}(H,{\sf
G},{\bm{f}})}\mathbb{E}_{\sf G}\left[\prod_{{\bf e}=(x,y)\in
E(C_{2t})}a^{\mathbb{G}}_{\varphi(x),\varphi(y)}\right].$

Equipped with the above definitions we now have the following result.

######  Lemma 3.15.

Fix $\varnothing\neq H\subsetneq C_{2t}$, ${\sf G}\subset K_{n}$, and
${\bm{f}}\in\mathbb{Z}_{\geqslant}^{4}$ such that $H$ does not contain any
isolated vertex and $e({\sf G})=O(n^{2}p^{2}\log n)$. Then, for $p\in(0,1)$
such that $(\log n)^{t}\ll np\ll n^{1/2}(\log n)^{-2t}$ we have that

(3.13) $\psi(H,{\bm{f}})=o(n^{2t}p^{2t}).$

Let us postpone the proof of Lemma 3.15 to later and now provide the proof of
Lemma 3.6.

###### Proof of Lemma 3.6 (using Lemmas 3.11 and 3.15).

It follows from Definition 3.14 and Lemma 3.15 that

$\mathbb{E}_{\sf G}[{\rm Hom}(C_{2t},\mathbb{G}(n,p)]=\sum_{H:H\subset
C_{2t}}\psi_{\sf G}(H)=\psi_{\sf G}(C_{2t})+(1+o(1))n^{2t}p^{2t}={\rm
Hom}(C_{2t},{\sf G})+(1+o(1))n^{2t}p^{2t},$

where the sum over $H$ in the first step is restricted to those subgraphs of
$C_{2t}$ that do not possess any isolated vertex. Therefore, by Lemma 3.11(b)
we deduce that any pre-seed is graph ${\sf G}$ is a seed graph, for $p$ as in
(1.14) and all large $n$. Now upon deleting edges ${\bf e}\in E({\sf G})$
(iteratively) such that ${\rm Hom}(C_{2t},{\sf G},{\bf
e})\leqslant\widehat{\delta}\varepsilon
n^{2t}p^{2t}/(\bar{C}n^{2}p^{2}\log(1/p))$ we obtain a subgraph ${\sf
G}^{\prime}\subset{\sf G}$ such that conditions (C2) and (C3) of Definition
3.5 holds for ${\sf G}^{\prime}$. Since $e({\sf
G})\leqslant\bar{C}n^{2}p^{2}\log(1/p)$, by triangle inequality we obtain that
(C1) also holds for ${\sf G}^{\prime}$. Thus, ${\sf G}^{\prime}$ is a core
graph. This concludes the proof. ∎

It remains to prove Lemmas 3.11 and 3.15. First, we prove Lemma 3.15.

###### Proof of Lemma 3.15.

To derive (3.13) we will split the sum over $\varphi$ into subsets of
$\mathcal{S}(H,{\sf G},{\bm{f}})$ such that the equivalence classes,
determined by $\varphi$, are same and show that the bound (3.13) holds for all
allowable choices of equivalence classes.

To this end, we fix a partition $\mathcal{P}$ of the edge set $E(\bar{H})$.
This automatically defines equivalence classes on $E(\bar{H})$ and therefore
it further determines the set of non-generating/frozen edges, to be denoted by
$\mathcal{F}=\mathcal{F}(\mathcal{P})\subset E(\bar{H})$. There is still an
indeterminacy in the choice of which end of generating edge to be mapped to
the left end of non-generating edges. So we fix
${\bm{m}}\in\\{-1,1\\}^{\mathcal{F}}$. Now we let $\mathcal{S}(H,{\sf
G},\mathcal{P},{\bm{m}})\subset\mathcal{S}(H,{\sf G},{\bm{f}})$ to be the
collection of all maps $\varphi$ such that the equivalence class induced by
$\varphi$ is $\mathcal{P}$, in particular the set of non-generating edges is
$\mathcal{F}$, and the end points of the free edges to be mapped (via
$\varphi$) to the left end of the frozen edges are determined by ${\bm{m}}$.

We then let $\psi(H,\mathcal{P},{\bm{m}})$ to be the rhs of (3.12) when the
sum there is taken over $\varphi\in\mathcal{S}(H,{\sf
G},\mathcal{P},{\bm{m}})$. As there are only finitely many choices of
${\bm{m}}$ and $\mathcal{P}$ (depending only on $t$) such that the number of
frozen edges is ${\bm{f}}$ we notice that it suffices to prove the bound
(3.13) for $\psi(H,\mathcal{P},{\bm{m}})$ for any fixed $\mathcal{P}$ and
${\bm{m}}$.

We now turn to prove (3.13) for $\psi(H,\mathcal{P},{\bm{m}})$. Observe that
conditioned on the edges in ${\sf G}$, for any $\varphi\in\mathcal{S}(H,{\sf
G},\mathcal{P},{\bm{m}})$, only the edges
$\varphi(E(\bar{H})\backslash\mathcal{F})$ are independent. Therefore

(3.14) $\psi(H,\mathcal{P},{\bm{m}})=\sum_{\varphi\in\mathcal{S}(H,{\sf
G},\mathcal{P},{\bm{m}})}\mathbb{E}\left[\prod_{{\bf e}=(x,y)\in
E(\bar{H})}a^{\mathbb{G}}_{\varphi(x),\varphi(y)}\right]=\widetilde{\psi}(H,\mathcal{P},{\bm{m}})\cdot
p^{|E(\bar{H})\backslash\mathcal{F}|},$

where $\widetilde{\psi}(H,\mathcal{P},{\bm{m}}):=|\mathcal{S}(H,{\sf
G},\mathcal{P},{\bm{m}})|$. As

(3.15)
$|E(\bar{H})\backslash\mathcal{F}|=2t-e(H)-\sum_{i=1}^{4}\mathfrak{f}_{i},$

it now remains to find an appropriate bound on
$\widetilde{\psi}(H,\mathcal{P},{\bm{m}})$. To this end, we let
$V_{\star}:=V(H)\backslash V(\mathcal{F})$ and
$\widehat{V}:=[2t]\backslash(V(H)\cup V(\mathcal{F}))$, where $V(\mathcal{F})$
is the set of frozen vertices. Recalling Definition 3.12, as
$\varphi\in\mathcal{S}(H,{\sf G},\mathcal{P},{\bm{m}})$, we observe that
$\varphi(V_{\star}\cup\widehat{V})$ determines the values of
$\varphi(V(\mathcal{F}))$. Therefore

$\mathcal{S}(H,{\sf
G},\mathcal{P},{\bm{m}})\subset\left\\{\varphi_{\star}\Big{|}\,\varphi_{\star}:V_{\star}\mapsto
V({\sf G}),\varphi_{\star}(E(H_{\star}))\subset E({\sf
G})\right\\}\times\left\\{\widehat{\varphi}\Big{|}\,\widehat{\varphi}:\widehat{V}\mapsto[n]\right\\},$

where $H_{\star}:={\sf G}[V_{\star}]$. Hence

$\widetilde{\psi}(H,\mathcal{P},{\bm{m}})\leqslant n^{\widehat{v}}\cdot{\rm
Hom}(H_{\star},{\sf G}),$

where $\widehat{v}:=|\widehat{V}|$.

Since $\varnothing\neq H\subsetneq C_{2t}$ and $H$ does not contain isolated
vertices it is easy to see that $H$ must be a vertex disjoint union of paths
and hence, by the definition of $H_{\star}$, so is $H_{\star}$. Let us assume
that $H=\cup_{i=1}^{k}P_{s_{i}}$ for some $k\geqslant 1$ and $s_{i}\geqslant
1$ for $i\in[k]$, where $P_{\ell}$ denotes a path of length $\ell$. Recall
Definition 3.13 and note that each frozen edge appearing after a path
$P_{s_{i}}$, for some $i\in[k]$ (when $C_{2t}$ is traversed from the lowest
indexed edge to the highest indexed edge in its canonical labelling) must be
either a type I or type II edge, while each frozen edge preceding a path
$P_{s_{i}}$ should be either a type I and or type III edge. This yields that

(3.16) $\mathfrak{f}_{1}+\mathfrak{f}_{2}\vee\mathfrak{f}_{3}\leqslant k.$

We next claim that

(3.17) $\widehat{v}\leqslant
2t-v(H)-\mathfrak{f}_{2}\vee\mathfrak{f}_{3}-\mathfrak{f}_{4}$

and

(3.18) ${\rm Hom}(H_{\star},{\sf G})\lesssim
n^{v(H)}p^{e(H)}\cdot(np^{2})^{k}\cdot(np)^{-(\mathfrak{f}_{1}+\mathfrak{f}_{2}\vee\mathfrak{f}_{3})}\cdot(\log
n)^{3t}.$

Before proving (3.17)-(3.18) let us use these bounds to derive the bound
(3.13) for $\psi(H,\mathcal{P},{\bm{m}})$. Using (3.14)-(3.15) and
(3.17)-(3.18) we obtain that

$\psi(H,\mathcal{P},{\bm{m}})\lesssim(np)^{2t}\cdot(\log
n)^{3t}\cdot(np^{2})^{k-\mathfrak{f}_{1}-\mathfrak{f}_{2}\wedge\mathfrak{f}_{3}}\cdot(np)^{-(\mathfrak{f}_{2}\vee\mathfrak{f}_{3}+\mathfrak{f}_{4})}.$

Now recall (3.16). If
$\mathfrak{f}_{1}+\mathfrak{f}_{2}\wedge\mathfrak{f}_{3}<k$ then the upper
bound on $p$ implies that the bound (3.13) holds for
$\psi(H,\mathcal{P},{\bm{m}})$. On other hand, if
$\mathfrak{f}_{2}\wedge\mathfrak{f}_{3}>0$ then the lower bound on $p$ yields
the desired bound on $\psi(H,\mathcal{P},{\bm{m}})$. In the remaining case,
i.e. when $\mathfrak{f}_{2}\wedge\mathfrak{f}_{3}=0$, as type I edges can only
be mapped to edges of same type via $\varphi$ and there must at least one
generating type I edge, we further obtain that $\mathfrak{f}_{1}$ must be
strictly less then the number of type I edges which in turn is strictly less
than $k$. From this observation the bound on $\psi(H,\mathcal{P},{\bm{m}})$ in
this remaining case follows.

To complete the proof of the lemma it now remains to derive (3.17)-(3.18). To
prove (3.17) pick any frozen edge that is of type either II or IV. Consider
the vertex on its right end point. Observe that such vertices are distinct as
we move over all type II and IV frozen edges. Furthermore, all these vertices
are in $([2t]\backslash V(H))\cap V(\mathcal{F})$. Therefore,
$\widehat{v}\leqslant 2t-v(H)-\mathfrak{f}_{2}-\mathfrak{f}_{4}$. Now
considering type III and IV frozen edges and the vertices at the left end
point of these edges, and repeating the same argument as above we arrive at
the bound (3.17).

Turning to prove (3.18) we observe that, for $\ell\geqslant-1$,

(3.19) ${\rm Hom}(P_{\ell},{\sf G})\leqslant(2e({\sf
G}))^{\lceil\frac{\ell+1}{2}\rceil}\qquad\text{ and }\qquad{\rm Hom}({\sf
H}_{1}\cup{\sf H}_{2},{\sf G})\leqslant{\rm Hom}({\sf H}_{1},{\sf G})\cdot{\rm
Hom}({\sf H}_{2},{\sf G}),$

where for notational convenience we set $P_{0}$ to be the graph containing a
single isolated vertex and $P_{-1}$ to be the empty graph, and ${\sf H}_{1}$
and ${\sf H}_{2}$ vertex disjoint. We then recall the definitions of
$V_{\star}$ and $H_{\star}$ from above to find that
$H_{\star}=\cup_{i=1}^{k}P_{\widetilde{s}_{i}}$ for some sequence
$\\{\widetilde{s}_{i}\\}_{i\in[k]}$ such that
$-1\leqslant\widetilde{s}_{i}\leqslant s_{i}$ for all $i\in[k]$. We claim that

(3.20)
$\sum_{i=1}^{k}\widetilde{s}_{i}\leqslant\sum_{i=1}^{k}s_{i}-\mathfrak{f}_{1}-\mathfrak{f}_{2}\vee\mathfrak{f}_{3}=e(H)-\mathfrak{f}_{1}-\mathfrak{f}_{2}\vee\mathfrak{f}_{3}=v(H)-k-\mathfrak{f}_{1}-\mathfrak{f}_{2}\vee\mathfrak{f}_{3}.$

The equalities in (3.20) follow from the fact that $H$ is a vertex disjoint
union of paths $\\{P_{s_{i}}\\}_{i=1}^{k}$ with $s_{i}\geqslant 1$. To prove
the inequality in (3.20) we consider type I or II frozen edges. Let
$\mathcal{R}$ be the vertices at the left end point of such edges. Clearly
$\mathcal{R}\subset V(H)\cap V(F)$, all elements of $\mathcal{R}$ are
distinct, and $|V(H)\cap
V(F)|\geqslant|\mathcal{R}|=\mathfrak{f}_{1}+\mathfrak{f}_{2}$. By a similar
argument we also have that $|V(H)\cap
V(F)|\geqslant\mathfrak{f}_{1}+\mathfrak{f}_{3}$. Thus $v(H_{\star})\leqslant
v(H)-\mathfrak{f}_{1}-\mathfrak{f}_{2}\vee\mathfrak{f}_{3}$. Then using that
$v(P_{\ell})=\ell+1$ for all $\ell\geqslant-1$ we obtain the inequality in
(3.20).

Equipped with (3.20) we apply (3.19) we deduce that

${\rm Hom}(H_{\star},{\sf G})\lesssim e({\sf
G})^{\sum_{i=1}^{k}(\frac{\widetilde{s}_{i}}{2}+1)}\lesssim(np)^{\sum_{i=1}^{k}\widetilde{s}_{i}+2k}\cdot(\log
n)^{3t}\leqslant(np)^{v(H)+k-\mathfrak{f}_{1}-\mathfrak{f}_{2}\vee\mathfrak{f}_{3}}\cdot(\log
n)^{3t}\\\
=n^{v(H)}p^{e(H)}(np^{2})^{k}(np)^{-(\mathfrak{f}_{1}+\mathfrak{f}_{2}\vee\mathfrak{f}_{3})}\cdot(\log
n)^{3t},$

where in the second step we used that $e({\sf G})=O(n^{2}p^{2}\log n)$,
$v(H)\leqslant 2t$, and $k\leqslant t$, and in the last step we have used
$v(H)=e(H)+k$. This yields (3.18). The proof of the lemma is now complete. ∎

We end this section with the proof of Lemma 3.11. To prove part (a) we will
need to use some standard notion that are used in the proof of Wigner’s
semicircle law, such as words, and graphs associated to words. These are
borrowed from [2, Chapter 2.1.3]. Readers familiar with these notions can skip
the definition below and move straight to the proof of Lemma 3.11.

######  Definition 3.16.

Given a finite set $\mathscr{S}$ an $\mathscr{S}$-word $w$ is a finite
sequence of letters, elements of $\mathscr{S}$, i.e. $w=s_{1}s_{2}\cdots
s_{k}$ for some $k\in\mathbb{N}$. The length of $w$, $\ell(w)$, is defined to
be $k$ and its weight, to be denoted by ${\rm wt}(w)$, is the number of
distinct letters in ${\rm supp}(w):=\\{s_{i},i\in[k]\\}$. The word $w$ is
closed if $s_{1}=s_{k}$. Two $\mathscr{S}$-words are equivalent if there is a
bijection on $\mathscr{S}$ which maps one word to the other. If $\mathscr{S}$
is clear from the context, we refer to $w$ simply as a word.

For a word $w$ as above we let $G(w)$ to be the graph associated with it whose
vertex set is ${\rm supp}(w)$ and the edge set is
$\\{\\{s_{i},s_{i+1}\\},i\in[k]\\}$. Note that for a closed word $w$ this
defines a path starting and ending at the same vertex. For an edge ${\bf e}\in
E(G(w))$ we define $\mathscr{N}_{\bf e}(w)$ to be the number of times this
path traverses the edge ${\bf e}$.

We then let $\mathscr{V}_{k,r}$ to be a set of representatives for the
equivalence classes of closed $[r]$-words $w$ with $\ell(w)=k+1$ and ${\rm
wt}(w)=r$. Define $\mathscr{W}_{k,r}\subset\mathscr{V}_{k,r}$ be the
collection of all $w$ such that $\mathscr{N}_{\bf e}(w)\geqslant 2$ for all
${\bf e}\in E(G(w))$. The set $\mathscr{W}_{k,k/2+1}$ ($k$ must be even) is
said to be the set of all Wigner words.

###### Proof of Lemma 3.11.

Fix a partition $\pi$ so that the quotient subgraph $C_{2t}/\pi$ is simple.
Our strategy would be to associate any such simple quotient graph to $G(w)$
for some appropriately chosen closed word $w$, and then use properties of
$G(w)$.

Towards this end, we observe that for any partition $\pi$ of $[2t]$ there is a
natural choice of a closed word $w=w(\pi)=s_{1}s_{2}\cdots s_{2t+1}$ such that
${\rm wt}(w)$ is the number of parts in the partition $\pi$, and
$\\{s_{1},s_{2},\ldots,s_{i}\\}$ is a discrete interval in $\mathbb{N}$ for
all $i\in[2t+1]$. Let us illustrate it through examples: If
$\pi_{1}=\\{\\{1,3,5\\},\\{2\\},\\{4\\},\\{6\\}\\}$ and
$\pi_{2}=\\{\\{1,3\\},\\{2,4\\},\\{5\\},\\{6\\}\\}$ then $w(\pi_{1})=1213141$
and $w_{2}(\pi)=1212341$. It can be argued that that this map $\pi\mapsto
w(\pi)$ is a bijection between the set of all $\pi$ such that its number of
parts is $r$ and $\mathscr{V}_{2t,r}$. Furthermore, the graphs $G(w(\pi))$ and
$C_{2t}/\pi$ are isomorphic.

Let $\pi$ be such that $\mathscr{N}_{\bf e}(w(\pi))=1$ for some edge ${\bf
e}\in G(w(\pi))$. We claim that $G(w(\pi))$ (or equivalently $C_{2t}/\pi$)
must contain a cycle. To see this, for ease of writing assuming that ${\bf
e}_{0}=(\llbracket 1\rrbracket,\llbracket 2t\rrbracket)$ is traversed only
once we observe that the path induced by the set of edges $\\{(\llbracket
i\rrbracket,\llbracket i+1\rrbracket),i\in[2t-1]\\}$, where $\llbracket
j\rrbracket$ denotes the equivalence class containing the vertex $j$ induced
by $\pi$, does not contain the edge ${\bf e}_{0}$. Therefore there are two
paths between $\llbracket 1\rrbracket$ and $\llbracket 2t\rrbracket$ yielding
the claim.

On the other hand $\mathscr{N}_{\bf e}(w(\pi))\geqslant 1$ for all edge ${\bf
e}$, $e(G(w(\pi)))\geqslant{\rm wt}(w)-1$ and $\sum_{\bf e}\mathscr{N}_{\bf
e}(w(\pi))=2t$, where the lower bound on $e(G(w(\pi)))$ is due to the fact
that $G(w(\pi))$ is connected. This shows that for any $r\geqslant t+2$ such
that ${\rm wt}(w(\pi))=r$ there exists some edge ${\bf e}_{\star}$ such that
$\mathscr{N}_{{\bf e}_{\star}}(w(\pi))=1$. Hence, we conclude that any simple
quotient graph $H=C_{2t}/\pi$ with $v(H)>t+1$ cannot be a tree.

It additionally follows from above that the set of $\pi$ for which that
$C_{2t}/\pi$ is a tree on $(t+1)$ vertices has a bijection with
$\mathscr{W}_{2t,t+1}$. So, the conclusion on the number of trees follows from
the one-to-one correspondence between Wigner words and Dyck paths (cf. [2,
Proof of Lemma 2.1.6]). This completes part (a).

The proof of (b) uses the following well known identity:

(3.21) ${\rm Hom}({\sf H},{\sf G})=\sum_{\pi}N({\sf H}/\pi,{\sf G}),$

where the sum is over all partition $\pi$ of the vertex set $V({\sf H})$ (cf.
[30, Chapter 5]), and we recall that $N({\sf H},{\sf G})$ denotes the number
of labelled copies of ${\sf H}$ in ${\sf G}$. Note that if ${\sf G}$ does not
possess any self-loop then the sum in (3.21) can be restricted to a sum over
$\pi$ such that the graph ${\sf H}/\pi$ is a simple quotient graph. By part
(a), for a simple quotient graph $H=C_{2t}/\pi$ either $e(H)\geqslant v(H)$ or
$e(H)=v(H)-1$ only if $v(H)\leqslant t+1$. Since for any $H$ one has that
$N(H,\mathbb{G}(n,p))=n^{v(H)}p^{e(H)}(1+o(1))$, denoting $\mathscr{T}$ to be
the set of all trees on $(t+1)$ vertices and $\upphi$ to be the trivial
partition (i.e. consisting of only singletons), and using that $np\gg 1$ we
deduce that

$\sum_{\pi:\pi\neq\upphi,C_{2t}/\pi\notin\mathscr{T}}\mathbb{E}[N(C_{2t}/\pi,\mathbb{G}(n,p)]=o(n^{2t}p^{2t})+o(n^{t+1}p^{t}).$

Finally using the bound on the number of simple quotient graphs
$C_{2t}/\pi\in\mathscr{T}$ and (3.21) the proof completes. ∎

###  3.2. Cores with many edges are unlikely

In this section we will prove Lemma 3.8. This will be based on a combinatorial
argument and it will require the following result on the number of graphs with
certain specified properties.

######  Lemma 3.17.

Fix $\varepsilon\in(0,1)$ and $t\in\mathbb{N}$. Let $p$ be such that $(\log
n)^{2t}\ll np\lesssim n^{1/2}$, and $\mathfrak{D}:=\mathfrak{D}(\varepsilon)$
and $D:=D(\varepsilon):=\lceil 32/\varepsilon\rceil$ be intergers such that
$\mathfrak{D}\geqslant D$. Denote

$\mathcal{V}_{1}:=\mathcal{V}_{1}({\sf G}):=\\{v\in V({\sf G}):\deg_{\sf
G}(v)\leqslant\mathfrak{D}\\}$

and $\overline{\mathcal{V}}_{1}:=V({\sf G})\backslash\mathcal{V}_{1}$. Let
$\mathcal{N}({\bm{e}},{\bm{v}},\mathfrak{D})$ be the number of core graphs
${\sf G}$ with $e({\sf G})={\bm{e}}$ and $v({\mathcal{V}}_{1}({\sf
G}))={\bm{v}}$. Then, for all large $n$, we have

$\mathcal{N}({\bm{e}},{\bm{v}},\mathfrak{D})\leqslant\binom{n}{{\bm{v}}}\cdot\exp(\varepsilon{\bm{e}}\log(1/p)).$

Proceeding similarly as in the proof of [8, Lemma 4.7], and using the lemma
below instead of [8, Lemma 3.6], the proof of Lemma 3.17 follows. Therefore,
we spare the details.

######  Lemma 3.18.

Let $p$ satisfy (1.14) and ${\sf G}$ be a core graph. Then, for every edge
${\bf e}=(u,v)\in E({\sf G})$

$\deg_{\sf G}(u)\deg_{\sf
G}(v)\geqslant\frac{\widetilde{c}_{0}(\varepsilon,t)n^{2}p^{2}}{(\log
n)^{2t}},$

for some constant $\widetilde{c}_{0}(\varepsilon,t)>0$.

The proof of Lemma 3.18 is postponed to Appendix B. We now proceed to prove
Lemma 3.8.

###### Proof of Lemma 3.8.

Let $\mathcal{V}_{1}({\sf G})$ be as in Lemma 3.17 with $\mathfrak{D}=D$. Note
that, by Lemma 3.18, there are no edges ${\sf G}$ with both end points in
$\mathcal{V}_{1}$. Therefore, $e({\sf G})\geqslant e(\mathcal{V}_{1}({\sf
G}),\overline{\mathcal{V}}_{1}({\sf G}))\geqslant v(\mathcal{V}_{1}({\sf
G}))$. We claim that

(3.22)
$\mathcal{N}({\bm{e}},{\bm{v}},D)\leqslant\left\\{\begin{array}[]{ll}\exp\left(2(1/3+\varepsilon){\bm{e}}\log(1/p)\right),&\mbox{
if }{\bm{v}}\leqslant{\bm{e}}/3,\\\
\exp\left(\left\\{(1+2\varepsilon)\log(1/p)-\log(np)/3\right\\}{\bm{e}}\right),&\mbox{
otherwise}.\end{array}\right.$

As the probability of any graph ${\sf G}$ with ${\bm{e}}$ edges is
$p^{\bm{e}}$, and upon using that
$t^{-1}\log(1/p)\leqslant\log(np)\leqslant\log(1/p)$, for $p$ satisfying
(1.14), the proof of this lemma follows by taking a union over
$({\bm{e}}_{11},{\bm{e}}_{12},{\bm{v}})$ such that
${\bm{e}}\geqslant\bar{C}_{\star}n^{2}p^{2}$, and
${\bm{e}}_{11},{\bm{e}}_{12}$, and ${\bm{v}}\leqslant n^{2}$.

Thus, it remains to prove (3.22). Since $p\ll n^{-1/2}$ the upper bound in
(3.22) is immediate from Lemma 3.17 when ${\bm{v}}\leqslant{\bm{e}}/3$.
Turning to prove the remaining case we apply Lemma 3.17 again, together with
Stirling’s approximation, to obtain that

$\mathcal{N}({\bm{e}},{\bm{v}},D)\leqslant\left(\frac{en}{{\bm{v}}}\right)^{\bm{v}}\cdot\exp(\varepsilon{\bm{e}}\log(1/p))\leqslant\left(\frac{3en}{\bar{C}_{\star}n^{2}p^{2}}\right)^{\bm{v}}\cdot\exp(\varepsilon{\bm{e}}\log(1/p))\\\
\leqslant\exp\left(\left\\{(1+2\varepsilon)\log(1/p)-\log(np)/3\right\\}{\bm{e}}\right),$

where in the last two steps we have used that ${\bm{v}}\geqslant{\bm{e}}/3$,
and in the penultimate and the final steps we have also used that
${\bm{e}}\geqslant\bar{C}_{\star}n^{2}p^{2}$ and $v(\mathcal{V}_{1}({\sf
G}))\leqslant e({\sf G})$, respectively. This completes the proof. ∎

###  3.3. Probability upper bound on the existence of strong-core graphs

In this section we prove Lemma 3.9. This will require that for all but a few
edges in a strong-core graph, the product of the degrees of two adjacent
vertices satisfy a tight upper and lower bound. First we define the set of
“bad” and “good” edges.

######  Definition 3.19.

Fix $C_{0}<\infty$. Let ${\sf G}_{\rm high}\subset{\sf G}$ be the subgraph
spanned by the edges ${\bf e}=(u,v)\in E({\sf G})$ for which

(3.23) $\deg_{\sf G}(u)\deg_{\sf G}(v)\geqslant C_{0}n^{2}p^{2},$

and set ${\sf G}_{\rm low}:={\sf G}\backslash{\sf G}_{\rm high}$.

The next lemma shows that a careful choice of $C_{0}$ in (3.23) yields that
${\rm Hom}(C_{2t},{\sf G})$ almost same as ${\rm Hom}(C_{2t},{\sf G}_{\rm
low})$, while keeping the number of edges in ${\sf G}_{\rm high}$ small. It
also provides a lower bound on the product of the degree of two adjacent
vertices. The proof is postponed to Appendix B.

######  Lemma 3.20.

Consider the same setup as in Lemma 3.8. Let ${\sf G}$ be a strong-core graph.
There exist constants $0<c_{0}(\varepsilon,t),C_{0}(\varepsilon,t)<\infty$
such that the followings hold:

  1. (a)

For every edge ${\bf e}=(u,v)\in E({\sf G})$

$\deg_{\sf G}(u)\deg_{\sf G}(v)\geqslant{c_{0}(\varepsilon,t)n^{2}p^{2}}.$

  2. (b)

Let ${\sf G}_{\rm high}={\sf G}_{\rm high}(\varepsilon,t)$ and ${\sf G}_{\rm
low}={\sf G}_{\rm low}(\varepsilon,t)$ be as in Definition 3.19 with
$C_{0}=C_{0}(\varepsilon,t)$ in (3.23). Then

${\rm Hom}(C_{2t},{\sf G}_{\rm low})\geqslant(1-\varepsilon){\rm
Hom}(C_{2t},{\sf G})\qquad\text{ and }\qquad e({\sf G}_{\rm
high})\leqslant\varepsilon e({\sf G}).$

We now prove Lemma 3.9.

###### Proof of Lemma 3.9.

In the first step we decompose a strong-core graph ${\sf G}$ into three
subgraphs: one is a bipartite graph with edges between vertices of low and
high degrees only, the second subgraph consisting of vertices of large
degrees, and the third consisting of negligible many edges. Furthermore,
almost all the homomorphisms of $C_{2t}$ into ${\sf G}$ are contained in the
first two subgraphs.

To carry out this step we need to introduce several notation. Let
$D=D(\varepsilon)$ be as in Lemma 3.17, and $C_{0}=C_{0}(\varepsilon,t)$ and
$c_{0}=c_{0}(\varepsilon,t)$ be as in Lemma 3.20. Set $D_{0}:=0$,

(3.24)
$\widetilde{C}=\widetilde{C}(\varepsilon,t):=(t-1)\left(\left\lceil\frac{(2\bar{C}_{\star})^{t}}{\varepsilon\widehat{\delta}}\right\rceil+2\right),\qquad\text{
and }\qquad D_{i}:=D\cdot\left(\frac{C_{0}}{c_{0}}\right)^{i-1},\text{ for
}i\in[\widetilde{C}].$

Define $\widetilde{V}_{0}:=\varnothing$. Then, for $i\in[\widetilde{C}]$ we
(iteratively) define

$V_{i}=V_{i}({\sf G}):=\left\\{v\in V({\sf G}_{\rm
low}):D_{i-1}+1\leqslant\deg_{\sf G}(v)\leqslant D_{i}\right\\}$

and

$\widetilde{V}_{i}=\widetilde{V}_{i}({\sf G}):=\left\\{v\in V({\sf G}_{\rm
low}):(u,v)\in E({\sf G}_{\rm low})\text{ for some }u\in
V_{i}\right\\}\backslash\widetilde{V}_{i-1}.$

We further define ${\sf H}_{i}$ to be the subgraph (of ${\sf G}_{\rm low}$)
spanned by the edges that are incident to some vertex in
$\cup_{j=1}^{i}V_{j}$, and $\bar{\sf H}_{i}={\sf G}_{\rm low}\backslash{\sf
H}_{i}$. Note that, by Lemma 3.20, $\\{{\sf H}_{i}\\}_{i=1}^{\widetilde{C}}$
are bipartite graphs.

We now claim that there exists an $i\in[\widetilde{C}]$ such that

(3.25) ${\rm Hom}(C_{2t},{\sf H}_{i})+{\rm Hom}(C_{2t},\bar{\sf
H}_{i})\geqslant\widehat{\delta}(1-8\varepsilon)n^{2t}p^{2t}.$

To derive this claim we observe that there exists an $i\in[\widetilde{C}-t+1]$
such that

(3.26) ${\rm Hom}(C_{2t},{\sf H}_{i+(t-1)})-{\rm Hom}(C_{2t},{\sf
H}_{i})\leqslant\varepsilon\widehat{\delta}n^{2t}p^{2t}.$

Otherwise, as for a graph ${\sf G}$ and a bipartite graph $\widetilde{\sf G}$
one has that

(3.27) ${\rm Hom}(C_{2t},{\sf G})\leqslant(2e({\sf G}))^{t}\qquad\text{ and
}\qquad{\rm Hom}(C_{2t},\widetilde{\sf G})\leqslant 2(e(\widetilde{\sf
G}))^{t},$

it follows that

${\rm Hom}(C_{2t},{\sf
G})\geqslant\left[\sum_{k=1}^{\widetilde{C}/(t-1)-1}{\rm Hom}(C_{2t},{\sf
H}_{k(t-1)+1})-{\rm Hom}(C_{2t},{\sf H}_{(t-1)(k-1)+1})\right]+{\rm
Hom}(C_{2t},{\sf H}_{1})\\\
\geqslant\left(\frac{\widetilde{C}}{t-1}-1\right)\varepsilon\widehat{\delta}n^{2t}p^{2t}>(2\bar{C}_{\star})^{t}n^{2t}p^{2t},$

(recall the definition of $\widetilde{C}$) yielding a contradiction to the
fact that $e({\sf G})\leqslant\bar{C}_{\star}n^{2}p^{2}$.

Recalling the definition of $\\{D_{k}\\}_{k=1}^{\widetilde{C}}$, and using the
tight upper and lower bounds on the product of the degrees of adjacent
vertices in ${\sf G}_{\rm low}$ given by Lemma 3.20, we further deduce that
any edge in $\bar{\sf H}_{k}$ that is incident to some edge in ${\sf H}_{k}$
must be contained in ${\sf H}_{k+1}$. Therefore, as the distance between any
two vertices of same parity in $C_{2t}$ is at most $(t-1)$, by induction we
derive that any homomorphism of $C_{2t}$ that uses edges of both ${\sf H}_{i}$
and $\bar{\sf H}_{i}$ must be contained in ${\sf H}_{i+(t-1)}$, but not in
${\sf H}_{i}$. Hence, by (3.26), we also obtain that the number of such
homomorphisms is at most $\varepsilon\widehat{\delta}(np)^{2t}$. As any
homomorphism of $C_{2t}$ into ${\sf G}_{\rm low}$ must either be fully
contained in ${\sf H}_{i}$ or $\bar{\sf H}_{i}$, or must use edges of both
${\sf H}_{i}$ and $\bar{\sf H}_{i}$, an application of Lemma 3.20(b) now
yields the claim (3.25). This concludes the first step.

It now remains to find an upper bound on the probability of the existence of a
strong-core subgraph $\mathbb{G}(n,p)$ such that (3.25) holds. This would be
the second step of the proof. Turning to do this we introduce a few more
notation. Let

$\mathcal{I}_{i,{\bm{e}}}:=\left\\{{\sf G}:{\sf G}\text{ strong-core},e({\sf
G})={\bm{e}},{\rm Hom}(C_{2t},{\sf H}_{i})+{\rm Hom}(C_{2t},\bar{\sf
H}_{i})\geqslant\widehat{\delta}(1-8\varepsilon)n^{2t}p^{2t}\right\\},$
$\mathcal{I}_{i,j,{\bm{e}},{\bm{e}}_{\sharp}}:=\left\\{{\sf G}:{\sf
G}\in\mathcal{I}_{i,{\bm{e}}},e({\sf
H}_{i})={\bm{e}}_{\sharp},(j-1)\varepsilon\widehat{\delta}\leqslant{\rm
Hom}(C_{2t},{\sf H}_{i})/(np)^{2t}\leqslant
j\varepsilon\widehat{\delta}\right\\},\quad j\in[s_{0}],$

where $s_{0}:=\lfloor(1-10\varepsilon)/\varepsilon\rfloor$, and

$\mathcal{I}_{i,s_{0}+1,{\bm{e}},{\bm{e}}_{\sharp}}:=\left\\{\exists{\sf
G}:{\sf G}\in\mathcal{I}_{i,{\bm{e}}},e({\sf H}_{i})={\bm{e}}_{\sharp},{\rm
Hom}(C_{2t},{\sf H}_{i})/(np)^{2t}\geqslant
s_{0}\varepsilon\widehat{\delta}\right\\}.$

Denote

$\mathcal{J}_{i,j,{\bm{e}},{\bm{e}}_{\sharp}}:=\left\\{\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf
G}\in\mathcal{I}_{i,j,{\bm{e}},{\bm{e}}_{\sharp}}\right\\},\quad
j\in[s_{0}+1].$

Observe that it suffices to show the following bounds:

(3.28)
$\mathbb{P}(\cup_{i,{\bm{e}},{\bm{e}}_{\sharp}}\mathcal{J}_{i,1,{\bm{e}},{\bm{e}}_{\sharp}})\leqslant\exp\left(-\frac{1}{2}\widehat{\delta}^{1/t}(1-\widetilde{\beta}\varepsilon)n^{2}p^{2}\log(1/p)\right),$
(3.29)
$\mathbb{P}\left(\cup_{i,{\bm{e}},{\bm{e}}_{\sharp}}\cup_{j=2}^{s_{0}}\mathcal{J}_{i,j,{\bm{e}},{\bm{e}}_{\sharp}}\right)\leqslant\exp\left(-\phi_{t}(\widehat{\delta})(1-\widetilde{\beta}\varepsilon)^{1/t}(1+\beta_{\star}\varepsilon^{1/t})+\widehat{\beta}t\varepsilon\phi_{t}(\widehat{\delta})\right),$

(recall (3.6)) and

(3.30)
$\mathbb{P}(\cup_{i,{\bm{e}},{\bm{e}}_{\sharp}}\mathcal{J}_{i,s_{0}+1,{\bm{e}},{\bm{e}}_{\sharp}})\leqslant\exp\left(-\phi_{t}(\widehat{\delta})(1-\widetilde{\beta}t\varepsilon)\right),$

where the unions in $i,j,{\bm{e}}$, and ${\bm{e}}_{\sharp}$ are taken over
their allowable ranges, and $\widetilde{\beta},\widehat{\beta}$, and
$\beta_{\star}$ are some absolute constants.

To prove (3.28)-(3.30) we let ${\bm{v}}_{\sharp}({\sf
G}):=|\cup_{j=1}^{i}V_{j}|$, and split into two cases: ${\bm{v}}_{\sharp}({\sf
G})={\bm{v}}_{\sharp}\leqslant\varepsilon e({\sf G})={\bm{e}}$ and
${\bm{v}}_{\sharp}>\varepsilon{\bm{e}}$. In the first case, applying Lemma
3.17 with

$\mathcal{V}_{1}=\cup_{j=1}^{i}V_{j}\cup\left\\{v\in V({\sf G}_{\rm
high}):\deg_{\sf G}(v)\leqslant D_{i}\right\\}$

and $\mathfrak{D}=D_{i}$ we find that the number of core graphs under
consideration can be bounded by

$\binom{n}{v}\left(\frac{1}{p}\right)^{\varepsilon{\bm{e}}}\leqslant\exp\left(8\varepsilon{\bm{e}}\log(1/p)\right),$

where we also used
$|\mathcal{V}_{1}|={\bm{v}}\leqslant{\bm{v}}_{\sharp}+2\varepsilon e({\sf G})$
(follows from Lemma 3.20(b) and $p\ll n^{-1/2}$). Since, by (3.27), for any
strong-core graph ${\sf G}$ one has the bound $e({\sf
G})\geqslant{\bm{e}}_{0}:=\frac{1}{2}\widehat{\delta}^{1/t}(1-8\varepsilon)^{1/t}n^{2}p^{2}$
and the probability of a graph ${\sf G}$ with ${\bm{e}}$ edges is
$p^{\bm{e}}$, using the union bound, we derive that

(3.31)
$\mathbb{P}\left(\cup_{i,{\bm{e}},{\bm{v}},{\bm{v}}_{\sharp}\leqslant\varepsilon{\bm{e}}_{\sharp}}\left\\{\exists{\sf
G}\subset\mathbb{G}(n,p):{\sf
G}\in\mathcal{I}_{i,j,{\bm{e}},{\bm{e}}_{\sharp}},{\bm{v}}_{\sharp}({\sf
G})={\bm{v}}_{\sharp}\right\\}\right)\leqslant\exp\left(-\frac{1}{2}\widehat{\delta}^{1/t}(1-\beta_{0}\varepsilon)n^{2}p^{2}\log(1/p)\right),$

for some absolute constant $\beta_{0}<\infty$ and all large $n$.

In the second case, using the lower bound ${\bm{e}}\geqslant{\bm{e}}_{0}$ we
obtain that

$\binom{n}{{\bm{v}}}\leqslant\left(\frac{4e}{\varepsilon\widehat{\delta}^{1/t}}\right)^{\bm{v}}\cdot\left(\frac{1}{p}\right)^{{\bm{v}}}\cdot\left(\frac{1}{np}\right)^{{\bm{v}}_{\sharp}}.$

Therefore, applications of Lemmas 3.17 and 3.20(b) now yield that

(3.32) $\mathbb{P}\left(\exists{\sf G}\subset\mathbb{G}(n,p):{\sf
G}\in\mathcal{I}_{i,j,{\bm{e}},{\bm{e}}_{\sharp}},{\bm{v}}_{\sharp}({\sf
G})={\bm{v}}_{\sharp}>\varepsilon{\bm{e}}\right)\\\
\leqslant\exp\left(-\log(1/p)({\bm{e}}-{\bm{e}}_{\sharp})-\log(1/p)({\bm{e}}_{\sharp}-{\bm{v}}_{\sharp})-\log(np){\bm{v}}_{\sharp}+4\varepsilon{\bm{e}}\log(1/p)\right),$

for all large $n$. We now need an upper bound on the rhs of (3.32). To obtain
such a bound we note that, if ${\rm Hom}(C_{2t},\bar{\sf
H}_{i})\geqslant\eta_{1}\widehat{\delta}(np)^{2t}$ and ${\rm Hom}(C_{2t},{\sf
H}_{i})\geqslant\eta_{2}\widehat{\delta}(np)^{2t}$ then by (3.27) and
recalling that ${\sf H}_{i}$ is a bipartite graph one has that

(3.33)
${\bm{e}}-{\bm{e}}_{\sharp}\geqslant\frac{1}{2}\eta_{1}^{1/t}\widehat{\delta}^{1/t}n^{2}p^{2}$

and

(3.34)
$\log(1/p)({\bm{e}}_{\sharp}-{\bm{v}}_{\sharp})+\log(np){\bm{v}}_{\sharp}\geqslant\log(np)(1-o(1)){\bm{e}}_{\sharp}\geqslant\eta_{2}^{1/t}\left(\frac{\widehat{\delta}}{2}\right)^{1/t}n^{2}p^{2}\log(np)(1-o(1)).$

On the other hand, as $p$ satisfies (1.14) and
${\bm{e}}\leqslant\bar{C}_{\star}n^{2}p^{2}$ (see also remark 3.10), we have

(3.35)
${\bm{e}}\log(1/p)=O(\widehat{\delta}^{1/t}n^{2}p^{2}\log(1/p))=O(t\phi_{t}(\widehat{\delta})).$

Now, we apply (3.33) with $\eta_{1}=1-10\varepsilon$, and (3.35) to obtain a
bound on the rhs of (3.32) for $j=1$. Taking a union over the allowable ranges
of $i,{\bm{v}},{\bm{v}}_{\sharp},{\bm{e}}$, and ${\bm{e}}_{\sharp}$, and using
the bound in (3.31) we then deduce (3.28).

Next, we apply (3.34) with $\eta_{2}=1-11\varepsilon$ to obtain a bound on the
rhs of (3.32) for $j=s_{0}+1$. Therefore, using (3.35) again and proceeding
similarly as in the case of $j=1$ we derive (3.30).

To prove (3.29) we fix $j_{0}\in\\{2,3,\ldots,s_{0}\\}$, and apply (3.33) and
(3.34) with $\eta_{1}=1-9\varepsilon-j_{0}\varepsilon$ and
$\eta_{2}=(j_{0}-1)\varepsilon$, respectively. Since $1\leqslant
j_{0}-1\leqslant j_{0}\leqslant(1/\varepsilon-10)$, by the definition of
$s_{0}$, we find that

$\eta_{1}^{1/t}+\eta_{2}^{1/t}\geqslant(1-10\varepsilon)^{1/t}\cdot\left(1+\frac{1}{4}\varepsilon^{1/t}\right).$

Therefore,

(3.36)
$\log(1/p)({\bm{e}}-{\bm{e}}_{\sharp})+\log(1/p)({\bm{e}}_{\sharp}-{\bm{v}}_{\sharp})+\log(np){\bm{v}}_{\sharp}\geqslant(1-o(1))\cdot(\eta_{1}^{1/t}+\eta_{2}^{1/t})\phi_{t}(\widehat{\delta})\\\
\geqslant\phi_{t}(\widehat{\delta})\cdot(1-\beta_{0}\varepsilon)^{1/t}\left(1+\frac{\varepsilon^{1/t}}{4}\right).$

Plugging this bound and (3.35) in (3.32), followed be a union over
$i,j,{\bm{v}},{\bm{v}}_{\sharp},{\bm{e}}$, and ${\bm{e}}_{\sharp}$ over their
respective allowable ranges, and using (3.31) we now establish (3.29). This
completes the proof. ∎

##  4\. Proof of Corollary 1.7