# Moderate Deviations in Triangle Count

Joe Neeman and Charles Radin and Lorenzo Sadun  Joe Neeman
Department of Mathematics
The University of Texas at Austin
Austin, TX 78712<EMAIL_ADDRESS>Charles Radin
Department of Mathematics
The University of Texas at Austin
Austin, TX 78712<EMAIL_ADDRESS>Lorenzo Sadun
Department of Mathematics
The University of Texas at Austin
Austin, TX 78712<EMAIL_ADDRESS>
###### Abstract.

We prove moderate deviations bounds for the lower tail of the number of
triangles in a $\mathcal{G}(n,m)$ random graph. We show that the probability
of decreasing the triangle density by $t$, with $n^{-3/4}\ll t\ll 1$, is
$\exp(-\Theta(n^{2}t^{2/3}))$; we find the leading coefficient in the exponent
for $m\geq\frac{1}{2}\binom{n}{2}$, and estimate it otherwise. This
complements results of Goldschmidt et al., who showed that for $n^{-3/2}\ll
t\ll n^{-1}$, the probability is $\exp(-\Theta(n^{3}t^{2}))$. That is,
moderate deviations behave much like small deviations for $t\ll n^{-1}$ and
much like large deviations for $n^{-3/4}\ll t$. We conjecture a sharp change
between the two regimes at $t=\Theta(n^{-3/4})$, which we associate with a
single large negative eigenvalue of the adjacency matrix becoming responsible
for almost all of the triangle deficit.

Our results can be interpreted as finite size effects in phase transitions in
constrained edge-triangle graphs.

This work was partially supported by the Deutsche Forschungsgemeinschaft (DFG,
German Research Foundation) under Germany’s Excellence Strategy – EXC-2047/1 –
390685813, and by a fellowship from the Alfred P. Sloan Foundation.

##  1\. Introduction

We prove moderate deviations bounds for the lower tail of the number of
triangles in a $\mathcal{G}(n,m)$ random graph, for deviations larger than
those of Goldschmidt et al. [1] but smaller than large deviations, which are
of order the mean of the triangle density. For instance, with the notation
that $\tau(G)$ is the triangle density of a $\mathcal{G}(n,m)$ graph $G$ where
$n\to\infty$ and $m=p\binom{n}{2}+O(1)$, for some $1/2\leq p<1$ that is fixed
as $n\to\infty$ and $n^{-3/4}\ll t\ll 1$, we prove (see Theorem 1) that

(1) $\Pr\left(\tau(G)\leq
p^{3}-t\right)=\exp\left(-\frac{\ln\frac{p}{1-p}}{2(2p-1)}t^{2/3}n^{2}+o(t^{2/3}n^{2})\right).$

The number of triangles in a random graph is a fundamental and surprisingly
important random variable in the study of probabilistic combinatorics. The
probabilistic behavior of these triangle counts is at least partially
responsible for the development of many important methods related to
concentration inequalities for dependent random variables, including Janson’s
inequality [2], the entropy method [3], martingale difference techniques in
random graphs, and others [4].

The traditional point of view, as exemplified by the seminal paper by Janson
and Rucínski [5], holds that the lower tail of the triangle count is easy to
characterize while the upper tail is hard. This view stems at least partly
from the fact that most earlier works studied the $\mathcal{G}(n,p)$ model, in
which edges appear independently, each with probability $p$. In the
$\mathcal{G}(n,m)$ model, in which the number of edges is fixed at $m$, the
situation is rather more subtle. For example, one can easily see that under
$\mathcal{G}(n,p)$, the number of triangles, $T(G)$, satisfies
$\operatorname{Var}(T(G))=\Theta(n^{4})$, while under $\mathcal{G}(n,m)$,
$\operatorname{Var}(T(G))=\Theta(n^{3})$. The distinction between the two
models – especially in the lower tail – becomes even more pronounced at larger
deviations. This can be intuitively explained by the fact that in
$\mathcal{G}(n,p)$ one can easily “depress” the triangle count simply by
reducing the number of edges: a graph $G$ with edge number $|E(G)|\approx
q\binom{n}{2}$ will typically have triangle density $\tau\approxeq q^{3}$, and
the probability of seeing such a graph under $\mathcal{G}(n,p)$ is of the
order $\exp(-\Theta(n^{2}(p-q)^{2}))$; it follows that under
$\mathcal{G}(n,p)$ we have

(2) $\Pr(\tau(G)\leq\mathbb{E}\tau(G)-t)\geq\exp(-\Omega(n^{2}t^{2})).$

Under $\mathcal{G}(n,m)$, large deficits in the triangle density are much
rarer than they are in $\mathcal{G}(n,p)$. At the scale of constant-order
deficits, this was noticed in [6, 7], where it is proved that for
$t=\Theta(1)$ and $\mathcal{G}(n,m)$ with $m=\Theta(n^{2})$,

(3) $\Pr(\tau(G)\leq\mathbb{E}\tau(G)-t)=\exp(-\Theta(n^{2}t^{2/3})).$

(They also found the exact leading-order term in the exponent when
$m=\frac{1}{2}\binom{n}{2}+o(n^{2})$ and bounded the leading-order coefficient
for all other values of $m$.) At the other end of the scale, a recent result
of Goldschmidt et al. [1] showed that for $n^{-3/2}\ll t\ll n^{-1}$ the lower
triangle tail has a different behavior:

(4) $\Pr(\tau(G)\leq\mathbb{E}\tau(G)-t)=\exp(-\Theta(n^{3}t^{2})).$

(Again, they also found the exact leading-order term in the exponent.) Since
$t\leq\Theta(n^{-3/2})$ is within the range of the Central Limit Theorem this
leaves open the case of $n^{-1}\ll t\ll 1$. Noting that the two exponential
rates (namely $n^{2}t^{2/3}$ and $n^{3}t^{2}$) cross over at
$t=\Theta(n^{-3/4})$, it is natural to guess that

(5)
$\Pr(\tau(G)\leq\mathbb{E}\tau(G)-t)=\begin{cases}\exp(-\Theta(n^{3}t^{2}))&\text{if
$t\ll n^{-3/4}$},\\\ \exp(-\Theta(n^{2}t^{2/3}))&\text{if $n^{-3/4}\ll t\ll
1$}.\end{cases}$

We prove the second of these two cases (see Theorem 2); the first remains a
conjecture. We also prove some structural results on graphs with
$\tau(G)\leq\mathbb{E}\tau(G)-\omega(n^{-3/4})$. These structural results
provide a plausible explanation for the importance of $t=\Theta(n^{-3/4})$,
namely that it is the threshold at which a single large negative eigenvalue of
the adjacency matrix becomes responsible for almost all of the triangle
deficit.

##  2\. Context and references

We are concerned with random graphs, more specifically with
$\mathcal{G}(n,m)$, the uniform distribution on graphs on $n$ nodes with $m$
edges, rather than the more common model $\mathcal{G}(n,p)$, in which the
edges are independent with probability $p$. For either of these random graph
models one can study the distribution of subgraph counts, for instance
triangle counts or triangle density (density being the quotient of the count
by the count in the complete graph) with which we are concerned. Results on
the probability of deviations of triangle density from the mean fall into
three classes by size: small deviations, on the order of the standard
deviation, large deviations, on the order of the mean, and moderate
deviations, of intermediate size.

Our main results concern the moderate regime of deviations of triangle density
in $\mathcal{G}(n,m)$, in which we prove, among other things, that deviations
near but below the large class are qualitatively different from deviations
near but above the small class. We know of no other results of this sort, for
$\mathcal{G}(n,m)$ or $\mathcal{G}(n,p)$.

For small deviations there is a long history under the name Central Limit
Theorem. There are also many papers on moderate and large deviations of
subgraph counts. As background, more specifically for results discussed here,
we suggest the following: [8, 9, 10, 11, 12, 13, 14, 15, 16] and references
within them for a broader view. As our results are strongly colored by large
deviations we note in particular [17].

For convenience we note some common asymptotics notation. We use $f=o(g)$ or
$f\ll g$ to mean $\lim|f(n)|/g(n)=0$, $f=O(g)$ to mean $\lim\sup
f(n)/g(n)<\infty$, $f=\Omega(g)$ to mean $\lim\inf f(n)/g(n)>0$, $f=\omega(g)$
or $f\gg g$ to mean $\lim|f|/g=\infty$, and $f=\Theta(g)$ to mean both
$f=O(g)$ and $f=\Omega(g)$. The phrase “with high probability” means “with
probability converging to 1 as $n\to\infty$,” and we also make use of
probabilistic asymptotic notation: “$f=O(g)$ with high probability” means that
for every $\epsilon>0$ there exists $C>0$ with $\limsup\Pr(f\geq
Cg)\leq\epsilon$; “$f=o(g)$ with high probability” means that for every
$\epsilon>0$, $|f|/g\leq\epsilon$ with high probability; and analogously for
$\Omega$ and $\omega$.

More specifically we are studying the triangle density of $\mathcal{G}(n,m)$
graphs in the range $\tau(G)=p^{3}-t$ for $n^{-3/4}\ll t\ll 1$. The case
$0\leq t\leq\Omega(n^{-3/2})$ is within the range of the Central Limit Theorem
(and it is covered by Janson’s more general work on subgraph statistics [18]).
The range $n^{-3/2}\ll t\ll n^{-1}$ is studied by [1]; they showed that in
this regime

(6) $\Pr(\tau(G)\leq
p^{3}-t)=\exp\left(-\frac{t^{2}n^{3}}{2\sigma_{p}^{2}}(1+o(1))\right),$

where $\sigma_{p}^{2}=\operatorname{Var}(\tau(G))/n^{3}$, which is of constant
order. They also show an upper bound for larger $t$: for $n^{-3/2}\ll t\ll 1$,

(7) $\Pr(\tau(G)\leq p^{3}-t)=\exp\left(-\Omega(t^{2}n^{3})\right).$

We show that this is not tight for $n^{-3/4}\ll t\ll 1$. For example, we show
that in this range,

(8) $\Pr(\tau(G)\leq p^{3}-t)=\exp\left(-\Theta(t^{2/3}n^{2})\right).$

In the case $p\geq\frac{1}{2}$, we also derive more detailed results (see
Theorem 1): we identify the leading constant in the exponent and prove some
results on the spectrum of the adjacency matrix of $G$.

###  2.1. Related work on random graphs

Besides the work of [1], there is related work on large deviation principles
(LDPs) for more general statistics, and LDPs for sparser graphs, notably in
[19].

Moderate deviations in triangle count in $\mathcal{G}(n,m)$ can be seen from a
different vantage based on [20]. That paper follows a series of works [6, 7,
24, 22, 23, 25, 26] on the asymptotics of ‘constrained’ random graphs, in
particular the asymptotics of $\mathcal{G}(n,m,t)$, the uniform distribution
on graphs on $n$ nodes constrained to have $m$ edges and $t$ triangles. A
large deviation principle, using optimization over graphons, a variant of the
seminal work [27] by Chatterjee and Varadhan on large deviations in
$\mathcal{G}(n,p)$, was used to prove various features of phase transitions
between asymptotic ‘phases’, phases illustrated by the entropy-optimal
graphons. (See also [28].) But in [20] numerical evidence showed that the
transitions could be clearly seen in finite systems, using constrained graphs
with as few as 30 vertices. From this perspective moderate deviations in
triangle count can be understood as finite size effects in a phase transition.
Asymptotically, entropy goes through a sharp ridge as the edge
density/triangle density pair $(\varepsilon,\tau)$ passes through
$(\varepsilon,\varepsilon^{3})$ (Thms. 1.1,1.2 in [7]), and moderate
deviations quantify how the sharp ridge rounds off at finite node number,
somewhat as an ice cube freezing in water has rounded edges. The focus thus
shifts to the infinite system, where emergent phases are meaningful, away from
$\mathcal{G}(n,m,t)$ or $\mathcal{G}(n,m)$.

###  2.2. Related work on random matrices

Since we are studying the spectrum of the adjacency matrix, our methods mainly
come from random matrix theory. Specifically, we are interested in large
deviations of eigenvalues of the random adjacency matrices coming from our
random graphs. The study of large deviations of eigenvalues is an active
topic, but the results we aim for are somewhat atypical. Traditionally, “large
deviations” refers to deviations on the order of the mean, so large deviations
results for random matrices typically consider the event that the largest
eigenvalue of a symmetric $n\times n$ matrix with i.i.d. mean-zero,
variance-$\sigma^{2}$ entries is of order $\alpha\sqrt{n}$ for
$\alpha>2\sigma$; this is because the typical value of the largest eigenvalue
is of order $2\sigma\sqrt{n}$. However, because an eigenvalue of order
$n^{\beta}$ contributes $n^{3\beta}$ to the triangle count, and because we are
interested in triangle deviation of orders $n^{9/4}$ through $n^{3}$, we are
necessarily interested in much larger eigenvalues.

Another difference in our work is that we consider several large eigenvalues
simultaneously. This is because we need to consider the possibility that the
triangle count is affected by several atypically large eigenvalues instead of
just one.

In related work,

  * •

Guionnet and Husson [29] showed an LDP for the largest eigenvalue for a family
of random matrices that includes Rademacher matrices, which is essentially the
case that we consider when $p=\frac{1}{2}$.

  * •

Augeri [30] showed an LDP for the largest eigenvalue for random matrices whose
entries have heavier-than-Gaussian tails.

  * •

Battacharya and Ganguly [31] showed an LDP for the largest eigenvalue of an
Erdős-Rényi graph. Their setting differs from the others in that the random
matrices they consider are not centered (which makes a big difference when
studying the largest eigenvalue).

  * •

Augeri, Guionnet, and Husson [32] showed an LDP for the largest eigenvalue for
most random matrices with subgaussian elements. These are essentially the same
random matrices that we consider, with the main difference being that they are
looking at eigenvalues of size $\Theta(\sqrt{n})$.

##  3\. Triangle counts

Our general setting is: we let $A$ be the adjacency matrix of a
$\mathcal{G}(n,m)$ graph, where $n\to\infty$ and $m=p\binom{n}{2}+O(1)$, for
some $p\in\mathbb{R}$ that is fixed as $n\to\infty$. We denote by $\tau(A)$
the triangle density of $A$, and by $\lambda_{n}(A)$ the smallest eigenvalue
of $A$.

We prove two theorems governing asymptotic behavior as $n\to\infty$ and
$n^{-3/4}\ll t\ll 1$. The first is a strong result for $\frac{1}{2}\leq p<1$.

######  Theorem 1.

If $\frac{1}{2}\leq p<1$ and $n^{-3/4}\ll t\ll 1$ then

(9) $\Pr\left(\tau(A)\leq
p^{3}-t\right)=\exp\left(-\frac{\ln\frac{1-p}{p}}{2(1-2p)}t^{2/3}n^{2}+o(t^{2/3}n^{2})\right),$

with the convention that $\frac{\ln\frac{1-p}{p}}{1-2p}=2$ when
$p=\frac{1}{2}$. Moreover, conditioned on $\tau(A)\leq p^{3}-t$, with high
probability we have

(10) $\lambda_{n}^{3}(A)=-tn^{3}(1-o(1))$

and $\lambda_{n-1}^{3}(A)\geq-o(tn^{3})$.

The second result, for $0<p\leq\frac{1}{2}$, is weaker.

######  Theorem 2.

If $0<p\leq\frac{1}{2}$ and $n^{-3/4}\ll t\ll 1$ then $\Pr\left(\tau(G)\leq
p^{3}-t\right)$ is bounded above by

(11)
$\exp\left(-\frac{\ln\frac{p}{1-p}}{2(2p-1)}t^{2/3}n^{2}+o(t^{2/3}n^{2})\right)$

and bounded below by

(12) $\exp\left(-\frac{1}{2p(1-p)}t^{2/3}n^{2}+o(t^{2/3}n^{2})\right).$

Moreover, conditioned on $\tau(A)\leq p^{3}-t$, with high probability we have

(13) $\lambda_{n}^{3}(A)=-\Omega(tn^{3}).$

Together, these theorems show that $p(\tau(A)\leq
p^{3}-t)=\exp(-\Theta(t^{2/3}n^{2}))$ for all $0<p<1$.

###  3.1. Centering the matrix

The main point of this section is that when considering the lower tail for
triangle counts in $\mathcal{G}(n,m)$ graphs, it suffices to look at
eigenvalues of the centered adjacency matrix. This might sound obvious, but
there are two subtleties:

  1. (1)

It is important that we are looking at the lower tail, because the upper tail
probabilities are controlled by perturbations to the largest eigenvector; this
is exactly the eigenvector that gets destroyed when we center the adjacency
matrix, so the eigenvalues of the centered adjacency matrix don’t give much
information about the upper tail probabilities.

  2. (2)

It is important that we are looking at $\mathcal{G}(n,m)$ and not
$\mathcal{G}(n,p)$, because – as discussed in the introduction – in
$\mathcal{G}(n,p)$ the entropically favorable way to reduce the triangle count
is to reduce the number of edges; again, this primarily affects the largest
eigenvector and so is not related to the centered adjacency matrix.

######  Lemma 3.

Let $A$ be the adjacency matrix of a graph with $n$ vertices and $m$ edges.
For any $p\in\mathbb{R}$,

(14)
$\operatorname{tr}[(A-p\mathbf{1}+pI)^{3}]=\operatorname{tr}[A^{3}]-p^{3}n^{3}+p^{3}n+6mp(np-2p+1)+3p^{3}n(n-1)-3p\sum_{i}d_{i}^{2},$

where $d_{i}$ is the degree of vertex $i$. Or, if $p=m/\binom{n}{2}$, then

(15)
$\operatorname{tr}[(A-p\mathbf{1}+pI)^{3}]\leq\operatorname{tr}[A^{3}]-p^{3}n^{3}+p^{3}n+6mp.$

Note that if $A$ is sampled from $\mathcal{G}(n,m)$ and $p=m/\binom{n}{2}$
then $\mathbb{E}A=p\mathbf{1}-pI$, and so the quantity of interest in Lemma 3
is in fact the centered adjacency matrix $A-\mathbb{E}A$.

###### Proof.

We expand everything in gory detail:

$\displaystyle\operatorname{tr}[(A-p\mathbf{1}+pI)^{3}]-\operatorname{tr}[A^{3}]+p^{3}\operatorname{tr}[\mathbf{1}^{3}]-p^{3}\operatorname{tr}[I^{3}]$
$\displaystyle=3\operatorname{tr}[-pA^{2}\mathbf{1}+p^{2}A\mathbf{1}^{2}+pA^{2}I+p^{2}AI^{2}+p^{3}\mathbf{1}^{2}I-p^{3}\mathbf{1}I^{2}-2p^{2}A\mathbf{1}I]$
$\displaystyle=3\operatorname{tr}[-pA^{2}\mathbf{1}+np^{2}A\mathbf{1}+pA^{2}+p^{2}A+np^{3}\mathbf{1}-p^{3}\mathbf{1}-2p^{2}A\mathbf{1}]$
$\displaystyle=3(-p\operatorname{tr}[A^{2}\mathbf{1}]+2(n-2)p^{2}m+2pm+0+n^{2}p^{3}-np^{3}),$

where we used the fact that $\operatorname{tr}[A\mathbf{1}]$ is the sum of the
entries of $A$ and $\operatorname{tr}[A^{2}]$ is the sum of squares of entries
of $A$; since $A$ is an adjacency matrix, both of these are $2m$. Finally,

(16)
$\operatorname{tr}[A^{2}\mathbf{1}]=\sum_{i,k}(A^{2})_{ik}=\sum_{i,j,k}A_{ij}A_{jk}=\sum_{j}d_{j}^{2}.$

This proves the equality. For the inequality, Cauchy-Schwarz implies that
$\sum_{i}d_{i}^{2}\geq\frac{1}{n}(\sum_{i}d_{i})^{2}=\frac{4m^{2}}{n}=2mp(n-1)$.
After applying this inequality and rewriting $3p^{3}n(n-1)$ as $6p^{2}m$, we
obtain the inequality. ∎

Combining Lemma 3 with the observation that
$\mathbb{E}\operatorname{tr}[A^{3}]=p^{3}n^{3}+O(n^{2})$ when $A$ is the
adjacency matrix of a $\mathcal{G}(n,m)$ graph, we arrive at the following
consequence:

######  Corollary 4.

Let $A$ be the adjacency matrix of a $\mathcal{G}(n,m)$ graph and let
$\tilde{A}=A-\mathbb{E}A$. For any $t\geq 0$,

(17)
$\Pr(\operatorname{tr}[A^{3}]\leq\mathbb{E}\operatorname{tr}[A^{3}]-t)\leq\Pr(\operatorname{tr}[\tilde{A}^{3}]\leq-t+O(n^{2}))$

For an inequality in the other direction, note that by the same argument as in
Lemma 3, as long as $\sum_{i}d_{i}^{2}\leq n^{3}p^{2}+D$, we have

(18)
$\operatorname{tr}[(A-p\mathbf{1}+pI)^{3}]=\operatorname{tr}[A^{3}]-p^{3}n^{3}+O(D+n^{2}).$

######  Corollary 5.

With the notation of Corollary 4, if $D=\Omega(n^{2})$ then

(19)
$\Pr\left(\operatorname{tr}[A^{3}]\leq\mathbb{E}\operatorname{tr}[A^{3}]-t\right)\geq\Pr\left(\operatorname{tr}[\tilde{A}^{3}]\leq-t-\Omega(D)\text{
and }\sum_{i}d_{i}^{2}\leq n^{3}p^{2}+D\right).$

##  4\. Large deviations for eigenvalues of random matrices

In this section and beyond, we let $A$ denote a generic random matrix and we
estimate the most positive eigenvalues of $A$. Since we are looking at lower
tails, the most important such matrix to keep in mind is minus the centered
adjacency matrix, previously denoted $\tilde{A}$ or $A-\mathbb{E}A$. This is
the same as plus the centered adjacency matrix of a random graph with edge
density $q=1-p$. The proof of Theorem 1 ($p\geq\frac{1}{2}$) thus relies on
results for $q\leq\frac{1}{2}$, while the proof of Theorem 2
($p\leq\frac{1}{2}$) relies on results for $q\geq\frac{1}{2}$.

######  Definition 6.

For a random variable $\xi$, its cumulant-generating function is

(20) $\Lambda_{\xi}(s)=\ln\mathbb{E}\exp(s\xi)$

whenever the expectation exists; when the expectation does not exist, we set
$\Lambda_{\xi}(s)=+\infty$.

######  Definition 7.

The random variable $\xi$ is _subgaussian_ if there exists a constant $C$ such
that $\Lambda_{\xi}(t)\leq Ct^{2}$ for every $t\in\mathbb{R}$.

Note that according to our definition, a subgaussian random variable has mean
zero (since if $\Lambda_{\xi}(t)$ is finite on a neighborhood of 0 then
$\Lambda_{\xi}(0)=0$ and $\Lambda_{\xi}^{\prime}(0)=\mathbb{E}\xi$, and so if
$\mathbb{E}\xi$ is non-zero then one cannot have $\Lambda_{\xi}(t)\leq Ct^{2}$
on a neighborhood of 0). Note also that if $\mathbb{E}\xi=0$ and
$\|\xi\|_{\infty}<\infty$ then $\xi$ is subgaussian.

######  Definition 8.

For a function $f:\mathbb{R}\to\mathbb{R}$, its Legendre transform is the
function $f^{*}:\mathbb{R}\to\mathbb{R}\cup\\{+\infty\\}$ defined by

(21) $f^{*}(y)=\sup_{x\in\mathbb{R}}\\{xy-f(x)\\}$

Some basic properties of the Legendre transform include:

  * •

If $f\leq g$ then $f^{*}\geq g^{*}$.

  * •

If $f$ is convex then $f^{**}=f$.

  * •

If $f(x)=cx^{2}$ then $f^{*}(x)=\frac{x^{2}}{4c}$.

Our goal in this note is to establish large deviations principles for extreme
eigenvalues and singular values of random matrices. We will consider a
symmetric $n\times n$ random matrix $A_{n}$ (or sometimes just $A$) having
i.i.d. upper-diagonal entries and zero diagonal entries. The letter $\xi$ will
always denote a random variable that is distributed as an upper-diagonal
element of $A$, and we will always assume that $\xi$ is subgaussian. We write
$\lambda_{i}(A)$ for the eigenvalues of $A$ (in non-increasing order) and
$\sigma_{i}(A)$ for the singular values of $A$ (in non-increasing order).

For the definition of a large deviations principle (LDP), we refer to [36,
Chapter 27].

######  Theorem 9.

Let $\xi$ be a subgaussian random variable. For any integer $k\geq 1$ and any
sequence $m_{n}$ satisfying $\sqrt{n}\ll m_{n}\ll n$, the sequence

(22) $\frac{1}{m_{n}}(\sigma_{1}(A_{n}),\dots,\sigma_{k}(A_{n}))$

satisfies an LDP with speed $m_{n}^{2}$ and good rate function
$I:\mathbb{R}_{+}^{k}\to[0,\infty)$ given by

(23)
$I(x)=\frac{|x|^{2}}{2}\inf_{s\in\mathbb{R}}\frac{\Lambda^{*}(s)}{s^{2}}.$

If we assume in addition that the function
$s\mapsto\frac{\Lambda^{*}(s)}{s^{2}}$ achieves its infimum at some $s\geq 0$,
then the sequence

(24) $\frac{1}{m_{n}}(\lambda_{1}(A_{n}),\dots,\lambda_{k}(A_{n}))$

satisfies an LDP with speed $m_{n}^{2}$ and the same good rate function $I$ as
above.

If $A_{n}$ is the centered adjacency matrix of $\mathcal{G}(n,q)$ then it is
covered by Theorem 9, where $\xi$ is the random variable taking the values
$-q$ and $1-q$ with probabilities $1-q$ and $q$ respectively. In this case, we
have

(25)
$\Lambda_{\xi}^{*}(s)=D(q+s,q):=(q+s)\ln\frac{q+s}{q}+(1-q-s)\ln\frac{1-q-s}{1-q},$

with the understanding that $\Lambda_{\xi}^{*}(s)=+\infty$ whenever
$q+s\not\in(0,1)$. It is not hard to check – and we will do it in Section 5.5
– that $\frac{\Lambda_{\xi}^{*}(s)}{s^{2}}$ achieves its infimum at some
$s\geq 0$ if and only if $q\leq\frac{1}{2}$.

In the case that $\frac{\Lambda^{*}(s)}{s^{2}}$ saturates its infimum only at
negative $s$ (corresponding to $q>\frac{1}{2}$ in the Bernoulli example), we
are not able to show an LDP for the eigenvalues. Note, however, that
$\sum_{i}\sigma_{i}^{2}(A)\geq\sum_{i}\lambda_{i}^{2}(A)$ and so our LDP for
singular values provides an upper bound: it implies, for example, that

(26)
$\frac{1}{m_{n}^{2}}\ln\Pr\left(\sqrt{\sum_{i}\lambda_{i}^{2}(A_{n})}>m_{n}t\right)\leq-\frac{t^{2}}{2}\inf_{s\in\mathbb{R}}\frac{\Lambda^{*}(s)}{s^{2}}+o(1)$

On the other hand, we can also easily show the lower bound

(27)
$\frac{1}{m_{n}^{2}}\ln\Pr\left(\sqrt{\sum_{i}\lambda_{i}^{2}(A_{n})}>m_{n}t\right)\geq-\frac{t^{2}}{2}\inf_{s\geq
0}\frac{\Lambda^{*}(s)}{s^{2}}-o(1),$

but the assumption that $\frac{\Lambda^{*}(s)}{s^{2}}$ saturates its infimum
only at negative $s$ implies that these bounds are non-matching.

There are natural examples (including the Bernoulli example mentioned above)
where $s^{-2}\Lambda^{*}(s)$ is increasing for $s\geq 0$. In this case,

(28) $\inf_{s\geq 0}s^{-2}\Lambda^{*}(s)=\lim_{s\to
0}s^{-2}\Lambda^{*}(s)=\frac{1}{2}(\Lambda^{*})^{\prime\prime}(0)=\frac{1}{2\mathbb{E}\xi^{2}},$

and so our lower bound (for simplicity, focusing only on the case $k=1$)
becomes

(29)
$\frac{1}{m_{n}^{2}}\ln\Pr\left(\lambda_{1}(A_{n})>m_{n}t\right)\geq-\frac{t^{2}}{4\mathbb{E}\xi^{2}}-o(1).$

When $\xi$ has a Gaussian distribution, this turns out to be sharp, but we
show that it is not sharp in general.

######  Theorem 10.

In the setting of Theorem 9, if $\mathbb{E}\xi^{3}<0$ and
$\lim_{s\to\infty}s^{-2}\Lambda(s)=0$ then there exists some $\eta>0$ such
that for any $t>0$,

(30)
$\lim_{n\to\infty}\frac{1}{m_{n}^{2}}\ln\Pr\left(\lambda_{1}(A_{n})>m_{n}t\right)>-(1-\eta)\frac{t^{2}}{4\mathbb{E}\xi^{2}}.$

In particular, the assumptions of Theorem 10 are satisfied for the (centered)
Bernoulli random variable with $q>\frac{1}{2}$ mentioned above.

For our applications to random graphs, we require a version of Theorem 9 for
random bits chosen without replacement. Specifically, we consider the Erdős-
Rényi random graphs $\mathcal{G}(n,m)$, where $m$ is an integer satisfying
$|m-q\binom{n}{2}|=O(1)$ (and $q\in(0,1)$ is fixed).

######  Theorem 11.

Fix $q\in(0,1)$ and let $A_{n}$ be the centered adjacency matrix of a
$\mathcal{G}(n,m)$ random graph with $|m-q\binom{n}{2}|=O(1)$. For any integer
$k\geq 1$ and any sequence $m_{n}$ satisfying $\sqrt{n}\ll m_{n}\ll n$, the
sequence

(31) $\frac{1}{m_{n}}(\sigma_{1}(A_{n}),\dots,\sigma_{k}(A_{n}))$

satisfies an LDP with speed $m_{n}^{2}$ and good rate function
$I:\mathbb{R}_{+}^{k}\to[0,\infty)$ given by
$I(x)=\frac{|x|^{2}}{2}\cdot\frac{\ln\frac{1-q}{q}}{1-2q}$ (or $I(x)=|x|^{2}$
when $q=\frac{1}{2}$).

If, in addition, $q\leq\frac{1}{2}$ then the sequence

(32) $\frac{1}{m_{n}}(\lambda_{1}(A_{n}),\dots,\lambda_{k}(A_{n}))$

also satisfies an LDP with the same speed and rate function.

##  5\. Upper bound

Most of this work is concerned with handling the triangle-count contribution
of very negative eigenvalues, but we also need to show that there is no
significant contribution from the rest. For this, we will use a deviation
inequality from [33]:

######  Theorem 12.

Assume that $\|\xi\|_{\infty}<\infty$, and let $f:\mathbb{R}\to\mathbb{R}$ be
a 1-Lipschitz, convex function. Define
$X_{n}=\frac{1}{n}\sum_{i=1}^{n}f(n^{-1/2}\lambda_{i}(A_{n}))$. Then there is
a universal constant $C<\infty$ such that for any $\delta\gg n^{-1}$,

(33) $\Pr(|X_{n}-\mathbb{E}X_{n}|\geq\delta)\leq
C\exp\left(-\frac{n^{2}\delta^{2}}{C\|\xi\|_{\infty}^{2}}\right).$

The main observation is that in the regime we are interested in (namely,
eigenvalues or singular values of order $\omega(\sqrt{n})$), the probability
of large eigenvalues can be controlled by a union bound over the potential
eigenvectors.

Let $\mathcal{M}_{k}$ be the set of $n\times n$ matrices with rank at most $k$
and Frobenius norm at most 1. Let $\mathcal{M}_{k}^{+}\subset\mathcal{M}_{k}$
consist of those matrices that are symmetric and positive semidefinite.

######  Lemma 13.

For any symmetric matrix $A$,

(34)
$\left(\sum_{i=1}^{k}\max\\{0,\lambda_{i}(A)\\}^{2}\right)^{1/2}=\sup_{M\in\mathcal{M}_{k}^{+}}\langle
A,M\rangle.$

For any matrix $A$,

(35)
$\left(\sum_{i=1}^{k}\sigma_{i}(A)^{2}\right)^{1/2}=\sup_{M\in\mathcal{M}_{k}}\langle
A,M\rangle.$

###### Proof.

Let $UDU^{T}=A$ be an eigen-decomposition of $A$ (where $D$ is diagonal and
$U$ is orthogonal), and let $\tilde{D}$ be $D$ but with all but the $k$th-
largest diagonal entries set to zero. Define

(36)
$M=\frac{U\tilde{D}U^{T}}{\|\tilde{D}\|_{F}}=\frac{U\tilde{D}U^{T}}{\left(\sum_{i=1}^{k}\lambda_{i}(A)^{2}\right)^{1/2}}.$

Then $M\in\mathcal{M}_{k}^{+}$ and $\langle
A,M\rangle=\|\tilde{D}\|_{F}=\left(\sum_{i=1}^{k}\lambda_{i}(A)^{2}\right)^{1/2}$.
This proves one direction of the first claim.

For the other direction, take any $M\in\mathcal{M}_{k}^{+}$, and decompose $A$
as $A_{+}-A_{-}$, where $A_{+}$ and $A_{-}$ are positive semi-definite and the
non-zero eigenvalues of $A_{+}$ are the positive eigenvalues of $A$. Then

(37) $\langle A,M\rangle\leq\langle
A_{+},M\rangle\leq\|A_{+}\|_{F}\|M\|_{F}\leq\sqrt{\sum_{i=1}^{k}\lambda_{i}(A_{+})^{2}}=\sqrt{\sum_{i=1}^{k}\lambda_{i}(A)^{2}}.$

This proves the first claim. The proof of the second claim is identical, but
uses a singular value decomposition instead of an eigen-decomposition. ∎

Hence, in order to prove the upper bounds in Theorem 9, it suffices to control

(38) $\Pr\left(\sup_{M\in\mathcal{M}_{k}^{+}}\langle
A,M\rangle>tn^{\alpha}\right).$

The first step is to replace the supremum with a finite maximum.

###  5.1. The net argument

######  Definition 14.

For a subset $\mathcal{N}$ of a metric space $(X,d)$, we say that
$\mathcal{N}$ is an $\epsilon$-net of $X$ if for every $x\in X$ there exists
$y\in\mathcal{N}$ with $d(x,y)\leq\epsilon$.

######  Lemma 15.

Let $\mathcal{N}\subset\mathcal{M}_{k}$ be an $\epsilon$-net (with respect to
$\|\cdot\|_{F}$) for $\epsilon<\frac{1}{2}$. Then for any symmetric matrix
$A$,

(39) $\sup_{M\in\mathcal{M}_{k}}\langle
A,M\rangle\leq\frac{1}{1-2\epsilon}\sup_{N\in\mathcal{N}}\langle A,N\rangle.$

###### Proof.

Fix $M\in\mathcal{M}_{k}$, and choose $N\in\mathcal{N}$ with
$\|N-M\|_{F}\leq\epsilon$. Note that $N-M$ has rank at most $2k$, and it has
at most $k$ positive eigenvalues and $k$ negative eigenvalues. Letting
$\epsilon M_{0}$ and $\epsilon M_{1}$ be the positive and negative parts of
$N-M$, we have $\|M_{0}\|_{F}\leq\|N-M\|_{F}/\epsilon\leq 1$ and (similarly
$\|M_{1}\|_{F}\leq 1$). In other words, we can decompose

(40) $M=N+\epsilon M_{0}+\epsilon M_{1}$

with $N\in\mathcal{N}$ and $M_{0},M_{1}\in\mathcal{M}_{k}$. We continue this
construction recursively: for every finite binary string $v$ and matrix
$M_{v}\in\mathcal{M}_{k}$, we can find $N_{v}\in\mathcal{N}$ and
$M_{v0},M_{v1}\in\mathcal{M}_{k}$ such that

(41) $M_{v}=N_{v}+\epsilon M_{v0}+\epsilon M_{v1}.$

Recursing this construction $m$ levels, it follows that (with $S_{m}$ being
the set of binary strings of length $m$ and $|v|$ denoting the length of the
string $v$)

(42) $M=\sum_{\ell=0}^{m-1}\sum_{v\in
S_{\ell}}\epsilon^{-|v|}N_{v}+\epsilon^{-m}\sum_{v\in S_{m}}M_{v}.$

Since $|S_{m}|=2^{m}$ and each $M_{v}$ has $\|M_{v}\|_{F}\leq 1$, the
remainder term converges to zero and we can continue this construction to the
limit:

(43) $M=\sum_{\ell=0}^{\infty}\sum_{v\in S_{\ell}}\epsilon^{-|v|}N_{v},$

where the outer sum converges in Frobenius norm.

Taking the inner product with $A$, note that Cauchy-Schwarz and the
convergence of the sum imply that the inner product and summation can be
exchanged:

(44) $\langle M,A\rangle=\sum_{\ell=0}^{\infty}\sum_{v\in
S_{\ell}}\epsilon^{-|v|}\langle
N_{v},A\rangle\leq\sum_{\ell=0}^{\infty}|S_{\ell}|\epsilon^{-\ell}\sup_{N\in\mathcal{N}}\langle
N,A\rangle=\frac{1}{1-2\epsilon}\sup_{N\in\mathcal{N}}\langle N,A\rangle.$

∎

The construction in Lemma 15 approximates the supremum over
$M\in\mathcal{M}_{k}$, which is enough for most of what we will do. In some
cases, we will want the supremum over $M\in\mathcal{M}_{k}^{+}$ instead, but
that can be handled also:

######  Lemma 16.

Let $\mathcal{N}\subset\mathcal{M}_{k}$ and
$\mathcal{N}^{+}\subset\mathcal{M}_{k}^{+}$ be $\epsilon$-nets (with respect
to $\|\cdot\|_{F}$) for $\epsilon<\frac{1}{2}$ Then for any symmetric matrix
$A$,

(45) $\sup_{M\in\mathcal{M}_{k}^{+}}\langle
A,M\rangle\leq\sup_{N^{+}\in\mathcal{N}^{+}}\langle
A,N^{+}\rangle+\frac{2\epsilon}{1-2\epsilon}\sup_{N\in\mathcal{N}}\langle
A,N\rangle.$

###### Proof.

Fix $M\in\mathcal{M}_{k}^{+}$ and choose $M_{0}\in\mathcal{N}^{+}$ such that
$\|M_{0}-M\|_{F}\leq\epsilon$. Then $\frac{M_{0}-M}{\epsilon}$ has rank at
most $2k$ and Frobenius norm at most $1$. Hence, we can write
$M_{0}-M=\epsilon N_{0}+\epsilon N_{1}$, where
$N_{0},N_{1}\in\mathcal{M}_{k}$. It follows that

(46) $\langle A,M\rangle=\langle A,M_{0}\rangle+\epsilon\langle
A,N_{0}\rangle+\epsilon\langle A,N_{1}\rangle,$

and we conclude by applying Lemma 15 to $\langle A,N_{0}\rangle$ and $\langle
A,N_{1}\rangle$. ∎

We have shown that to approximate the supremum it suffices to take a good
enough net. In order to put this together with a union bound, we need a bound
on the size of a good net. Our starting point is the following basic bound in
Euclidean space [35, Corollary 4.2.13]

######  Lemma 17.

The unit Euclidean ball in $\mathbb{R}^{d}$ admits an $\epsilon$-net (with
respect to the Euclidean metric) $\mathcal{N}$ satisfying
$|\mathcal{N}|\leq(3/\epsilon)^{d}$.

######  Corollary 18.

There is a constant $C$ such that for any $0<\epsilon<1$, there is an
$\epsilon$-net (with respect to Frobenius norm) for $\mathcal{M}_{k}$ of size
at most $(C/\epsilon)^{2nk}$ and an $\epsilon$-net for $\mathcal{M}_{k}^{+}$
of size at most $(C/\epsilon)^{k}$.

###### Proof.

Let $\tilde{\mathcal{N}}$ be an $(\epsilon/2)$-net for the set of $n\times k$
matrices with Frobenius norm at most one. Since this space is isometric to
$\mathbb{R}^{nk}$ with the Euclidean norm, Lemma 17 implies that we can choose
such a $\tilde{\mathcal{N}}$ with
$|\tilde{\mathcal{N}}|\leq(C/\epsilon)^{nk}$. Now let
$\mathcal{N}=\\{XY^{T}:X,Y\in\tilde{\mathcal{N}}\\}$. Then
$|\mathcal{N}|\leq|\tilde{\mathcal{N}}|^{2}\leq(C/\epsilon)^{2nk}$.

It remains to show that $\mathcal{N}$ is an $\epsilon$-net. Since
$\|XY^{T}\|_{F}\leq\|X\|_{F}\|Y\|_{F}$, it follows that every
$N\in\mathcal{N}$ has $\|N\|_{F}\leq 1$; also, each $N\in\mathcal{N}$ clearly
has rank at most $k$. Now choose an arbitrary $M\in\mathcal{M}_{k}$ and write
$M=AB^{T}$ for $n\times k$ matrices $A$ and $B$ of Frobenius norm at most 1
(for example, this can be done using a singular value decomposition). Choose
$X,Y\in\tilde{\mathcal{N}}$ with $\|X-A\|_{F}\leq\frac{\epsilon}{2}$ and
$\|Y-B\|_{F}\leq\frac{\epsilon}{2}$. Then

$\displaystyle\|XY^{T}-M\|_{F}$
$\displaystyle\leq\|XY^{T}-AY^{T}\|_{F}+\|AY^{T}-AB^{T}\|_{F}$
$\displaystyle\leq\|X-A\|_{F}+\|Y^{T}-B^{T}\|_{F}$
$\displaystyle\leq\epsilon.$

To construct an $\epsilon$-net of $\mathcal{M}_{k}^{+}$, take
$\tilde{\mathcal{N}}$ be as above and let
$\mathcal{N}=\\{XX^{T}:X\in\tilde{\mathcal{N}}\\}$. Then
$|\mathcal{N}|\leq|\tilde{\mathcal{N}}|$, and the proof that $\mathcal{N}$ is
an $\epsilon$-net of $\mathcal{M}_{k}^{+}$ is essentially the same as the
proof above, the only change being that every $M\in\mathcal{M}_{k}^{+}$ can be
written as $M=AA^{T}$ for an $n\times k$ matrix $A$ of Frobenius norm at most
1. ∎

Applying a union bound over these nets gives the main result of this section:
singular values and eigenvalues of $A$ can be controlled in terms of the
deviations of linear functions of $A$. The main point here is that (as we will
show in the next section) if $t\gg\sqrt{n}$ then the
$O(nk\ln\frac{1}{\epsilon})$ terms are negligible compared to the other terms.

######  Proposition 19.

Let $A$ be a symmetric $n\times n$ random matrix with i.i.d. entries. For any
integer $k\geq 1$, any $0<\epsilon<\frac{1}{2}$, and any $t>0$,

(47)
$\ln\Pr\left(\sum_{i=1}^{k}\sigma_{i}^{2}(A)>t\right)\leq\sup_{M\in\mathcal{M}_{k}}\ln\Pr\left(\langle
A,M\rangle\geq(1-2\epsilon)t\right)+O(nk\ln\frac{1}{\epsilon}).$

###### Proof.

For the first inequality, let $\mathcal{N}$ be an $\epsilon$-net for
$\mathcal{M}_{k}$ according to Corollary 18. By Lemma 13 and Lemma 15

$\displaystyle\Pr\left(\sum_{i=1}^{k}\sigma_{i}^{2}(A)>t\right)$
$\displaystyle=\Pr\left(\sup_{M\in\mathcal{M}_{k}}\langle A,M\rangle>t\right)$
$\displaystyle\leq\Pr\left(\max_{N\in\mathcal{N}}\langle
A,N\rangle>(1-2\epsilon)t\right).$

By a union bound,

$\displaystyle\Pr\left(\max_{N\in\mathcal{N}}\langle
A,N\rangle>(1-2\epsilon)t\right)$
$\displaystyle\leq\sum_{N\in\mathcal{N}}\Pr\left(\langle
A,N\rangle>(1-2\epsilon)t\right)$
$\displaystyle\leq|\mathcal{N}|\sup_{M\in\mathcal{M}_{k}}\Pr\left(\langle
A,M\rangle>(1-2\epsilon)t\right),$

which, by our bound on $|\mathcal{N}|$, completes the proof of the first
claim. ∎

We remark that it is possible to prove a version of Proposition 19 for
eigenvalues also, giving an upper bound on $\Pr(\sum\lambda_{i}^{2}(A)>t)$ in
terms of

(48) $\sup_{M^{+}\in\mathcal{M}_{k}^{+}}\Pr\left(\langle A,M^{+}\rangle\geq
t\right).$

This can in principle give a better bound on the eigenvalues than for the
singular values. The issue is that we do not know how to exploit the
additional information that we are testing $A$ against a positive semidefinite
matrix.

###  5.2. Hoeffding-type argument

Using a Hoeffding-type argument, we can get a sharp upper bound on

(49) $\sup_{M\in\mathcal{M}_{k}}\ln\Pr\left(\langle A,M\rangle\geq t\right)$

for any $k$ and any $t$ (in fact, the sharp upper bound turns out not to
depend on $k$).

######  Lemma 20.

If $\xi$ is subgaussian then

(50)
$4\sup_{s\in\mathbb{R}}\frac{\Lambda_{\xi}(s)}{s^{2}}=\left(\inf_{s\in\mathbb{R}}\frac{\Lambda_{\xi}^{*}(u)}{u^{2}}\right)^{-1}<\infty.$

###### Proof.

The fact that $\sup_{s\in\mathbb{R}}\frac{\Lambda(s)}{s^{2}}<\infty$ is the
definition of subgaussianity. To show the claimed identity, let
$L=\sup_{t\in\mathbb{R}}\frac{\Lambda_{\xi}(t)}{t^{2}}$ and define
$M_{L}(s)=Ls^{2}$. Clearly, $\Lambda(s)\leq M_{L}(s)$ for all
$s\in\mathbb{R}$. It follows that $\Lambda^{*}(u)\geq
M_{L}^{*}(u)=\frac{u^{2}}{4L}$; in other words,

(51) $\frac{\Lambda^{*}(u)}{u^{2}}\geq\frac{M_{L}^{*}(u)}{u^{2}}=\frac{1}{4L}$

for all $u$. This shows that

(52)
$4\sup_{s\in\mathbb{R}}\frac{\Lambda(s)}{s^{2}}\geq\left(\inf_{u\in\mathbb{R}}\frac{\Lambda^{*}(u)}{u^{2}}\right)^{-1}.$

For the other direction, suppose that for some $L^{\prime}$ we have
$\Lambda^{*}(u)\geq\frac{u^{2}}{4L^{\prime}}=M^{1/(4L)^{\prime}}(u)$ for every
$u$. Then (since $\Lambda$ is convex) $\Lambda(t)=\Lambda^{**}(t)\leq
M_{1/(4L^{\prime})}^{*}(t)=L^{\prime}t^{2}$ for every $t$. The definition of
$L$ ensures that $L^{\prime}\geq L$, and this shows the other direction of the
claim. ∎

######  Proposition 21.

Let $\xi$ be a random variable with globally-finite moment-generating
function, and define

(53) $\Lambda(s)=\ln\mathbb{E}\exp(s\xi)$

to be the cumulant-generating function of $\xi$. Let $A$ be a symmetric random
matrix with zero diagonal, and with upper-diagonal elements distributed
independently according to $\xi$. Define
$\ell^{*}=\sup_{s>0}\frac{\Lambda(s)}{s^{2}}$. Then

(54) $\sup_{\|M\|_{F}\leq 1}\Pr(\langle
A,M\rangle>t)\leq\exp\left(-\frac{t^{2}}{8\sup_{s>0}\frac{\Lambda(s)}{s^{2}}}\right)=\exp\left(-\frac{t^{2}}{2}\inf_{s>0}\frac{\Lambda^{*}(s)}{s^{2}}\right).$

###### Proof.

Since $\langle A,M\rangle=\langle A,(M+M^{T})/2\rangle$ and since
$\|(M+M^{T})/2\|_{F}\leq\|M\|_{F}$, it suffices to consider only symmetric
matrices $M$. Let $m=\frac{n}{n-1}{2}$ and let $\xi_{1},\dots,\xi_{m}$ be the
upper-diagonal elements of $A$, in any order. Let $\|M\|\leq 1$ be symmetric,
with upper-diagonal entries $a_{1},\dots,a_{m}$. Then $\langle
A,M\rangle=2\sum_{i=1}^{m}a_{i}\xi_{i}$, and so (for any $s>0$)

$\displaystyle\Pr(\langle A,M\rangle>t)$ $\displaystyle=\Pr\left(\sum
a_{i}\xi_{i}>t/2\right)$ $\displaystyle=\Pr\left(e^{s\sum
a_{i}\xi_{i}}>e^{st/2}\right)$ $\displaystyle\leq e^{-st/2}\mathbb{E}e^{s\sum
a_{i}\xi_{i}}$ $\displaystyle=\exp\left(\sum_{i}\Lambda(sa_{i})-st/2\right),$

where the inequality follows from Markov’s inequality. Now,
$\sum_{i=1}^{m}a_{i}^{2}\leq\frac{1}{2}\|M\|_{F}^{2}\leq\frac{1}{2}$, and so
if we set $\ell^{*}=\sup_{r>0}\frac{\Lambda(r)}{r^{2}}$ then

(55)
$\sum_{i}\Lambda(sa_{i})=\sum_{i}\frac{\Lambda(sa_{i})}{(sa_{i})^{2}}(sa_{i})^{2}\leq
s^{2}\sum_{i}\ell^{*}a_{i}^{2}\leq\frac{s^{2}\ell^{*}}{2}.$

Hence,

(56) $\Pr(\langle
A,M\rangle>t)\leq\exp\left(\frac{s^{2}\ell^{*}}{2}-\frac{st}{2}\right),$

and the first claim follows by optimizing over $s$.

The second claim follows immediately from Lemma 20. ∎

Putting Proposition 21 together with Proposition 19, we arrive at the
following upper bound for singular values:

######  Corollary 22.

Let $A$ be a symmetric $n\times n$ random matrix with i.i.d. upper diagonal
entries. Assuming that the entries are subgaussian and have cumulant-
generating function $\Lambda$, let
$L=\inf_{s\in\mathbb{R}}\frac{\Lambda^{*}(s)}{s^{2}}$. Then for any integer
$k$ and any $t>0$, if $t^{2}L>2nk$ then

(57)
$\ln\Pr\left(\sqrt{\sum_{i=1}^{k}\sigma_{i}^{2}(A)}>t\right)\leq-\frac{t^{2}L}{2}+O\left(nk\ln\frac{t^{2}L}{nk}\right).$

###### Proof.

We combine Proposition 21 and Proposition 19, setting
$\epsilon=\frac{nk}{t^{2}L}$ (which is less than $\frac{1}{2}$ by assumption).
This yields an upper bound of

(58) $-\frac{t^{2}L}{2}+O\left(nk+nk\ln\frac{t^{2}L}{nk}\right),$

and the $nk$ term can be absorbed in the final term. ∎

######  Remark 23.

Note that the argument leading to Corollary 22 applies even when the entries
$\xi_{ij}$ are not identically distributed as long as
$L\leq\inf_{s}\frac{\Lambda_{ij}^{*}(s)}{s^{2}}$ for every $i$, where
$\Lambda_{ij}$ is the cumulant-generating function of $\xi_{ij}$.

###  5.3. Lower bound

In this section, we give a lower bound that matches the upper bound of
Corollary 22 whenever $\sqrt{n}\ll t\ll n$. The starting point is the lower
bound of Cramér’s theorem [36, Theorem 27.3]

######  Theorem 24.

Let $\xi$ be a mean-zero random variable with everywhere-finite cumulant-
generating function $\Lambda_{\xi}$. Let $\xi_{1},\dots,\xi_{m}$ be
independent copies of $\xi$. Then

(59)
$\frac{1}{m}\ln\Pr\left(\sum_{i=1}^{m}\xi_{i}>mt\right)\to-\Lambda^{*}(t)$

as $m\to\infty$.

######  Proposition 25.

In the setting of Corollary 22, suppose in addition that the function
$s\mapsto s^{-2}\Lambda^{*}(s)$ achieves its minimum at some finite
$s\in\mathbb{R}$. Then for any $1\ll t\ll n^{2}$ and for any
$w_{1},\dots,w_{k}>0$, we have

(60)
$\ln\Pr\left(\sum_{i=1}^{k}w_{i}\sigma_{i}(A_{n})>|w|\sqrt{t}\right)\geq-\frac{tL}{2}-o(t).$

If $s\mapsto s^{-2}\Lambda^{*}(s)$ achieves its minimum at some $s\geq 0$,
then for any $1\ll t\ll n^{2}$ and for any $w_{1},\dots,w_{k}>0$, we have

(61)
$\ln\Pr\left(\sum_{i=1}^{k}w_{i}\lambda_{i}(A_{n})>|w|\sqrt{t}\right)\geq-\frac{tL}{2}-o(t).$

Choosing an arbitrary $w_{1},\dots,w_{k}$ and applying the Cauchy-Schwarz
inequality, Proposition 25 implies the same lower bounds on
$\ln\Pr(\sum_{i}\sigma_{i}^{2}(A_{n})>t)$ and
$\ln\Pr(\sum_{i}\lambda_{i}^{2}(A_{n})>t)$. In particular, it really is a
lower bound that matches the upper bound of Corollary 22.

###### Proof.

Fix $t$ and assume that $\frac{\Lambda^{*}(s)}{s^{2}}$ achieves its minimum at
$s_{*}\in\mathbb{R}$. Actually, we will assume $s_{*}\neq 0$; the case
$s_{*}=0$ is easily handled by replacing $s_{*}$ with $\epsilon>0$ everywhere,
and then sending $\epsilon\to 0$. Fix $w_{1},\dots,w_{k}$ and assume
$\sum_{i}w_{i}^{2}=t$; because the statement of the proposition is homogeneous
in $w$, this is without loss of generality. Now choose the smallest integers
$\ell_{1},\dots,\ell_{k}$ so that $\ell_{i}-1\geq\frac{w_{i}}{s_{*}}$. We
write $|\ell|^{2}$ for $\sum_{i}\ell_{i}^{2}$, and note that
$|\ell|^{2}\geq\frac{1}{s_{*}^{2}}\sum_{i}w_{i}^{2}=\frac{t}{s_{*}^{2}}$,
meaning that $1\ll|\ell|^{2}\ll n^{2}$.

Let $M$ be a block-diagonal matrix, whose non-zero entries are all equal to
$s_{*}$, appearing in blocks of size $\ell_{i}\times\ell_{i}$ for
$i=1,\dots,k$. (The fact that $\sum_{i}\ell_{i}\leq\sqrt{k}|\ell|\ll n$
implies that these blocks do indeed fit into an $n\times n$ matrix.) Then $M$
has rank $k$, and the singular values of $M$ are $s_{*}\ell_{i}$ for
$i=1,\dots,k$; note that our choices of $\ell_{i}$ ensure that
$w_{i}\leq\sigma_{i}(M)\leq w_{i}+2s_{*}$. Moreover, if we set
$m=\sum_{i}\frac{\ell_{i}(\ell_{i}-1)}{2}$ (which is also an integer, and
counts the number of non-zero upper-diagonal elements of $M$) then $\langle
A,M\rangle$ is equal in distribution to $2s_{*}\sum_{i=1}^{m}\xi_{i}$. Hence,

(62) $\Pr\left(\langle
A,M\rangle>t\right)=\Pr\left(\operatorname{sgn}(s_{*})\sum_{i=1}^{m}\xi_{i}>\frac{t}{2|s_{*}|}\right).$

Now, $m=\frac{1}{2}|\ell|^{2}-\frac{1}{2}\sum_{i}\ell_{i}$, while on the other
hand

(63)
$\frac{t}{s_{*}^{2}}=\frac{\sum_{i}w_{i}^{2}}{s_{*}^{2}}\leq\sum_{i}(\ell_{i}-1)^{2}=|\ell|^{2}-2\sum_{i}\ell_{i}+2k.$

Since $\sum_{i}\ell_{i}\geq|\ell|\gg 1$, we have $\frac{t}{2s_{*}^{2}}\leq m$
for sufficiently large $n$. Going back to our probability estimates, we have

$\displaystyle\ln\Pr\left(\langle A,M\rangle>t\right)$
$\displaystyle=\ln\Pr\left(\operatorname{sgn}(s_{*})\sum_{i=1}^{m}\xi_{i}>\frac{t}{2|s_{*}|}\right)$
$\displaystyle\geq\ln\Pr\left(\operatorname{sgn}(s_{*})\sum_{i=1}^{m}\xi_{i}>m|s_{*}|\right)$
$\displaystyle=-m\Lambda^{*}(s_{*})+o(m)$
$\displaystyle=-\frac{t\Lambda^{*}(s_{*})}{2s_{*}^{2}}-o(t),$

where the second-last equality follows by Cramér’s theorem (applied to the
random variables $-\xi_{i}$ in case $s_{*}<0$). By the Cauchy-Schwarz
inequality we have

(64) $\langle
A,M\rangle\leq\sum_{i=1}^{k}\sigma_{i}(A)\sigma_{i}(M)\leq\sum_{i=1}^{k}\sigma_{i}(A)(w_{i}+2s_{*})\\\
\leq\sum_{i=1}^{k}\sigma_{i}(A)w_{i}+2s_{*}\sqrt{k}\sqrt{\sum_{i=1}^{k}\sigma_{i}^{2}(A)},$

and hence

(65) $\Pr\left(\langle
A,M\rangle>t\right)\leq\Pr\left(\sum_{i=1}^{k}\sigma_{i}(A)w_{i}>t-t^{2/3}\right)+\Pr\left(\sum_{i=1}^{k}\sigma_{i}^{2}(A)>\frac{t^{4/3}}{4s_{*}^{2}k}\right).$

By Corollary 22, the second probability is of order $\exp(-\Omega(t^{4/3}))$,
and hence

(66)
$\ln\Pr\left(\sum_{i=1}^{k}\sigma_{i}(A)w_{i}>t-t^{2/3}\right)\geq(1-o(1))\ln\Pr\left(\langle
A,M\rangle>t\right)\geq-\frac{t\Lambda^{*}(s_{*})}{2s_{*}^{2}}-o(t).$

Substituting in $t=|w|\sqrt{t}$ in place of $t-t^{2/3}$, the extra error term
can be absorbed in the $o(t)$ term.

For the second claim, simply note that if $s_{*}>0$ then the matrix $M$ is
positive semi-definite. Denoting
$\lambda_{i}^{+}(A)=\max\\{0,\lambda_{i}(A)\\}$, we replace (64) by

(67) $\langle
A,M\rangle\leq\sum_{i=1}^{k}\lambda_{i}^{+}(A)\lambda_{i}(M)\leq\sum_{i=1}^{k}\lambda_{i}^{+}(A)(w_{i}+2s_{*})\leq\sum_{i=1}^{k}\lambda_{i}^{+}(A)w_{i}+2s_{*}\sqrt{k}\sqrt{\sum_{i=1}^{k}\sigma_{i}^{2}(A)},$

and the rest of the proof proceeds as before. ∎

There are a few extra useful facts that we can extract from the proof of
Proposition 25, namely that we have explicit candidates for extremal
eigenvectors and singular vectors. We will state these just for the largest
eigenvector, but of course they also hold in other situations.

######  Corollary 26.

Assume that $s\mapsto s^{-2}\Lambda^{*}(s)$ achieves its minimum at some
$s_{*}\geq 0$. For $1\ll t\ll n^{2}$, let $\ell=\lceil 1+\sqrt{t}/s_{*}\rceil$
and define $v\in\mathbb{R}^{n}$ by $v_{1},\dots,v_{\ell}=s_{*}^{1/2}t^{-1/4}$
and $v_{\ell+1},\cdots,v_{n}=0$. Then $|v|\leq 1+o(1)$ and

(68) $\ln\Pr(v^{T}A_{n}v\geq t)\geq-\frac{t^{2}L}{2}-o(t^{2}).$

Corollary 26 is immediate from the proof of Proposition 25, because in the
case $k=1$ and $w_{1}=\sqrt{t}$, the $M$ that we constructed in that proof is
exactly $\sqrt{t}vv^{T}$.

###  5.4. The LDP

Putting together Corollary 22 and Proposition 25, we complete the proof of the
LDP (Theorem 9). Take a sequence $m_{n}$ satisfying $\sqrt{n}\ll m_{n}\ll n$,
and set $X=\frac{1}{m_{n}}(\sigma_{1}(A_{n}),\dots\sigma_{k}(A_{n}))$. Let
$E\subset\mathbb{R}^{k}$ be any closed set, and let $t=\inf_{x\in E}|x|$. Then
$\frac{1}{m_{n}}(\sigma_{1}(A_{n}),\dots,\sigma_{k}(A_{n}))\in E$ implies that
$\sum\sigma_{i}^{2}(A_{n})>m_{n}^{2}t^{2}$. By Corollary 22,

$\ln\Pr\left(X\in
E\right)\leq\ln\Pr\left(\sum_{i=1}^{k}\sigma_{i}^{2}(A_{n})>m_{n}^{2}t^{2}\right)\\\
\leq-\frac{m_{n}^{2}t^{2}L}{2}+O\left(n\ln\frac{m_{n}^{2}}{n}\right)=-\frac{m_{n}^{2}t^{2}L}{2}+o(m_{n}^{2}).$

On the other hand, if $E\subset\mathbb{R}^{k}$ is open, then choose any $w\in
E$. Since $E$ is open, there is some $\epsilon>0$ so that if $\langle
x,w\rangle\geq|w|^{2}$ and $|x|^{2}\leq|w|^{2}+\epsilon$ then $x\in E$. Now,
Proposition 25 implies that

(69) $\ln\Pr\left(\langle
X,w\rangle\geq|w|^{2}\right)=\ln\Pr\left(\sum_{i}\sigma_{i}(A_{n})w_{i}\geq
m_{n}|w|^{2}\right)\geq-\frac{m_{n}^{2}|w|^{2}L}{2}-o(m_{n}^{2})$

On the other hand, Corollary 22 implies that

$\ln\Pr\left(|X|^{2}>|w|^{2}+\epsilon\right)=\ln\Pr\left(\sum_{i}\sigma_{i}^{2}(A_{n})\geq
m_{n}^{2}(|w|^{2}+\epsilon)\right)\\\
\leq-\frac{m_{n}^{2}(|w|^{2}+\epsilon)L}{2}-o(m_{n}^{2}).$

In particular, $\Pr(|X|^{2}>|w|^{2}+\epsilon)$ is dominated by $\Pr(\langle
X,w\rangle\geq|w|^{2})$, implying that

(70) $\ln\Pr(X\in E)\geq\ln\Pr\left(\langle X,w\rangle\geq|w|^{2}\text{ and
}|X|^{2}\leq|w|^{2}+\epsilon\right)\geq-\frac{m_{n}^{2}|w|^{2}L}{2}-o(m_{n}^{2}).$

Since this holds for arbitrary $w\in E$, it implies the lower bound in the
LDP.

The second part of Theorem 9 follows the exact same argument, only it uses the
second part of Proposition 25.

###  5.5. The case of $\mathcal{G}(n,m)$

We next consider the case of Theorem 11. The first observation is that
$q\leq\frac{1}{2}$ if and only if $\Lambda^{*}(s)/s^{2}$ achieves its minimum
at some non-negative $s$.

######  Lemma 27.

If $\xi=-q$ with probability $1-q$ and $\xi=1-q$ with probability $q$ then
$\Lambda^{*}$ (the convex conjugate of $\xi$’s cumulant generating function)
satisfies

(71)
$\inf_{s\in\mathbb{R}}\frac{\Lambda^{*}(s)}{s^{2}}=\frac{\ln\frac{1-q}{q}}{1-2q},$

and the minimum is uniquely attained at $s=1-2q$.

###### Proof.

We recall that $\Lambda^{*}(s)=D(q+s,q)$ where

(72) $D(r,q)=r\ln\frac{r}{q}+(1-r)\ln\frac{1-r}{1-q}$

(with the convention that $D(r,q)=+\infty$ for $r\not\in(0,1)$). Note that
$D(r,q)$ is non-negative, convex, and has a double-root at $r=q$. Fix $q$ and
define

(73) $L(r)=\frac{D(r,q)}{(r-q)^{2}}=\frac{\Lambda^{*}(r-q)}{(r-q)^{2}}$

(defined by continuity at $r=q$); our task is then to minimize $L$. We compute

(74)
$L^{\prime}(r)=-\frac{(q+r)\ln\frac{r}{q}+(2-q-r)\ln\frac{1-r}{1-q}}{(r-q)^{3}}=:-\frac{F(r)}{(r-q)^{3}}.$

Then

$\displaystyle F^{\prime}(r)$
$\displaystyle=\ln\frac{r}{q}-\ln\frac{1-r}{1-q}+\frac{q}{r}-\frac{1-q}{1-r}$
$\displaystyle F^{\prime\prime}(r)$
$\displaystyle=(r-q)\left(\frac{1}{r^{2}}-\frac{1}{(1-r)^{2}}\right).$

In particular, $F^{\prime\prime}$ has exactly two roots on $(0,1)$: at
$r=\frac{1}{2}$ and at $r=q$ (counting with multiplicity in case
$q=\frac{1}{2}$). It follows that $F$ has at most 4 roots on $(0,1)$. On the
other hand, we can easily see that
$F(q)=F^{\prime}(q)=F^{\prime\prime}(q)=F(1-q)=0$. Hence, $F(r)$ has a triple-
root at $r=q$ and a single root at $r=1-q$, and no other roots. Since $r=q$ is
only a triple-root, $L^{\prime}(q)\neq 0$, and it follows that $r=1-q$ is the
only root of $L^{\prime}(r)$. It follows that $L(r)$ is minimized at either
$r=0$, $r=1$, or $r=1-q$. The possible minimum values are therefore

(75) $x:=q^{-2}\ln\frac{1}{1-q},\qquad
y:=(1-q)^{-2}\ln\frac{1}{q},\qquad\text{or }z:=\frac{\ln\frac{1-q}{q}}{1-2q}.$

We will show that $z$ is the smallest one. By symmetry in $q$ and $1-q$, it
suffices to show that $z\leq x$ for all $q$. Now,

(76)
$q^{2}(1-2q)(z-x)=q^{2}\ln\frac{1-q}{q}+(1-2q)\ln(1-q)=(1-q)^{2}\ln(1-q)-q^{2}\ln
q.$

Let $f(q)=(1-q)^{2}\ln(1-q)-q^{2}\ln q$, and we need to show that $f(q)<0$ for
$0<q<\frac{1}{2}$ and $f(q)>0$ for $\frac{1}{2}<q<1$. In fact, since
$f(q)=-f(1-q)$, it suffices to show only one of these. Finally, note that
$f(0)=f(\frac{1}{2})=0$, and $f^{\prime\prime}(q)>0$ for $0<q<\frac{1}{2}$,
and it follows that $f(q)<0$ for $0<q<\frac{1}{2}$. ∎

To complete the proof of Theorem 11, it is enough to show that the upper bound
of Corollary 22 and the lower bound of Proposition 25 still hold in this
setting; then the proof of the LDP proceeds exactly as in the proof of Theorem
9. Checking Corollary 22 is trivial: recalling that $A_{n}$ is the centered
adjacency matrix of $\mathcal{G}(n,m)$ for $|m-q\binom{n}{2}|=O(1)$, we let
$\tilde{A}_{n}$ be the centered adjacency matrix of $\mathcal{G}(n,q)$. Note
that the distribution of $A_{n}$ is equal to the distribution of
$\tilde{A}_{n}$, conditioned on the event that $\tilde{A}_{n}$ has exactly $m$
positive entries on the upper diagonal; call this event $E$. By Stirling’s
approximation, $\Pr(E)=\Omega(n^{-1})$, and it follows that for any event $F$,

(77) $\Pr(A_{n}\in F)=\Pr(\tilde{A}_{n}\in F\mid E)\leq\frac{\Pr(A_{n}\in
F)}{\Pr(E)}\leq O(n\Pr(\tilde{A}_{n}\in F)).$

In other words, $\ln\Pr(A_{n}\in F)\leq\ln\Pr(\tilde{A}_{n}\in F)+O(\ln n)$,
and so Corollary 22 immediately implies the same upper bound for
$\mathcal{G}(n,m)$.

For the lower bound, we need to look into the proof of Proposition 25. Recall
that in the proof of Proposition 25, we constructed a matrix $M$ with
$O(t)=o(n^{2})$ non-zero entries, all of which had the same value. For the
$\mathcal{G}(n,q)$ adjacency matrix $\tilde{A}_{n}$,
$\langle\tilde{A}_{n},M\rangle$ has a (scaled and translated) binomial
distribution; for the $\mathcal{G}(n,m)$ adjacency matrix $A_{n}$, $\langle
A_{n},M\rangle$ has a (scaled and translated) hypergeometric distribution.
Now, if $H_{k,n,r}$ denotes a hypergeometric random variable with population
size $n$, $k$ successes, and $r$ trials; and if $B_{q,r}$ denotes a binomial
random variable with success probability $q$ and $r$ trials; then one easily
shows using Stirling’s approximation that

(78) $|\ln\Pr(H_{k,n,r}=s)-\ln\Pr(B_{k/n,r}=s)|=O(r^{2}/n).$

In the setting of Proposition 25, the number of trials $r$ is the number of
non-zero elements in $M$, and since $r^{2}/n=O(t^{2}/n)=o(t)$, we have

(79) $\ln\Pr(\langle
A_{n},M\rangle>t)\geq\ln\Pr(\langle\tilde{A}_{n},M\rangle>t)-o(t).$

With this lower bound, we can follow the rest of the proof of Proposition 25
to complete the proof of Theorem 11.

##  6\. Proof of Theorem 10

Next, we consider the case that $\frac{\Lambda^{*}(s)}{s^{2}}$ does not
achieve its infimum at any $s>0$, and we construct an example showing that
taking $s\to 0$ does not yield the sharp bound. The basic idea is to use the
first part of Lemma 13, by producing a positive semi-definite matrix $M$ and
giving a lower bound on the tails of $\langle A,M\rangle$. The main challenge
is to find a good matrix satisfying the positive definiteness constraint: in
Proposition 25 we chose a matrix taking only one non-zero value, specifically,
$s_{*}\in\operatorname{argmin}\frac{\Lambda^{*}(s)}{s^{2}}$. The issue, of
course, is that if $s_{*}$ is negative then such matrix cannot be positive
semi-definite. Instead, we will construct a rank-1 matrix taking four
different non-zero values.

Consider a sequence $a_{1},\dots,a_{n}$ whose non-zero elements take $m$
different values, $\alpha b_{1},\dots,\alpha b_{m}$, with $\alpha b_{i}$
repeated $\tilde{m}_{i}=\beta m_{i}(1+o(1))$ times respectively (the addition
of the error term just allows us to deal with the fact that matrices have
integer numbers of rows and columns). We will think of $m_{i}$ and $b_{i}$ as
being fixed, while $\alpha$ and $\beta$ depend on the tail bound that we want
to show, with $\alpha$ being small and $\beta$ being large. Then for any
$t=\sum_{i=1}^{m}t_{i}$,

(80)
$\Pr\left(\sum_{i}a_{i}\xi_{i}>t\right)\geq\prod_{i=1}^{m}\Pr\left(\sum_{j=1}^{\lceil\tilde{m}_{i}\rceil}\xi_{j}>t/(\alpha
b_{i})\right)$

and so Theorem 24 implies that if $\frac{t_{i}}{\alpha\beta
m_{i}b_{i}}=\Theta(1)$ then

(81)
$\ln\Pr\left(\sum_{i}a_{i}\xi_{i}>t\right)\geq-\beta\sum_{i}m_{i}\Lambda^{*}\left(\frac{t_{i}}{\alpha\beta
m_{i}b_{i}}\right)-o\left(\beta\sum_{i}m_{i}\right)$

Our goal will be to choose the parameters $m_{i},b_{i},\alpha,\beta$, and
$t_{i}$ to make the right hand side large. First, we will treat $m_{i}$ and
$b_{i}$ as given, and optimize over $t_{i}$, $\alpha$, and $\beta$. We will
enforce the constraints $\sum_{i}t_{i}=t$ and
$\sum_{i}a_{i}^{2}=\alpha^{2}\beta\sum_{i}m_{i}b_{i}^{2}=2$.

Define

$\displaystyle\beta$
$\displaystyle=t^{2}\frac{\sum_{i}m_{i}b_{i}^{2}}{2\left(\sum_{i}m_{i}b_{i}\Lambda^{\prime}(b_{i})\right)^{2}}$
$\displaystyle\alpha$
$\displaystyle=2\left(\beta\sum_{i}m_{i}b_{i}^{2}\right)^{-1/2}=\frac{\sum_{i}m_{i}b_{i}\Lambda^{\prime}(b_{i})}{t\sum_{i}m_{i}b_{i}^{2}}$
$\displaystyle t_{i}$ $\displaystyle=\alpha\beta
m_{i}b_{i}\Lambda^{\prime}(b_{i}).$

With these choices, we have

(82) $\alpha^{2}\beta=\frac{2}{\sum_{i}m_{i}b_{i}^{2}},$

meaning that

(83) $\sum_{i}a_{i}^{2}=\alpha^{2}\beta\sum_{i}m_{i}b_{i}^{2}=2$

and

(84) $\sum_{i}t_{i}=\alpha\beta\sum_{i}m_{i}b_{i}\Lambda^{\prime}(b_{i})=t.$

(These turn out to be the optimal choices of $\alpha,\beta$, and $t$, although
we do not need to show this, since any choice will give us a bound.) Plugging
these parameters into (81), we obtain

(85)
$\ln\Pr\left(\sum_{i}a_{i}\xi_{i}>t\right)\geq-\frac{t^{2}}{2}\cdot\frac{\sum_{i}m_{i}b_{i}^{2}\cdot\sum_{i}m_{i}\Lambda^{*}(\Lambda^{\prime}(b_{i}))}{\left(\sum_{i}m_{i}b_{i}\Lambda^{\prime}(b_{i})\right)^{2}}-o(t^{2}),$

where the $o(t^{2})$ term depends on the parameters $m_{i}$ and $b_{i}$.

Next, we will define the parameters $m_{i}$ and $b_{i}$. Take
$\epsilon,\delta>0$, and define

$\displaystyle m_{1}$ $\displaystyle=\frac{1}{\epsilon^{2}}$ $\displaystyle
b_{1}$ $\displaystyle=\epsilon$ $\displaystyle m_{2}$
$\displaystyle=2\frac{\epsilon}{\delta^{3}}$ $\displaystyle b_{2}$
$\displaystyle=-\delta$ $\displaystyle m_{3}$
$\displaystyle=\frac{\epsilon^{4}}{\delta^{6}}$ $\displaystyle b_{3}$
$\displaystyle=\frac{\delta^{2}}{\epsilon},$

and note that it is possible to define a positive semi-definite integral
kernel taking the value $b_{i}/2$ on a set of measure $2m_{i}$, simply by
starting with a function taking the values $\sqrt{\epsilon}$ and
$-\delta/\sqrt{\epsilon}$ on sets of size $1/\epsilon$ and
$\epsilon/\delta^{3}$ respectively, and then taking the outer product of that
function with itself. It follows that if $\epsilon$ and $\delta$ are fixed and
$\beta$ is large (and $\alpha$ is arbitrary), then we can define a rank-1
p.s.d. matrix ($M$, say) with $(1+o(1))2\beta m_{i}$ entries taking the value
$\alpha b_{i}/2$; note that
$\|M\|_{F}^{2}=\frac{1+o(1)}{2}\alpha\beta^{2}\sum_{i}m_{i}=1+o(1)$. Since $A$
is a symmetric matrix with $\xi$ on the upper diagonal, this will yield

(86) $\langle A,M\rangle=\sum_{i}a_{i}\xi_{i}$

where $(a_{i})$ is a sequence containing $(1+o(1))\beta m_{i}$ copies of
$\alpha b_{i}$.

We will first choose a small $\delta$ and then choose a smaller $\epsilon$.
The error terms in the following analysis are taking this into account, so for
example we may write $\epsilon^{2}\delta^{-k}=o(\epsilon)$ no matter how large
$k$ is. Our next task is to compute the various expressions in (85), in terms
of $\epsilon$ and $\delta$. Before doing so, we observe some basic properties
of the Legendre transform.

######  Lemma 28.

Assume that $f$ is convex and differentiable and
$\lim_{x\to\infty}\frac{f(x)}{x^{2}}=0$. Then
$\lim_{x\to\infty}\frac{f^{*}(f^{\prime}(x))}{x^{2}}=0$.

###### Proof.

Fix $x$ and let $y=f^{\prime}(x)$. By the definition of $f^{*}$, we can write

(87) $f^{*}(y)=\sup_{z}\\{zy-f(z)\\},$

and note that the supremum is attained at $x=z$ (because the derivative is
zero, and the expression being supremized is concave). Hence,

(88) $f^{*}(f^{\prime}(x))=xf^{\prime}(x)-f(x).$

Convexity of $f$ implies that $f^{\prime}$ is non-decreasing, and so
$f(x)=o(x^{2})$ implies that $f^{\prime}(x)=o(x)$ as $x\to\infty$. Hence,
$f^{*}(f^{\prime}(x))=xf^{\prime}(x)-f(x)=o(x^{2})$. ∎

######  Lemma 29.

If $f$ is convex with $f(0)=f^{\prime}(0)=0$ and $f^{\prime\prime}(0)>0$, and
if both $f$ and $f^{*}$ are $\mathcal{C}^{4}$ in a neighborhood of $0$, then

(89)
$f^{*}(f^{\prime}(\epsilon))=f^{\prime\prime}(0)\frac{\epsilon^{2}}{2}+((f^{*})^{\prime\prime\prime}(0)(f^{\prime\prime})^{3}(0)+3f^{\prime\prime\prime}(0))\frac{\epsilon^{3}}{6}+O(\epsilon^{4})$

as $\epsilon\to 0$

###### Proof.

This is nothing but Taylor’s theorem and a computation. Setting $g=f^{*}$, we
compute

(90)
$\frac{d}{d\epsilon}g(f^{\prime}(\epsilon))=g^{\prime}(f^{\prime}(\epsilon))f^{\prime\prime}(\epsilon),$

and then

(91)
$\frac{d^{2}}{d\epsilon^{2}}g(f^{\prime}(\epsilon))=g^{\prime\prime}(f^{\prime}(\epsilon))(f^{\prime\prime}(\epsilon))^{2}+g^{\prime}(f^{\prime}(\epsilon))f^{\prime\prime\prime}(\epsilon),$

and finally

(92)
$\frac{d^{3}}{d\epsilon^{3}}g(f^{\prime}(\epsilon))=g^{\prime\prime\prime}(f^{\prime}(\epsilon))(f^{\prime\prime}(\epsilon))^{3}+3g^{\prime\prime}(f^{\prime}(\epsilon))f^{\prime\prime}(\epsilon)f^{\prime\prime\prime}(\epsilon)+g^{\prime}(f^{\prime}(\epsilon))f^{\prime\prime\prime\prime}(\epsilon).$

Our assumptions on $f$ ensure that $g^{\prime}(0)=0$, and hence the first-
order term vanishes, the second-order term at $\epsilon=0$ becomes

(93) $g^{\prime\prime}(0)(f^{\prime\prime}(0))^{2},$

and the third-order term at $\epsilon=0$ becomes

(94)
$g^{\prime\prime\prime}(0)(f^{\prime\prime}(0))^{3}+3g^{\prime\prime}(0)f^{\prime\prime}(0)f^{\prime\prime\prime}(0).$

Finally, note that $g^{\prime\prime}(0)f^{\prime\prime}(0)=1$. ∎

Note that $\Lambda$ satisfies the assumptions on $f$ in Lemmas 28 (because we
assumed that $\Lambda(s)=o(s^{2})$) and 29 (because every cumulant-generating
function defined on a neighborhood of zero is $\mathcal{C}^{\infty}$ in a
neighborhood of zero). Note that $\Lambda$ and $\Lambda^{*}$ both have a
second-order root at zero. Define

(95) $L=\Lambda^{\prime\prime}(0)>0.$

Expanding out the parameters in (85), we have

(96)
$\sum_{i}m_{i}b_{i}^{2}=1+2\frac{\epsilon}{\delta}+\frac{\epsilon^{2}}{\delta^{2}}$

for the first term in the numerator. The second term in the numerator is

$\displaystyle\sum_{i}m_{i}\Lambda^{*}(\Lambda^{\prime}(b_{i}))$
$\displaystyle=\frac{1}{\epsilon^{2}}(\Lambda^{*}\circ\Lambda^{\prime})(\epsilon)+2\frac{\epsilon}{\delta^{3}}(\Lambda^{*}\circ\Lambda^{\prime})(-\delta)+\frac{\epsilon^{4}}{\delta^{6}}(\Lambda^{*}\circ\Lambda^{\prime})(\delta^{2}/\epsilon).$

According to Lemma 28 and our assumptions on $\Lambda$, the last term is
$o(\epsilon^{2})$. Applying Lemma 29 to the other terms, we have

$\displaystyle\sum_{i}m_{i}\Lambda^{*}(\Lambda^{\prime}(b_{i}))$
$\displaystyle=\frac{L}{2}+M\frac{\epsilon}{6}+L\frac{\epsilon}{\delta}-M\frac{\epsilon}{3}+O(\epsilon^{2}+\epsilon\delta)$
$\displaystyle=\frac{L}{2}\left(1+\frac{2\epsilon}{\delta}\right)-M\frac{\epsilon}{6}+O(\epsilon^{2}+\epsilon\delta),$

where

(97)
$M=(\Lambda^{*})^{\prime\prime\prime}(0)L^{3}+3\Lambda^{\prime\prime\prime}(0).$

For the denominator in (85), we ignore the $i=3$ contribution, giving a lower
bound of

$\displaystyle\sum_{i}m_{i}\Lambda^{\prime}(b_{i})$
$\displaystyle\geq\frac{\Lambda^{\prime}(\epsilon)}{\epsilon}-2\frac{\epsilon\Lambda^{\prime}(-\delta)}{\delta^{2}}$
$\displaystyle=\Lambda^{\prime\prime}(0)+\frac{\epsilon}{2}\Lambda^{\prime\prime\prime}(0)+O(\epsilon^{2})+2\frac{\epsilon}{\delta}\Lambda^{\prime\prime}(0)-\epsilon\Lambda^{\prime\prime\prime}(0)+O(\epsilon\delta)$
$\displaystyle=L\left(1+2\frac{\epsilon}{\delta}\right)-\frac{\epsilon}{2}\Lambda^{\prime\prime\prime}(0)+O(\epsilon^{2}+\epsilon\delta).$

Putting everything together,

$\displaystyle\frac{\sum_{i}m_{i}\Lambda^{\prime}(b_{i})\cdot\sum_{i}m_{i}\Lambda^{*}(\Lambda^{\prime}(b_{i}))}{\left(\sum_{i}m_{i}\Lambda^{\prime}(m_{i})\right)^{2}}$
$\displaystyle=\frac{\left(1+\frac{2\epsilon}{\delta}+O(\epsilon^{2})\right)\left(\frac{L}{2}\left(1+\frac{2\epsilon}{\delta}\right)-\frac{\epsilon
M}{6}+O(\epsilon^{2}+\epsilon\delta)\right)}{\left(L\left(1+\frac{2\epsilon}{\delta}\right)-\frac{\epsilon\Lambda^{\prime\prime\prime}(0)}{2}+O(\epsilon^{2}+\epsilon\delta)\right)^{2}}$
$\displaystyle=\frac{\frac{L}{2}-\frac{\epsilon
M}{6}+O(\epsilon^{2}+\epsilon\delta)}{L^{2}-\epsilon
L\Lambda^{\prime\prime\prime}(0)+O(\epsilon^{2}+\epsilon\delta)}$
$\displaystyle=\frac{1}{2L}-\frac{\epsilon
M}{6L^{2}}+\frac{\epsilon\Lambda^{\prime\prime\prime}(0)}{2L^{2}}+O(\epsilon^{2}+\epsilon\delta)$
$\displaystyle=\frac{1}{2L}-\frac{\epsilon(\Lambda^{*})^{\prime\prime\prime}(0)L}{6}+O(\epsilon^{2}+\epsilon\delta),$

and in particular it is possible to choose $\delta$ and $\epsilon$ so that
this quantity is at most $(1-\eta)\frac{1}{2L}$ for some $\eta>0$.

Going back to (85) and recalling that the sequence $a_{i}$ can be realized as
the elements of a rank-1 p.s.d. matrix, $M$ say, with $\|M\|_{F}=1+o(1)$, we
have shown that

(98) $\ln\Pr(\lambda_{1}(A_{n})>t)\geq\ln\Pr(\langle
A,M\rangle>t\|M\|_{F})\geq-(1-\eta)\frac{t^{2}}{4L}-o(t^{2}).$

Replacing $t$ by $m_{n}t$ and recalling that
$L=\Lambda^{\prime\prime}(0)=\mathbb{E}\xi^{2}$ completes the proof of Theorem
10.

##  7\. Back to triangle counts

We now turn to the proofs of Theorems 1 and 2. The proofs are very similar, so
we devote most of this section to proving Theorem 1 and then indicate what
changes must be made to obtain Theorem 2.

Our eigenvalue LDP (Theorem 9) allows us to control the triangle-count
contribution from a constant number of very extreme eigenvalues, but in order
to fully characterize the behavior of the triangle-count, we also need to
handle the other eigenvalues. We will do this in two steps: we use Theorem 12
to control the contribution of the bulk eigenvalues, and then Corollary 22 to
show that the triangle count cannot be determined by $\omega(1)$ largish
eigenvalues. Bear in mind that we will be applying our eigenvalue LDP to
$\mathbb{E}A-A$, where $A$ is the adjacency matrix, because Theorem 11 is for
the positive eigenvalues of centered matrices, and we are interested in the
negative eigenvalues here.

###  7.1. The contribution of the bulk

We consider two functions $f_{1}$ and $f_{2}$, where

(99) $f_{1}(x)=\begin{cases}0&\text{if $x<0$}\\\ x^{3}&\text{if $0\leq
x<\sqrt{K}$}\\\ 3Kx-2K^{3/2}&\text{if $x\geq\sqrt{K}$}\end{cases}$

and $f_{2}(x)=-f_{1}(-x)$. Then both $f_{1}$ and $f_{2}$ are $3K$-Lipschitz
functions; also, $f_{1}$ is convex and $f_{2}$ is concave.

The following lemma is the main technical result of this section. Essentially,
it says that changing the triangle-count using non-extreme eigenvalues carries
a substantial entropy cost.

######  Lemma 30.

Let $A_{n}$ be the centered adjacency matrix of a $\mathcal{G}(n,m)$ graph.
There is a universal constant $C$ such that if $K\geq C$ then

(100)
$\Pr\left(\sum_{i:\lambda_{i}(A_{n})\geq-\sqrt{Kn}}\lambda_{i}^{3}(A_{n})<-\delta-O(n^{2})\right)\leq\exp\left(-\Omega\left(\frac{\delta^{2}}{n^{3}K^{2}}\right)\right).$

###### Proof.

We will prove the claim when $A_{n}$ is the centered adjacency matrix of a
$\mathcal{G}(n,p)$ graph, with $p=m/\binom{n}{2}$. The result for
$\mathcal{G}(n,m)$ follows from the fact that a $\mathcal{G}(n,m)$ graph can
be obtained by starting from $\mathcal{G}(n,p)$ and conditioning on the
(probability $\Omega(1/n)$) event that there are exactly $m$ edges.

Note that

(101) $f_{1}(x)+f_{2}(x)\leq\begin{cases}0&\text{if $x<-\sqrt{K}$}\\\
x^{3}&\text{if $x\geq-\sqrt{K}$}.\end{cases}$

Hence,

(102) $\sum_{i}(f_{1}+f_{2})(n^{-1/2}\lambda_{i}(A_{n}))\leq
n^{-3/2}\sum_{i:\lambda_{i}(A_{n})\geq-\sqrt{Kn}}\lambda_{i}^{3}(A_{n}).$

Since $-f_{2}$ is convex, Theorem 12 applies to both $f_{1}$ and $f_{2}$,
giving

(103)
$\Pr\left(\frac{1}{n}\operatorname{tr}[(f_{1}+f_{2})(n^{-1/2}A_{n})]\leq\frac{1}{n}\mathbb{E}\operatorname{tr}[(f_{1}+f_{2})(n^{-1/2}A_{n})]-s\right)\leq
2\exp(-\Omega(n^{2}s^{2}/K^{2}))$

whenever $s=\omega(K/n)$. From the inequality above, we also have

(104)
$\Pr\left(\sum_{i:\lambda_{i}(A_{n})\geq-\sqrt{Kn}}\lambda_{i}^{3}(A_{n})\leq
n^{3/2}\mathbb{E}\operatorname{tr}(f_{1}+f_{2})(n^{-1/2}A_{n})-s\right)\leq
2\exp\left(-\Omega\left(\frac{s^{2}}{K^{2}n^{3}}\right)\right).$

It remains to control
$\mathbb{E}\operatorname{tr}[(f_{1}+f_{2})(n^{-1/2}A_{n})]$; specifically, we
want to show that $\mathbb{E}\operatorname{tr}(f_{1}+f_{2})(n^{-1/2}A_{n})$ is
close to $n^{-3/2}\mathbb{E}\operatorname{tr}(A_{n}^{3})$ (which is
$O(\sqrt{n})$). But note that

$|\operatorname{tr}[(f_{1}+f_{2})(n^{-1/2}A_{n})-n^{-3/2}A_{n}^{3}]|\\\ \leq
n^{-3/2}\sum_{i:|\lambda_{i}|>\sqrt{Kn}}|\lambda_{i}(A_{n})|^{3}\leq
n^{-1/2}|s_{1}(A_{n})|^{3}1_{\\{|s_{1}(A_{n})|>\sqrt{Kn}\\}},$

where $s_{1}(A_{n})$ is the largest singular value of $A_{n}$. But Proposition
21 implies that if $K$ is sufficiently large then
$\mathbb{E}[|s_{1}(A_{n})|^{3}1_{\\{|s_{1}(A_{n})|>\sqrt{Kn}\\}}]\leq\exp(-\Omega(\sqrt{n}))$.
Hence,

(105)
$\Pr\left(\sum_{i:\lambda_{i}(A_{n})\geq-\sqrt{Kn}}\lambda_{i}^{3}(A_{n})\leq
n^{3/2}\mathbb{E}\operatorname{tr}(A_{n}^{3})-s-\exp(-\Omega(\sqrt{n}))\right)\leq
2\exp\left(-\Omega\left(\frac{s^{2}}{K^{2}n^{3}}\right)\right).$

Finally, note that $\mathbb{E}\operatorname{tr}(A_{n}^{3})=O(n^{2})$. ∎

We will be interested in applying Lemma 30 when $\delta\gg n^{9/4}$. In this
case, the $O(n^{2})$ term becomes negligible and the probability bound is at
most $\exp(-\omega(n^{3/2}))$.

###  7.2. Many large negative eigenvalues

There is one situation that we still need to handle: the possibility that
there are $\omega(1)$ eigenvalues smaller than $-\Omega(\sqrt{n})$, and
$\omega(1)$ of these eigenvalues contribute to the triangle count.

The first observation is that although Corollary 22 is written for a fixed
_number_ of singular values, it can be easily transferred to an inequality for
singular values above a certain threshold.

######  Corollary 31.

With the notation of Corollary 22, if $\sigma_{i}=\sigma_{i}(A)$ are the
singular values of $A$ then

(106) $\ln\Pr\left(\sqrt{\sum_{\sigma_{i}>\sqrt{Kn}}\sigma_{i}^{2}}\geq
t\right)\leq-\frac{t^{2}L}{2}+O\left(\frac{t^{2}}{K}\ln K\right)$

The same bound holds if $A$ is the centered adjacency matrix of a
$\mathcal{G}(n,m)$ graph.

###### Proof.

Set $k=\lceil t^{2}/(Kn)\rceil$ and observe that if
$s_{1},\dots,s_{k}\geq\sqrt{Kn}$ then $\sum_{i=1}^{k}\sigma_{i}^{2}\geq t$.
Hence, we either have

(107)
$\sum_{\sigma_{i}>\sqrt{Kn}}\sigma_{i}^{2}\leq\sum_{i=1}^{k}\sigma_{i}^{2},$

or else $\sum_{i=1}^{k}\sigma_{i}^{2}\geq t$. It follows that

(108) $\ln\Pr\left(\sqrt{\sum_{\sigma_{i}>\sqrt{Kn}}\sigma_{i}^{2}}\geq
t\right)\leq\ln\Pr\left(\sqrt{\sum_{i=1}^{k}\sigma_{i}^{2}}\geq t\right),$

and we conclude by applying Corollary 22 with our choice of $k$.

Finally, if $A$ is the centered adjacency matrix of a $\mathcal{G}(n,m)$ graph
then we use the same argument that was used to extend Corollary 22 to the
$\mathcal{G}(n,m)$ case, namely that a $\mathcal{G}(n,m)$ graph can be
obtained by conditioning a $\mathcal{G}(n,p)$ graph on an event of
$\Omega(n^{-1})$ probability. ∎

###  7.3. The upper bound in Theorem 1

Let $A$ be the adjacency matrix of a $\mathcal{G}(n,m)$ graph and recall that
$\tau(A)=\frac{\operatorname{tr}[A^{3}]}{n(n-1)(n-2)}=\frac{\operatorname{tr}[A^{3}]}{n^{3}}+O(1/n)$.
Let $\tilde{A}=A-\mathbb{E}A$; by Corollary 4,

(109) $\Pr(\tau(A)\leq p^{3}-t)=\Pr(\operatorname{tr}[A^{3}]\leq
n^{3}p^{3}-n^{3}t+O(n^{2}))\leq\Pr(\operatorname{tr}[\tilde{A}^{3}]\leq-n^{3}t+O(n^{2})).$

Writing out
$\operatorname{tr}[\tilde{A}^{3}]=\sum_{i}\lambda_{i}^{3}(\tilde{A})$, choose
$K=\omega(1)$ and $\epsilon=o(1)$ such that $K/\epsilon=o(n^{1/2}t^{2/3})$.
Applying Lemma 30 to $-\tilde{A}$ gives

(110)
$\Pr\left(\sum_{i:\lambda_{i}\geq-\sqrt{Kn}}\lambda_{i}^{3}(\tilde{A})<-\epsilon
tn^{3}\right)\leq\exp\left(-\Omega\left(\frac{\epsilon^{2}t^{2}n^{3}}{K^{2}}\right)\right)=\exp(-\omega(n^{2}t^{2/3}))$

On the other hand, Jensen’s inequality implies that

(111)
$\left|\sum_{i:\lambda_{i}<-\sqrt{Kn}}\lambda_{i}^{3}\right|\leq\left(\sum_{i:\lambda_{i}<-\sqrt{Kn}}\lambda_{i}^{2}\right)^{3/2}\leq\left(\sum_{i:\sigma_{i}>\sqrt{Kn}}\sigma_{i}^{2}\right)^{3/2},$

where $\lambda_{i}=\lambda_{i}(\tilde{A})$ and
$\sigma_{i}=\sigma_{i}(\tilde{A})$. Recall here that
$L=\inf_{s\in\mathbb{R}}\frac{\Lambda^{*}(s)}{s^{2}}$, where $\Lambda$ is the
cumulant-generating function of an entry of $\tilde{A}$. Lemma 27 (with
$q=1-p$) implies that $L=\frac{\ln\frac{p}{1-p}}{2p-1}$. By Corollary 31 (and
taking into account the fact that $\epsilon=o(1)$ and $K=\omega(1)$),

$\displaystyle\Pr\left(\sum_{i:\lambda_{i}<-\sqrt{Kn}}\lambda_{i}^{3}(\tilde{A})<-(1-\epsilon)tn^{3}\right)$
$\displaystyle\leq\Pr\left(\sqrt{\sum_{i:\sigma_{i}>\sqrt{Kn}}\sigma_{i}^{2}}>(1-\epsilon)^{1/3}t^{1/3}n\right)$
$\displaystyle\leq\exp\left(-\frac{L}{2}t^{2/3}n^{2}+o(t^{2/3}n^{2})\right).$

Combined with (110), this yields

(112) $\ln\Pr\left(\operatorname{tr}[\tilde{A}^{3}]\leq-
tn^{3}\right)\leq-\frac{Lt^{2/3}n^{2}}{2}(1+o(1)).$

Now we apply (109), noting that $n^{3}t=\omega(n^{2})$, and so
$n^{3}t+O(n^{2})=n^{3}t(1+o(1))$, to get

(113) $\ln\Pr(\tau(A)\leq p^{3}-t)\leq-\frac{Lt^{2/3}n^{2}}{2}(1+o(1)).$

This completes the proof of the upper bound in Theorem 1 but let us also note
two other facts that we can easily extract from the proof. From (110) we see
that only the extremely negative eigenvalues contribute to the triangle
deviation:

######  Corollary 32.

Conditioned on $\tau(A)\leq p^{3}-t$,
$\sum_{i:\lambda_{i}\leq-\Omega(\sqrt{n})}\lambda_{i}^{3}(\tilde{A})\leq-
tn^{3}(1-o(1))$ with high probability.

The other piece of information we can extract from our proof is that the
vertex degrees of a triangle-deficient graph are close to constant.

######  Corollary 33.

Conditioned on $\tau(A)\leq p^{3}-t$, if $d_{1},\dots,d_{n}$ are the vertex
degrees of the graph then with high probability

(114) $\sum_{i}(d_{i}-pn)^{2}=o(tn^{3}).$

###### Proof.

Since $\sum_{i}d_{i}=2m=n^{2}p+O(n)$, we have
$\sum_{i}(d_{i}-pn)^{2}=\sum_{i}d_{i}^{2}-p^{2}n^{3}+O(n^{2})$. Going back to
the proof of Lemma 3, we have

(115)
$\operatorname{tr}[\tilde{A}^{3}]\leq\operatorname{tr}[A^{3}]-p^{3}n^{3}-3p\sum_{i}(d_{i}-pn)^{2}+O(n^{2}).$

It follows that

(116) $\left\\{\tau(A)\leq
p^{3}-t\right\\}\subseteq\left\\{\operatorname{tr}[\tilde{A}^{3}]\leq-
tn^{3}-3p\sum_{i}(d_{i}-pn)^{2}+O(n^{2})\right\\}.$

Hence, if $tn^{3}\gg n^{2}$ then

$\ln\Pr\left(\tau(A)\leq p^{3}-t\text{ and }\sum_{i}(d_{i}-pn)^{2}\geq\epsilon
tn^{3}\right)\\\ \leq\ln\Pr\left(\operatorname{tr}[\tilde{A}^{3}]\leq-
tn^{3}(1+\Omega(\epsilon))\right)\leq-\frac{Lt^{2/3}n^{2}}{2}(1+\Omega(\epsilon)).$

In particular,

(117) $\Pr\left(\tau(A)\leq p^{3}-t\text{ and
}\sum_{i}(d_{i}-pn)^{2}\geq\epsilon tn^{3}\right)=o\left(\Pr\left(\tau(A)\leq
p^{3}-t\right)\right),$

and claim follows. ∎

###  7.4. The lower bound in Theorem 1

In showing the lower bound of Theorem 1, we need to apply Corollary 5 (instead
of Corollary 4 as in the upper bound), and therefore we need to control
$\operatorname{tr}[\tilde{A}^{3}]$ and $\sum_{i}d_{i}^{2}$ simultaneously. To
do this, take $v$ and $\ell$ as in Corollary 26 (applied with $t^{2/3}n^{2}$
in place of $t$). Now, let $\xi_{1},\dots,\xi_{\binom{n}{2}}$ be some ordering
of the upper diagonal of $\tilde{A}$, ordered so that the first
$\xi_{1},\dots,\xi_{\binom{\ell}{2}}$ correspond to the upper diagonal of the
upper-left $\ell\times\ell$ principal submatrix. Then
$\langle\tilde{A},vv^{T}\rangle=2\sum_{i=1}^{\binom{\ell}{2}}v_{1}^{2}\xi_{i}$,
and so conditioning on $\langle\tilde{A},vv^{T}\rangle<-t^{1/3}n$ is
equivalent to conditioning on
$\sum_{i=1}^{r}\xi_{i}<-\frac{t^{1/3}n}{2v_{1}^{2}}$ (where we have set
$r=\binom{\ell}{2}$).

Let $\Omega$ be the event that $\langle\tilde{A},vv^{T}\rangle\leq-t^{1/3}n$.
To prove the lower bound of Theorem 1, we show three properties:

  1. (1)

$\ln\Pr(\Omega)\geq-\frac{t^{2/3}n^{2}L}{2}(1+o(1))$.

  2. (2)

Conditioned on $\Omega$, $\sum_{i}d_{i}^{2}=n^{3}p^{2}+O(n^{2})$ with
probability at least $\exp(-o(t^{2/3}n^{2}))$.

  3. (3)

Conditioned on $\Omega$, $\operatorname{tr}[\tilde{A}^{3}]\leq-
tn^{3}(1-\epsilon)$ with probability at least
$1-\exp(-\Omega(\epsilon^{2/3}t^{2/3}n^{2}))$.

To complete the proof of the lower bound in Theorem 1 from these three facts,
we choose $\epsilon\to 0$ slowly enough that the probability of failure in
item (3) is at most half the probability of success in item (2). It then
follows that with probability at least $\exp(-t^{2/3}n^{2}L/2(1+o(1))$,
$\Omega$ holds together with properties (2) and (3). In particular, we have
shown that

(118) $\ln\Pr\left(\operatorname{tr}[\tilde{A}^{3}]\leq-
tn^{3}-\Omega(n^{2})\text{ and }\sum_{i}d_{i}^{2}\leq
n^{3}p^{2}+O(n^{2})\right)\geq-\frac{t^{2/3}n^{2}L}{2}(1+o(1)),$

and so the lower bound of Theorem 1 follows from Corollary 5.

Note that the first claimed property follows immediately from Corollary 26.

Next we prove the second property, noting that $\ell=\Theta(t^{1/3}n)$ and so
$\ell^{3}/n=O(tn^{2})=o(t^{2/3}n^{2})$.

######  Lemma 34.

Conditioned on $\Omega$, we have $\sum_{i}d_{i}^{2}=n^{3}p^{2}+O(n^{2})$ with
probability at least $\exp(-O(\ell^{3}/n))$.

###### Proof.

We decompose $A$ block-wise as

$A=\begin{bmatrix}A_{11}&A_{12}\\\ A_{21}&A_{22}\end{bmatrix}$

where $A_{11}$ has size $\ell\times\ell$. Note that the event $\Omega$ amounts
to conditioning on the number of ones in $A_{11}$, and that the number of ones
in $A_{11}$ is between 0 and $\ell^{2}$. For some $0\leq s\leq\ell^{2}$, let
$\Omega_{s}$ be the event that $A_{11}$ has $s$ ones; we will prove the claim
conditioned on each $\Omega_{s}$ and then it follows for $\Omega$.

Let $\tilde{\Omega}_{s}$ be the event that $A_{12}$ has $\ell pn-s+\eta$ ones
for $|\eta|\leq 1$ (where the $\eta$ term is merely to account for
integrality). Conditioned on $\Omega_{s}\cap\tilde{\Omega}_{s}$,
$d_{1},\dots,d_{\ell}$ have expectation $pn\pm O(1)$, and it follows that
$d_{\ell+1},\dots,d_{n}$ also have expectation $pn\pm O(1)$. Note that –
conditioned on $\Omega_{s}\cap\tilde{\Omega}_{s}$, each $d_{i}$ is distributed
as either a hypergeometric random variable or a sum of two independent
hypergeometric random variables; it follows from standard concentration
results that conditioned on $\Omega_{s}\cap\tilde{\Omega}_{s}$,

$\sum_{i}d_{i}^{2}=n^{3}p^{2}+O(n^{2})$

with high probability.

It therefore suffices to lower bound $\Pr(\tilde{\Omega}_{s}\mid\Omega_{s})$,
which is exactly the probability that a hypergeometric random variable – with
$\binom{n}{2}-\binom{\ell}{2}$ population, $p\binom{n}{2}-\Theta(\ell^{2})$
successes, and $n\ell$ trials – deviates from its mean by order
$\Theta(\ell^{2})$. Since a deviation of order $\Theta(\ell^{2})$ is a
deviation of $\Theta(\ell^{3/2}n^{-1/2})$ standard deviations, Stirling’s
approximation implies that

$\Pr(\tilde{\Omega}_{s}\mid\Omega_{s})=\exp(-O(\ell^{3}/n)).$

∎

Finally, we prove the third property claimed above.

######  Lemma 35.

For any $\epsilon>0$,

$\Pr(\Omega\text{ and }\operatorname{tr}[\tilde{A}^{3}]\geq-\epsilon
tn^{3})\leq\exp(-\Omega(\epsilon^{2/3}t^{2/3}n^{2})).$

###### Proof.

On the event $\Omega$, we have $\lambda_{n}(\tilde{A})\leq-t^{1/3}n$, and so
in order to have $\Omega$ and $\operatorname{tr}[\tilde{A}^{3}]\geq
tn^{3}(1-a_{n})$ we must have

$\sum_{i=1}^{n-1}\lambda_{i}(\tilde{A})^{3}\geq a_{n}tn^{3}.$

Now, Lemma 30 implies that only extremely large eigenvalues can contribute:
for a sufficiently large $K$ we have

$\Pr\left(\sum_{i:\lambda_{i}(\tilde{A})\geq\sqrt{Kn}}\lambda_{i}^{3}(\tilde{A})\geq
a_{n}tn^{3}\right)\leq\exp(-\Omega(a_{n}^{2}t^{2}n^{3})),$

which is less than $\exp(-\omega(n^{2}t^{2/3}))$ if $a_{n}\to 0$ sufficiently
slowly.

In order to control the contribution of the large eigenvalues, consider the
symmetric random matrix $B$ having independent upper-diagonal entries, with
each entry $B_{ij}$ having the same distribution as $\tilde{A}_{ij}$ given
$\Omega$. Because the distribution of $\tilde{A}$ given $\Omega$ can be
obtained by conditioning $B$ on an event of probability $\Omega(1/n)$, it
suffices to show that

$\Pr\left(\sum_{i:\lambda_{i}(B)\geq\sqrt{Kn}}\lambda_{i}(B)^{2}\geq\epsilon^{2/3}t^{2/3}n^{2}\right)\leq\exp(-\Omega(\epsilon^{2/3}t^{2/3}n^{2})),$

But this follows because $\mathbb{E}B=\mathbb{E}[\tilde{A}\mid\Omega]$ is
negative semi-definite and we may apply Remark 23 to $B-\mathbb{E}B$. ∎

###  7.5. The two extreme eigenvalues

In proving the upper bound on $\Pr(\tau(A)\leq p^{3}-t)$, we applied the
inequality $\sum_{i}|a_{i}|^{3}\leq(\sum_{i}a_{i}^{2})^{3/2}$ to the
collection of most-negative eigenvalues. In order to understand how these most
negative eigenvalues are actually distributed, observe that in order for the
inequality above to be an equality, all but one of the terms in the sum must
be zero. Made quantitative, this observation implies that in order for our
probability upper bound to be tight, the smallest eigenvalue must dominate the
others. In what follows, we write $\|a\|_{p}^{p}$ for $\sum_{i}|a_{i}|^{p}$.

######  Lemma 36.

Let $a_{1},\dots$ be a sequence of non-negative numbers, in non-increasing
order. For $\epsilon>0$, if

(119) $\sum_{i\geq 2}a_{i}^{3}\geq\epsilon a_{1}^{3}$

then

(120) $\|a\|_{2}^{2}\geq(1+\epsilon)^{1/3}\|a\|_{3}^{2}.$

###### Proof.

If $\sum_{i\geq 2}a_{i}^{3}\geq\epsilon a_{1}^{3}$ then
$\|a\|_{\infty}^{3}=a_{1}^{3}\leq\frac{\|a\|_{3}^{3}}{1+\epsilon}$. Then
$\|a\|_{3}^{3}\leq\|a\|_{\infty}\|a\|_{2}^{2}\leq(1+\epsilon)^{-1/3}\|a\|_{3}\|a\|_{2}^{2}$,
and the claim follows. ∎

Applying Lemma 36 to the most negative eigenvalues of $\tilde{A}$ allows us to
show that the eigenvalues of $\tilde{A}$ satisfy the claims that Theorem 1
makes for the eigenvalues of $A$.

######  Corollary 37.

In the setting of Theorem 1, for any $\epsilon>0$, conditioned on $\tau(A)\leq
p^{3}-t$ we have

(121) $\lambda_{n}^{3}(\tilde{A})\leq-(1-\epsilon)tn^{3}\text{ and
}\lambda_{n-1}^{3}(\tilde{A})\geq-\epsilon tn^{3}$

with high probability.

###### Proof.

Let $S=\\{i:\lambda_{i}(\tilde{A})\leq-\Omega(\sqrt{n})\\}$. By Corollary 32,
for any $\delta>0$, conditioned on $\tau(A)\leq p^{3}-t$ we have

(122) $\sum_{i\in S}\lambda_{i}^{3}(\tilde{A})\leq-(1-\delta)tn^{3}$

with high probability. On this event, we either have
$\lambda_{n}^{3}(\tilde{A})\leq-(1-\delta-\epsilon)tn^{3}$ or $\sum_{i\in
S\setminus\\{n\\}}\lambda_{i}^{3}(\tilde{A})\leq-\epsilon tn^{3}$. We will
show that for some $\delta=\Omega(\epsilon)$,

(123) $\Pr\left(\sum_{i\in
S}\lambda_{i}^{3}(\tilde{A})\leq-(1-\delta)tn^{3}\text{ and }\sum_{i\in
S\setminus\\{n\\}}\lambda_{i}^{3}(\tilde{A})\leq-\epsilon tn^{3}\right)$

is much smaller than $\Pr(\tau(A)\leq p^{3}-t)$; this will imply the claim.

Indeed, applying Lemma 36 to the sequence of $|\lambda_{i}|$ for $i\in S$, we
see that if

(124) $\sum_{i\in S}\lambda_{i}^{3}(\tilde{A})\leq-(1-\delta)tn^{3}\text{ and
}\sum_{i\in S\setminus\\{n\\}}\lambda_{i}^{3}(\tilde{A})\leq-\epsilon tn^{3}$

then

(125) $\sum_{i\in
S}\lambda_{i}^{2}(\tilde{A})\geq(1+\epsilon)^{1/3}(1-\delta)t^{2/3}n^{2}\geq(1+\Omega(\epsilon))t^{2/3}n^{2},$

where the last inequality follows by choosing a sufficiently small
$\delta=\Omega(\epsilon)$. But Corollary 31 implies that

$\displaystyle\Pr\left(\sum_{i\in
S}\lambda_{i}^{2}(\tilde{A})\geq(1+\Omega(\epsilon))t^{2/3}n^{2}\right)$
$\displaystyle\leq\exp\left(-(1+\Omega(\epsilon))(1-o(1))\frac{t^{2/3}n^{2}L}{2}\right)$
$\displaystyle=o(\Pr(\tau(A)\leq p^{3}-t)),$

where the final bound follows from the lower bound of Theorem 1. ∎

To complete the proof of Theorem 1, we need to pass from the eigenvalues of
$\tilde{A}$ to the eigenvalues of $A$; recall that
$A=\tilde{A}+p\mathbf{1}-pI$. Since $p\mathbf{1}\geq 0$, we have

(126) $\lambda_{n-1}(A)\geq\lambda_{n-1}(\tilde{A})-p,$

and so $\lambda_{n-1}(\tilde{A})\geq-o(tn^{3})$ implies the same for
$\lambda_{n-1}(A)$. For $\lambda_{n}$, we have
$\lambda_{n}(A)\leq\lambda_{n}(\tilde{A}+p\mathbf{1})$ and so it remains to
take care of the $p\mathbf{1}$ term.

Let $v$ be an eigenvector with eigenvalue $\lambda_{n}(\tilde{A})$ satisfying
$|v|^{2}=1$. Then $|\langle
v,\tilde{A}\mathbf{1}\rangle|=|\lambda_{n}(\tilde{A})||\langle
v,\mathbf{1}\rangle|$; conditioned on $\tau(A)\leq p^{3}-t$, this is
$(1+o(1))tn^{3}|\langle v,\mathbf{1}\rangle|$ with high probability. On the
other hand
$\tilde{A}\mathbf{1}=(A-p\mathbf{1}+pI)\mathbf{1}=d-p(n-1)\mathbf{1}$, where
$d$ whose entries are the vertex degrees. By Corollary 33, conditioned on
$\tau(A)\leq p^{3}-t$ we have $|d-pn\mathbf{1}|^{2}=o(tn^{3})$, and since
$|\mathbf{1}|^{2}=n=o(tn^{3})$, we also have
$|\tilde{A}\mathbf{1}|^{2}=|d-p(n-1)\mathbf{1}|^{2}=o(tn^{3})$. Hence,

(127) $(1+o(1))tn^{3}|\langle v,\mathbf{1}\rangle|=|\langle
v,\tilde{A}\mathbf{1}\rangle|\leq|\tilde{A}\mathbf{1}|=o(tn^{3}),$

and it follows that $|\langle v,\mathbf{1}\rangle|=o(1)$. Finally, note that

(128) $v^{T}(\tilde{A}+p\mathbf{1})v=v^{T}\tilde{A}v+p|\langle
v,\mathbf{1}\rangle|^{2}=\lambda_{n}(\tilde{A})+o(1),$

and so by Rayleigh’s criterion it follows that
$\lambda_{n}(\tilde{A}+p\mathbf{1})\leq\lambda_{n}(\tilde{A})+o(1)$. This
completes the proof of Theorem 1.

###  7.6. Theorem 2

Like Theorem 1, Theorem 2 has three elements: an upper bound on the
probability of a moderate deviation, a lower bound, and a bound on the most
negative eigenvalue of the adjacency matrix.

The upper bound is proved exactly as in the proof of Theorem 1. The singular
values of the eigenvalues are controlled by the rate function involving
$\inf_{x\in\mathbb{R}}\frac{\Lambda^{*}(s)}{s^{2}}$, which we have already
established to be $\frac{\ln\frac{1-p}{p}}{2(1-2p)}$. Upper bounds on singular
values then give upper bounds on eigenvalues. The entire argument is
independent of whether $p\geq\frac{1}{2}$ or $p<\frac{1}{2}$.

The proof of the lower bound in Theorem 2 is similar to that of the lower
bound in Theorem 1, except that we use the vector
$v=(\frac{1}{\sqrt{n}},\dots,\frac{1}{\sqrt{n}},-\frac{1}{\sqrt{n}},\dots,-\frac{1}{\sqrt{n}})$.
For this $v$, Cramér’s theorem shows that
$\ln\Pr(\langle\tilde{A},vv^{T}\rangle\leq-t^{1/3}n)\geq-\frac{t^{2/3}n^{2}}{2p(1-p)}(1+o(1))$,
and the rest of the proof proceeds as before. (Note that we cannot use the
vector $v$ constructed in the proof of Theorem 10, because Lemma 35 fails for
that $v$: the matrix $\mathbb{E}[\tilde{A}\mid\Omega]$ is not negative semi-
definite.)

For the claim about the eigenvalue, we use Lemma 36: fix $\eta>0$ and $K>0$
and consider the event $\Omega$ on which

$\sum_{\lambda_{i}(\tilde{A})\leq-\sqrt{Kn}}\lambda_{i}^{3}(\tilde{A})\leq-
tn^{3}$

but $\lambda_{n}^{3}(\tilde{A})\geq-\frac{1}{1+\eta}tn^{3}$. According to
Lemma 36, on this event we have

$\sum_{\lambda_{i}(\tilde{A})\leq-\sqrt{Kn}}\lambda_{i}^{2}(\tilde{A})\geq(1+\eta)^{1/3}t^{2/3}n^{2}.$

By Corollary 31 (for a sufficiently slowly growing $K=\omega(1)$),

$\ln\Pr(\Omega)\leq-\frac{t^{2/3}n^{2}(1+\eta)^{1/3}\ln\frac{p}{1-p}}{2(2p-1)}+o(t^{2/3}n^{2}),$

which, for sufficiently large $\eta$ (depending on $p$) implies that

$\ln\Pr(\Omega)\leq-(1+\Omega(1))\frac{t^{2/3}n^{2}}{2p(1-p)}.$

It follows from the lower bound in Theorem 2 that $\Pr(\Omega\mid\tau\leq
p^{3}-t)\to 0$. Together with Lemma 30 – which shows that eigenvalues larger
than $-\sqrt{Kn}$ are unlikely to contribute – this implies that
$\lambda_{n}^{3}\leq-\frac{1}{1+\eta}tn^{3}$ with high probability given
$\tau\leq p^{3}-t$. (The main difference here compared to the proof of Theorem
1 is that because we lack matching upper and lower bounds on the log-
probabilities, we cannot take $\eta\approx 0$.)

## References

  * [1] C. Goldschmidt, S. Griffiths and A. Scott, Moderate deviations of subgraph counts in the Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$, Trans. Amer. Math. Soc. 373 (2020) 5517–5585.
  * [2] S. Janson, Poisson approximation for large deviations, Random Structures & Algorithms 1 (1990) 221–229.
  * [3] S. Boucheron, G. Lugosi, P. Massart etal, Concentration inequalities using the entropy method, Ann. Prob. 31 (2003) 1583–1614.
  * [4] S. Chatterjee, The missing log in large deviations for triangle counts, Random Structures & Algorithms 40 (2012) 437–451.
  * [5] S. Janson and A. Ruciński, The Infamous Upper Tail, Random Structures & Algorithms 20 (2002) 317-342.
  * [6] C. Radin and L. Sadun, Phase transitions in a complex network, J. Phys. A 46 (2013) 12 pp.
  * [7] C. Radin and L. Sadun, Singularities in the entropy of asymptotically large simple graphs, J. Stat. Phys. 158 (2015) 853–865.
  * [8] S. Chatterjee and A. Dembo, Nonlinear large deviations, Adv. Math. 299 (2016) 396–450.
  * [9] N. Cook and A. Dembo, Large deviations of subgraph counts for sparse Erdős-Rényi graphs, Adv. Math, 373 (2020) 107289.
  * [10] E. Lubetzky and Y. Zhao, On the variational problem for upper tails in sparse random graphs, Random Structures Algorithms 50 (2017) 420–436.
  * [11] B. Bhattacharya, S. Ganguly, E. Lubetzky and Y. Zhao, Upper tails and independence polynomials in random graphs, Adv. Math. 319 (2017) 313–347.
  * [12] Y. Zhao, On the lower tail variational problem for random graphs, Combin. Probab. Comput. 26 (2017) 301–320.
  * [13] S. Bhattacharya and A. Dembo, Upper Tail For Homomorphism Counts in Constrained Sparse Random Graphs, arXiv:1909.03045
  * [14] B. Gunby, Upper Tails of Subgraph Counts in Sparse Regular Graphs, arXiv:2010.00658.
  * [15] E. Lubetzky and Y. Zhao, On replica symmetry of large deviations in random graphs, Random Structures Algorithms 47 (2015) 109–146.
  * [16] S. Janson and L. Warnke, The lower tail: Poisson approximation revisited, Random Structures and Algorithms 48 (2016) 219–246.
  * [17] S. Chatterjee, An introduction to large deviations for random graphs, Bull. Amer. Math. Soc. 53 617–642.
  * [18] Svante Janson, Orthogonal decompositions and functional limit theorems for random graph statistics, American Mathematical Soc. 1994.
  * [19] M. Harel, F. Mousset and W. Samotij, Upper tails via high moments and entropic stability, arXiv:1904.08212.
  * [20] J. Neeman, C. Radin and L. Sadun, Phase transitions in finite random networks, J. Stat. Phys. 181 (2020) 30–328.
  * [21] C. Radin, K. Ren and L. Sadun, The asymptotics of large constrained graphs, J. Phys. A: Math. Theor. 47 (2014) 175001.
  * [22] R. Kenyon, C. Radin, K. Ren and L. Sadun, Multipodal structure and phase transitions in large constrained graphs, J. Stat. Phys. 168 (2017) 233–258.
  * [23] R. Kenyon, C. Radin, K. Ren and L. Sadun, Bipodal structure in oversaturated random graphs, Int. Math. Res. Notices, 2018 (2016) 1009–1044.
  * [24] C. Radin, K. Ren and L. Sadun, A symmetry breaking transition in the edge/triangle network model, Ann. Inst. H. Poincaré D 5 (2018) 251–286.
  * [25] R. Kenyon, C. Radin, K. Ren and L. Sadun, The phases of large networks with edge and triangle constraints, J. Phys. A: Math. Theor. 50 (2017) 435001\.
  * [26] H. Koch, Vertex order in some large constrained random graphs, SIAM J. Math. Anal. 48 (2016) 2588–2601.
  * [27] S. Chatterjee and S.R.S. Varadhan, The large deviation principle for the Erdős-Rényi random graph, Eur. J. Combin. 32 (2011) 1000–1017.
  * [28] A. Dembo and E. Lubetzky, A large deviation principle for the Erdős-Rényi uniform graph, Electron. Commun. Probab. 23 (2018) 1–13.
  * [29] A. Guionnet and J. Husson, Large deviations for the largest eigenvalue of Rademacher matrices, Ann. Prob. 48 (2000) 1436–1465.
  * [30] F. Augeri, Large deviations principle for the largest eigenvalue of Wigner matrices without Gaussian tail, Electron. J. Probab. 21 (2016) 49 pp.
  * [31] B. Bhattacharya and S. Ganguly, Upper Tails for Edge Eigenvalues of Random Graphs, SIAM Journal on Discrete Mathematics 34 (2020) 1069–1083.
  * [32] F. Augeri, A. Guionnet and J. Husson, Large deviations for the largest eigenvalue of sub-Gaussian matrices, arXiv:1911.10591.
  * [33] A. Guionnet and O. Zeitouni, Concentration of the Spectral Measure for Large Matrices, Electron. Commun. Probab. 5 (2020) 119–136.
  * [34] T. Tao, Topics in random matrix theory, Americal Mathematical Soc. 2012.
  * [35] R. Vershynin, High-dimensional probability: An introduction with applications in data science, Cambridge University Press 2018.
  * [36] O. Kallenberg, Foundations of Modern Probability, Second Edition, Springer 2001.