# Moderate Deviations of Triangle Counts in the Erdős-Rényi Random Graph
$G(n,m)$: The Dense case

José D. Alvarado and Gabriel Dias do Couto and Simon Griffiths  Instituto de
Matemática e Estatística, Universidade de São Paulo, Rua do Matão 1010,
05508–090 São Paulo, Brazil<EMAIL_ADDRESS>Departamento de
Matemática, PUC-Rio, Rua Marquês de São Vicente 225, Gávea, 22451-900 Rio de
Janeiro, Brazil<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Let $N_{\triangle}(G)$ be the number of triangles in a graph $G$. In [GGS] and
[NRS22] (respectively) the following bounds were proved on the lower tail
behaviour of triangle counts in the dense Erdős-Rényi random graphs $G_{m}\sim
G(n,m)$:

$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mathbb{E}\left[N_{\triangle}(G_{m})\right]\right)\,=\,\begin{cases}\exp\left(-\Theta\left(\delta^{2}n^{3}\right)\right)&\text{if
$n^{-3/2}\ll\delta\ll n^{-1}$}\\\
\exp\left(-\Theta(\delta^{2/3}n^{2})\right)&\text{if $n^{-3/4}\ll\delta\ll
1$.}\end{cases}\phantom{\Bigg{|}}$

Neeman, Radin and Sadun [NRS22] also conjectured that the probability should
be of the form $\exp\left(-\Theta\left(\delta^{2}n^{3}\right)\right)$ in the
“missing interval” $n^{-1}\ll\delta\ll n^{-3/4}$. We prove this conjecture.

As part of our proof we also prove that some random graph statistics, related
to degrees and codegrees, are normally distributed with high probability.

José received postdoctoral grants from the Brazilian funding agencies CNPq
(Proc. 153903/2018-0), FAPERJ (Proc. E-26/202.011/2020) and FAPESP (Proc.
2020/10796-0), Gabriel is supported by a CAPES PhD scholarship and Simon was
partially supported by FAPERJ (Proc. 201.194/2022) and by CNPq (Proc.
307521/2019-2).

##  1\. Introduction

The distribution and tail behaviour of subgraph counts, and especially the
triangle count, has been a very active area of research in recent decades.
Subgraph counts are very natural examples of sums of dependent random
variables.

In particular, a great many results have been proved regarding small
deviations (of the order of the standard deviation) beginning with Ruciński
[Ru88], see also [BKR, JanRSA, Jan, JN, KRT, RR, Rol]. There have also been
many results which focus on large deviations (of the order of the mean)
including the seminal articles of Vu [Vu] and Janson and Ruciński [JR] in the
early 2000s, and continuing with Chatterjee and Varadhan [CV] who related
these deviations to solutions of variational problems, which were resolved in
certain cases by Lubetzky and Zhao [LZ] and Zhao [Z]. The survey of Chatterjee
[Chat] and the references therein give a detailed overview. Further
developments related to these techniques may be found in [Au, CD20, El]. A
major breakthrough by Harel, Mousset and Samotij [HMS2019] essentially
resolved the large deviation upper tail problem for triangles.

There has also been some interest in deviations of intermediate value, which
we call moderate deviations. These deviations are considered in the $G(n,p)$
model in [DE, DE2, FGN]. It is argued by the third author, together with
Goldschmidt and Scott [GGS] that, for many moderate deviation problems, the
$G(n,m)$ model is more appropriate as it is possible to study finer causes of
deviations, and that, in any case, one may deduce results for $G(n,p)$ by a
simple conditioning argument. See also [AGG], which extends these results to
sparser random graphs.

Let us now consider the model $G_{m}\sim G(n,m)$, in which $G_{m}$ is selected
uniformly from graphs with $n$ vertices and $m$ edges. Let $N_{\triangle}(G)$
be the number of triangles in a graph $G$. The majority of results previously
mentioned have focussed on the upper tail, whereas we shall focus on the lower
tail. That is, we consider the question of how likely it is that a random
graph has many _fewer_ triangles than expected. Let us begin by stating the
main results of [GGS] and [NRS22] in this context.

Let $p\in(0,1)$ be a constant, and suppose that the sequence $m=m_{n}$ is such
that111We shall omit floor signs and assume certain quantities are integers.
It will be clear that the results and proofs are robust to a $\pm 1$ additive
error, which corresponds to $\pm O(n^{-2})$ error in terms of the density $p$.
$m=p\binom{n}{2}$. That is, the random graph $G_{m}\sim G(n,m)$ has density
$p$. Let us also abbreviate $\mathbb{E}\left[N_{\triangle}(G_{m})\right]$ to
$\mu_{n,m}$. Note $\mu_{n,m}=p^{3}\binom{n}{3}$. The main result of [GGS] in
this context states that222In verifying that this corresponds to the result of
[GGS], note that triangles are counted with multiplicity in that article.

$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mu_{n,m}\right)\,=\,\exp\left(\frac{-(1+o(1))\delta^{2}\mu_{n,m}}{2(1-p)^{2}(1+2p)}\right)\,$

provided $n^{-3/2}\ll\delta\ll n^{-1}$. This shows that the “normal tail”
extends far beyond deviations of the order of the standard deviation,
$\Theta(n^{3/2})$ (for which $\delta=\Theta(n^{-3/2})$).

Neeman, Radin and Sadun [NRS22] used techniques associated with the spectrum
of the random graph to prove the following results. Writing $\gamma_{p}$ for
$\log(p/(1-p))/2(2p-1)$ for $p>1/2$ and $\gamma_{1/2}=1$, then

$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mu_{n,m}\right)\,=\,\exp\left(-(1+o(1))\gamma_{p}\delta^{2/3}p^{2}n^{2}\right)\,$

for $p\in[1/2,1)$ and $n^{-3/4}\ll p\ll 1$. On the other hand, for
$p\in(0,1/2)$ they prove that the asymptotic rate lies in the (closed)
interval from $\gamma_{p}\delta^{2/3}p^{2}n^{2}$ to
$\delta^{2/3}p^{2}n^{2}/2p(1-p)$.

More crudely, if we ignore the exact constants, we may summerise the results
of the two articles as follows. Fix $p\in(0,1)$, and let $G_{m}\sim G(n,m)$
for $m=p\binom{n}{2}$ then

$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mu_{n,m}\right)\,=\,\begin{cases}\exp\left(-\Theta\left(\delta^{2}n^{3}\right)\right)&\text{if
$n^{-3/2}\ll\delta\ll n^{-1}$}\\\
\exp\left(-\Theta(\delta^{2/3}n^{2})\right)&\text{if $n^{-3/4}\ll\delta\ll
1$\, .}\end{cases}\phantom{\Bigg{|}}$

In the “missing regime” where $n^{-1}\ll\delta\ll n^{-3/4}$ Neeman, Radin and
Sadun [NRS22] proved an upper bound of the form
$\exp\left(-\Omega\left(\delta^{2}n^{3}\right)\right)$ and a lower bound of
the form $\exp\left(-O(\delta^{2/3}n^{2})\right)$, see the discussion in
Section 3.1 of [NRS22]. These bounds are shown as the green and red lines in
Figure 1 respectively.

$\vspace{1mm}-1.5$$-1$$-0.5$$0$$0$$0.5$$1$$1.5$$2$$\theta$$\gamma$ Figure 1.
In this figure, the $\theta$-axis parameterises $\delta$ as
$\delta=n^{\theta}$, and the $\gamma$-axis parameterises the log-probability
$-\log{\mathbb{P}\left(N_{\triangle}(G_{m})<(1-\delta)\mu_{n,m}\right)}=n^{\gamma}$.
The black lines show the results proved in [GGS] and [NRS22] respectively. The
green and red lines show the upper and lower bounds of [NRS22] in the interval
$-1\leqslant\theta\leqslant-3/4$. Our main theorem shows that the log-
probability follows the green line in this interval.

Furthermore, they conjectured that the correct order in this range is
$\delta^{2}n^{3}$. Our main result confirms that this is indeed the case.

######  Theorem 1.1.

Let $\lambda\in(0,1)$. There exists a constant $C>0$ such that the following
holds. Let $\delta=\delta_{n}$ be such that $n^{-1}\leqslant\delta\leqslant
C^{-1}n^{-3/4}$ and let $m=m_{n}$ be such that $\lambda\binom{n}{2}\leqslant
m\leqslant(1-\lambda)\binom{n}{2}$, then

$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mu_{n,m}\right)\,\geqslant\,\exp(-C\delta^{2}n^{3})\,.$

There is a sense in which our result is natural, as it shows that the log
probability continues along its existing path up until
$\delta=\Theta(n^{-3/4})$, as shown in Figure 1. However, this was not at all
a forgone conclusion. In a surprising result, Neeman, Radin and Sadun [NRS22]
showed that for $C_{5}$, and longer odd cycles, their results hold down to
$\delta=\Theta(n^{-1})$, at which point there is a jump discontinuity in the
log-probability.

The behaviour for the even cycle $C_{4}$ is more extreme, as a well known
calculation using the Cauchy-Schwarz inequality shows that a deviation below
$(1-\delta)\mu$ is _impossible_ for some $\delta=\Theta(n^{-1})$. The
situation for other bipartite graphs may well be similar, and is related to
Siderenko’s conjecture [Sid].

On the other hand, large deviations are always possible for counts of non-
bipartite graphs $H$, since there is always some probability that $G_{m}$
contains a linear sized complete bipartite subgraph, which causes there to be
fewer than $(1-\delta)\mu$ copies of $H$ for some constant $\delta>0$.

The problem of lower tail moderate deviations, in the range across the range
$n^{-1}\ll\delta\ll 1$, is wide open. And it would be of interest to determine
the behaviour of lower tails of subgraph counts in general across this range.
Related to the “continuity” question, we make the following conjecture – there
is a “discontinuity” in the lower tail log probability for the graph $H$,
around $\delta=n^{-1}$, if and only if $H$ is triangle-free. Let $N_{H}(G)$
denote the number of copies of $H$ contained in $G$. Here is a more formal
statement.

######  Conjecture 1.2.

Let $p\in(0,1)$ be a constant, and let $m=p\binom{n}{2}$. Let
$\mu_{H}=\mathbb{E}\left[N_{H}(G_{m})\right]$. Then the function

$\beta\,\,\mapsto\,\,\frac{\log{\log{\mathbb{P}\left(N_{H}(G_{m})\,<\,(1-n^{\beta})\mu_{H}\right)^{-1}}}}{\log{n}}$

has a jump discontinuity at $\beta=-1$, if and only if $H$ is triangle-free.

It may well be of interest to investigate similar lower tail problems for
other discrete combinatorial problems, such as arithmetic progressions in
uniform random sets. Some results may be found in [Irreg] and [Reg] for this
model. We remark that lower tail probabilities are often much larger in the
Binomial random model, see [JW].

In the following section we give an overview of the proof, and a summary of
the layout of the article.

##  2\. An overview of the proof

Our approach starts with the naively simple idea that fewer triangles are
created if many of the edges added are in few triangles (i.e., have small
codegree). However, it turns out to be surprisingly difficult to make this
approach rigorous, and so we shall consider (and condition on) a slightly
different event.

We now attempt to explain intuitively how and why our proof works. We also
introduce notation that will be used throughout the article. Set
$N:=\binom{n}{2}$. We shall use the notation $\pm K$ to denote an error of up
to $|K|$, so that $a=b\pm K$ means $a\in[b-K,b+K]$.

Our objective is to prove a lower bound on the probability,

$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mu_{n,m}\right)\,,$

that $G_{m}$ contains many fewer triangles than expected, where
$n^{-1}\leqslant\delta\leqslant C^{-1}n^{-3/4}$. We achieve this by defining
an event, which is not too rare, and on which the conditional expectation of
the triangle count is much smaller. Given an event $E$ such that

$\mathbb{E}\left[N_{\triangle}(G_{m})\,|\,E\right]\,\leqslant\,(1-2\delta)\mu_{n,m}$

It follows from Markov’s inequality that

$\mathbb{P}\left(N_{\triangle}(G_{m})\,\geqslant\,(1-\delta)\mu_{n,m}|E\right)\,\leqslant\,\frac{(1-2\delta)\mu_{n,m}}{(1-\delta)\mu_{n,m}}\,\leqslant\,1-n^{-1}\,.$

Considering the complementary event, we have
$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mu_{n,m}|E\right)\geqslant
n^{-1}$, from which it follows that

$\mathbb{P}\left(N_{\triangle}(G_{m})\,<\,(1-\delta)\mu_{n,m}\right)\geqslant
n^{-1}\mathbb{P}\left(E\right)\,.$

In summary, to prove Theorem 1.1 it suffices to prove the following
proposition.

######  Proposition 2.1.

Let $\lambda\in(0,1)$. There exists a constant $C>0$ such that the following
holds. Let $\delta=\delta_{n}$ be such that $n^{-1}\leqslant\delta\leqslant
C^{-1}n^{-3/4}$ and let $m=m_{n}$ be such that $\lambda N\leqslant
m\leqslant(1-\lambda)N$, then there exists an event $E$ such that

  1. (i)

$\mathbb{P}\left(E\right)\,\geqslant\,\exp(-C\delta^{2}n^{3})$ and

  2. (ii)

$\mathbb{E}\left[N_{\triangle}(G_{m})|E\right]\,\leqslant\,(1-2\delta)\mu_{n,m}$.

What kind of event $E$ might “cause” there to be fewer triangles?

We may clearly define $G_{m}$ by running the Erdős-Rényi random graph process,
which starts with an empty graph on $n$ vertices and to which we add an edge
at each step. It is easy to see that $G_{m}$ is the $m$th graph in this
process.

Here is a first attempt at defining such an event $E$. Run the process for
some time $m_{0}$, a little smaller than $m$, and let $G_{0}$ be the current
graph (with $m_{0}$ edges). Let $H$ be the graph which represents the non-
edges of $G_{0}$ with relatively small codegree. Now, a good way to create
fewer triangles, in the remainder of the process, would be to include in
$G\setminus G_{0}$ more pairs from $H$ than expected. Indeed, pairs with
smaller codegree create fewer triangles! This suggests taking $E$ to be the
event that the $e(G\cap H)$ is significantly larger than its mean.

However, when calculating the conditional expectation
$\mathbb{E}\left[N_{\triangle}(G_{m})|E\right]$ we must consider not only the
triangles with two edges in $G_{0}$ and one “new” edge, but also the triangles
with two or three “new” edges. The conditional expectations of these latter
two turn out to be challenging to calculate.

In fact, the calculations become easier if the graph (in the role of the graph
$H$ above) is close to regular. For this reason we turn to a new parameter,
related to codegree, which we call _synergy_.

######  Definition 2.2.

For $p\in(0,1)$, the _p-synergy_ of the vertices $u$ and $w$ in a graph $G$,
is

$S^{p}_{G}(u,w)\,:=\,d_{G}(u,w)-pd_{G}(u)-pd_{G}(w)+p^{2}(n-2)\,.$

If $p$ is omitted from the notation, as in $S_{G}(u,w)$, then take $p=e(G)/N$.

If $G$ is clear from context then it too may be omitted, as in $S(u,w)$.

Our approach will essentially be as described above, except using synergies
instead of codegrees. The reader will note that synergies are essentially
recentered versions of codegrees. This recentering is useful for some
technical reasons. A key facet of the article, see Section 3, is to show that
the sequence of synergies $S(u,w)$ over the non-neighbours, $w\in
V(G)\setminus N_{G_{0}}(u)$, of a given vertex $u$, is, with very high
probability, close to normally distributed.

What then is our new attempt at defining the event $E$?

As before we first run the process for $m_{0}$ steps to reveal a graph $G_{0}$
(with $m_{0}$ edges). We then let $f_{1},\dots f_{N-m_{0}}$ be all the non-
edges of $G_{0}$ in non-decreasing order of synergy $S(u,w)$. We may define

$F_{-}\,:=\,\left\\{f_{i}:i\in\left\\{1,\dots,\frac{N-m_{0}}{2}\right\\}\right\\}\,,$

that is $F_{-}$ is a graph consisting of the half333We shall always take
$m_{0}$ such that $N-m_{0}$ is even. of non-edges of $G_{0}$ with smaller
synergy. Again it is true that taking pairs of $F_{-}$ as edges will tend to
create fewer triangles. For this reason we may want to take $E$ to be the
event that $e(G_{1}\cap F_{-})$ is much larger than its expected value, where
$G_{1}=G_{m}\setminus G_{0}$ is the graph of edges added in the remainder of
the process.

This is essentially the event $E$ we shall take. For technical reasons we
shall

  1. (i)

find it useful to include in $E$ some basic quasirandomness properties of the
first graph $G_{0}$, and

  2. (ii)

use a parameter $\alpha$, so that the event is actually $E_{\alpha}$, for some
$\alpha>0$.

We now describe the layout of the article. In Section 3, we prove properties
about synergies of pairs of vertices. In Section 4, we prove important results
about the graph $F_{-}$, and about the connection between synergies and
codegrees. In Section 5, we first define an event $E_{0}$ which encodes the
basic quasiradnomness properties we require of $G_{0}$ and then we define the
events $E_{\alpha}$. We also prove a lower bound on the probability of
$E_{\alpha}$, which corresponds to part (i) of Proposition 2.1.

Finally, in Section 6, we show that conditioning on the event $E_{\alpha}$ has
the correct effect on the expected number of triangles. Doing so we complete
the proof of Proposition 2.1, and therefore complete the proof of Theorem 1.1.
We remark that the main challenge in Section 6 is to control the influence of
triangles with two or three “new” edges, i.e., two or three edges in $G_{1}$.
In some sense our control of their influence is just about good enough, and so
to reduce their influence by a constant factor we take $m_{0}=(1-\eta)m$ and
$m_{1}:=m-m_{0}=\eta m$, where we shall choose the constant $\eta>0$ to be
sufficiently small.

##  3\. The Synergies are normally normal

In this section we prove that, for each vertex $u$, it is very likely that the
sequence of synergies $(S_{G_{0}}(u,w):w\in
V(G)\setminus(N_{G_{0}}(u)\cup\\{u\\}))$ is close to normally distributed.

Given a vector $\textbf{x}=(x_{1},\dots,x_{k})$ we define

$F_{\textbf{x}}(t)\,:=\,\frac{|\\{i:x_{i}\leqslant t\\}|}{k}\,,$

which may be thought of as a distribution function associated with the vector
x. In this context it is natural to consider the distance between this
distribution and the distribution function $\Phi$ of the standard normal. For
each $t\in\mathbb{R}$ we may set

$d_{t}(\textbf{x},\Phi)\,:=\,\left|F_{\textbf{x}}(t)-\Phi(t)\right|$

and

$d(\textbf{x},\Phi)\,:=\,\sup\\{d_{t}(\textbf{x},\Phi)\,:\,t\in\mathbb{R}\\}\,.$

In light of these definitions we say x is $\varepsilon$-_close_ to normal if
$d(\textbf{x},\Phi)\leqslant\varepsilon$, and $\varepsilon$-_far_ from normal
if $d(\textbf{x},\Phi)>\varepsilon$.

We shall only consider synergies of pairs $u,w$ which are non-neighbours. Note
that $\mathbb{E}\left[S_{G_{p}}^{p}(u,w)\mid uw\not\in E(G_{p})\right]=0$,
where $G_{p}\sim G(n,p)$. Let us also observe the value of the variance

$\sigma_{p}^{2}\,:=\,\textup{Var}\big{(}S_{G_{p}}^{p}(u,w)\mid uw\not\in
E(G_{p})\big{)}\,=\,p^{2}(1-p)^{2}(n-2)\,,$ (3.1)

see the appendix for a proof of this statement. We may now introduce the
normalised version of synergy:

$\tilde{S}^{p}(u,w)\,:=\,\frac{S^{p}(u,w)}{\sigma_{p}}\,.$

Again, we may also write $\tilde{S}_{G}^{p}(u,w)$ to clarify which graph is
considered. If $p$ is not specified, as in $\tilde{S}(u,w)$ or
$\tilde{S}_{G}(u,w)$, then the normalisation444In fact, if $G\sim G(n,m)$ then
this normalisation is in some sense “incorrect” as we are using the mean and
standard deviation associated with the $G(n,p)$ model. However, as these
parameters differ by so little, between the two models, the same normalisation
may be used, and this simplifies comparisons between the models. uses
$\sigma_{p}$ where $p=e(G)/N$.

Now we can state the main theorem of this section. Given a vertex $u$ of a
graph $G$, let

$\mathcal{S}^{p}_{G}(u)\,:=\,\big{(}\tilde{S}^{p}_{G}(u,w)\,:\,w\in
V(G)\setminus(N(u)\cup\\{u\\})\big{)}\,.$

and

$\mathcal{S}_{G}(u)\,:=\,\big{(}\tilde{S}_{G}(u,w)\,:\,w\in
V(G)\setminus(N(u)\cup\\{u\\})\big{)}\,.\phantom{\Big{|}}$

That is, $\mathcal{S}^{p}_{G}(u)$ and $\mathcal{S}_{G}(u)$ are sequences of
(normalised) synergies of pairs $uw$ where $w$ varies over non-neighbours of
$u$ in $G$.

######  Proposition 3.1.

Let $\lambda>0$, let $0<\beta<1/4$ and let $\varepsilon=n^{-\beta}$. Let
$G_{m}\sim G(n,m)$, where $\lambda N\leqslant m\leqslant(1-\lambda)N$. Then,
for each vertex $u\in V(G_{m})$,

$\mathbb{P}\left(\mathcal{S}_{G_{m}}(u)\,\text{is }\varepsilon\text{-far from
normal}\right)\,\leqslant\,\exp(-n^{1/2-2\beta-o(1)})\,=\,\exp(-n^{\Omega(1)})\,.$

We shall begin by showing that this result follows from the analogous
statement for $G\sim G(n,p)$.

######  Proposition 3.2.

Let $\lambda>0$ and let $p\in[\lambda,1-\lambda]\subseteq(0,1)$. Let
$0<\beta<1/4$ and let $\varepsilon=n^{-\beta}$. Let $G_{p}\sim G(n,p)$. Then,
for each vertex $u\in V(G_{m})$,

$\mathbb{P}\left(\mathcal{S}^{p}_{G_{p}}(u)\,\text{is }\varepsilon\text{-far
from
normal}\right)\,\leqslant\,\exp(-n^{1/2-2\beta-o(1)})\,=\,\exp(-n^{\Omega(1)})\,.$

######  Remark.

It may well be possible to prove that $\mathcal{S}^{p}_{G_{p}}(u)$ is
$\varepsilon$-close to normal for smaller values of $\varepsilon$, perhaps as
small as $O(n^{-1/2})$, by using properties of the relative synergy
$S^{p}(u,w|I)$ (defined below) and the difference $S^{p}(u,w)-S^{p}(u,w|I)$
discussed in Claim 2 of the proof of Proposition 3.2.

The advantage of the $G(n,p)$ statement is that $G_{p}\sim G(n,p)$ has more
independence. Let us first observe that Proposition 3.1 follows from
Proposition 3.2.

###### Proof of Proposition 3.1.

Given $m\in[\lambda N,(1-\lambda)N]$, set $p:=m/N\in[\lambda,1-\lambda]$. We
write $\mathbb{P}_{p}$ and $\mathbb{P}_{m}$ for the probability measures
associated with $G\sim G(n,p)$ and $G\sim G(n,m)$ respectively. As there is
probability at least $n^{-2}$ that $G_{p}$ has $m$ edges, and such a graph is
distributed as $G(n,m)$, we have, for any event $E$ of graphs with $m$ edges:

$\mathbb{P}_{p}(E)\,\geqslant\,n^{-2}\mathbb{P}_{m}(E)\,.$

Using this inequality and Proposition 3.2, we have that

$\displaystyle\mathbb{P}\left(\mathcal{S}_{G_{m}}(u)\,\text{is
}\varepsilon\text{-far from normal}\right)\,$
$\displaystyle=\,\mathbb{P}_{m}(\mathcal{S}_{G}(u)\,\text{is
}\varepsilon\text{-far from normal})\phantom{\big{|}}$
$\displaystyle=\,\mathbb{P}_{m}(\mathcal{S}^{p}_{G}(u)\,\text{is
}\varepsilon\text{-far from normal})\phantom{\big{|}}$
$\displaystyle\leqslant\,n^{2}\mathbb{P}_{p}(\mathcal{S}^{p}_{G}(u)\,\text{is
}\varepsilon\text{-far from normal})\phantom{\big{|}}$
$\displaystyle\leqslant\,n^{2}\exp(-n^{1/2-2\beta-o(1)})\,.\phantom{\big{|}}$

As $n^{2}$ is of the form $\exp(n^{o(1)})$, this gives the required bound. ∎

We now turn to the task of proving Proposition 3.2. We must prove that, with
very high probability, the vector $\mathcal{S}^{p}_{G}(u)$ is close to normal.
For the remainder of the section $G\sim G(n,p)$.

The main challenge is that, even in $G(n,p)$, the (normalised) synergies
$\tilde{S}^{p}_{G}(u,w)$, which are the entries of $\mathcal{S}^{p}_{G}(u)$,
are not independent. Our task would be significantly easier if they were
independent, see Lemma 3.3, or even if they could be closely approximated by a
sequence of independent random variables.

While we are not able to approximate the whole sequence
$\mathcal{S}^{p}_{G}(u)$ by a sequence of independent random variables, we are
able to do so if we first restrict to a subsequence – a small random sample of
the entries of $\mathcal{S}^{p}_{G}(u)$.

In Section 3.1, we prove a lemma (Lemma 3.3) about the case of a sequence of
independent random variables. In Section 3.2, we prove a lemma (Lemma 3.6)
which implies that a sampling can be used to control the whole. Finally, we
show in Section 3.3 that these results imply that $\mathcal{S}^{p}_{G}(u)$ is
likely to be close to normal, proving Proposition 3.2.

We remark that synergies are not really so complex as random variables,
especially after we reveal one of the neighbourhoods. This is illustrated in
Figure 2.

$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{u}$$\textstyle{w}$

$\textstyle{\bullet}$$\textstyle{-p}$$\textstyle{1-p}$$\textstyle{\bullet}$
Figure 2. In this figure we illustrate the fact that, conditioned on the
neighbourhood of $u$, $N_{G_{p}}(u)$, each edge from $w$ adds $1-p$ to the
synergy $S_{G_{p}}^{p}(u,w)$ if the other end is in $N_{G_{p}}(u)$ and $-p$ if
not.

###  3.1. Sequences of iid random variables

The definition of distance from normal applies even more naturally to random
variables. Let $F$ be the distribution function of a random variable $X$. Then
we may define

$d_{t}(X,\Phi)\,:=\,\left|F(t)-\Phi(t)\right|$

and

$d(X,\Phi)\,:=\,\sup\\{d_{t}(\textbf{x},\Phi)\,:\,t\in\mathbb{R}\\}\,.\phantom{\big{|}}$

In fact, this is known as the Kolmogorov distance between the distributions.

######  Lemma 3.3.

Let $\varepsilon>0$ and $k\geqslant 1$. Let $X$ be a random variable with
$d(X,\Phi)\leqslant\varepsilon$. Let $\mathbf{X}=(X_{1},\dots,X_{k})$ be a
sequence of iid copies of $X$. Then

$\mathbb{P}\left(\mathbf{X}\text{ is }3\varepsilon\text{-far from
normal}\right)\,\leqslant\,2\varepsilon^{-1}\,\exp\left(\frac{-\varepsilon^{2}k}{2}\right)\,.$

###### Proof.

We first prove for a fixed $t\in\mathbb{R}$ that

$\mathbb{P}\left(d_{t}(\mathbf{X},\Phi)\,>\,2\varepsilon\right)\,\leqslant\,2\exp\left(\frac{-\varepsilon^{2}k}{2}\right)\,.$
(3.2)

We then deduce the lemma by a simple $\varepsilon$-net argument.

Fix $t\in\mathbb{R}$. Let $p(t):=\mathbb{P}\left(X\leqslant t\right)$. As
$d(X,\Phi)\leqslant\varepsilon$, we have $|p(t)-\Phi(t)|\leqslant\varepsilon$.

Let $Y:=|\\{i:X_{i}\leqslant t\\}|$. Note that $Y\sim\mathbf{Bin}(k,p(t))$ and
that $\mathbb{E}\left[Y\right]=kp(t)$, so that
$|\mathbb{E}\left[Y\right]-k\Phi(t)|\leqslant\varepsilon k$. We now have that

$\mathbb{P}\left(d_{t}(\mathbf{X},\Phi)\,>\,2\varepsilon\right)\,=\,\mathbb{P}\left(|Y-k\Phi(t)|>2\varepsilon
k\right)\,\leqslant\,\mathbb{P}\left(|Y-\mathbb{E}\left[Y\right]|>\varepsilon
k\right)\,.$

By applying the Chernoff bound for the lower tail to both $Y$ and
$k-Y\sim\mathbf{Bin}(k,1-p(t))$, we obtain that

$\mathbb{P}\left(|Y-\mathbb{E}\left[Y\right]|>\varepsilon
k\right)\,\leqslant\,2\exp\left(\frac{-\varepsilon^{2}k}{2}\right)\,,$

as claimed.

We now proceed to the $\varepsilon$-net argument. For each
$j=1,\dots,\lfloor\varepsilon^{-1}\rfloor$, let
$t_{j}=\Phi^{-1}(j\varepsilon)$. We also extend the definition to
$t_{0}=-\infty$ and $t_{\lfloor\varepsilon^{-1}\rfloor+1}=\infty$. In a slight
abuse of notation we extend our definition of $d_{t}(\mathbf{X},\Phi)$ to
include $d_{-\infty}(\mathbf{X},\Phi)=d_{\infty}(\mathbf{X},\Phi)=0$ for any
real vector $\mathbf{X}$.

It now follows by an easy monotonicity argument that for $t\in(t_{j-1},t_{j}]$
we have

$\displaystyle\mathbb{P}_{i\in I}\big{(}X_{i}\leqslant t\big{)}\,-\,\Phi(t)\,$
$\displaystyle\leqslant\,\mathbb{P}_{i\in I}\big{(}X_{i}\leqslant
t_{j}\big{)}\,-\,\Phi(t_{j-1})$
$\displaystyle\leqslant\,d_{t_{j}}(\mathbf{X},\Phi)\,+\,\varepsilon\,.$

By an essentially identical argument

$\Phi(t)\,-\,\mathbb{P}_{i\in I}\big{(}X_{i}\leqslant
t\big{)}\,\leqslant\,d_{t_{j-1}}(\mathbf{X},\Phi)\,+\,\varepsilon\,.$

It follows that

$d(\mathbf{X},\Phi)\,\leqslant\,\max_{j}d_{t_{j}}(\mathbf{X},\Phi)\,+\,\varepsilon\,.$
(3.3)

In other words, if we accept losing an additive term $\varepsilon$, we only
need to consider the distance $d_{t}(\mathbf{X},\Phi)$ at the finitely many
points $t=t_{j}$ for $j=1,\dots,\lfloor\varepsilon^{-1}\rfloor$.

We may now complete the proof, as, if $\mathbf{X}$ is $3\varepsilon$-far from
normal, then by (3.3), we have that $d_{t}(\mathbf{X},\Phi)\,>\,2\varepsilon$
for some $t\in\\{t_{j}:j=1,\dots,\lfloor\varepsilon^{-1}\rfloor\\}$. By (3.2)
and a union bound, this has probability at most

$\varepsilon^{-1}\,\cdot\,2\exp\left(\frac{-\varepsilon^{2}k}{2}\right)\,,$

as required. ∎

The case where each $X_{i}$ is itself obtained as a weighted sum of iid
Bernoulli random variables will be particularly relevant. Let
$(a_{i})_{i=1}^{\ell}$ be a sequence of real numbers and let
$X:=\sum_{i=1}^{\ell}a_{i}\xi_{i}$, where the random variables $\xi_{i}$ are
iid with distribution Bernoulli $\textrm{Bern}(p)$. Let
$\tilde{X}:=(X-\mu_{X})/\sigma_{X}$, be the renormalisation of $X$, using
$\mu_{X}=p\sum_{i}a_{i}$ and $\sigma_{X}^{2}\,=\,p(1-p)\sum_{i}a_{i}^{2}$. By
the Berry-Esseen inequality [Berry, Esseen] (using, for example, Theorem 1 of
[Berry], with $\Lambda=\max\\{|a_{i}|\\}$ and $\sigma=\sigma_{X}$) we have
that

$d(\tilde{X},\Phi)\,\leqslant\,\frac{2\max\\{|a_{i}|\\}}{\sigma_{X}}$ (3.4)

In particular, as a corollary of the above lemma we have.

######  Corollary 3.4.

Let $(a_{i})_{i=1}^{\ell}$ be a sequence of real numbers, let $p\in(0,1)$ and
set $\mu=p\sum_{i}a_{i}$ and $\sigma^{2}=p(1-p)\sum_{i}a_{i}^{2}$. For
$j=1,\dots,k$, let us define $X_{j}=\sum_{i}a_{i}\xi_{i,j}$ where the
$\xi_{i,j}$ are iid $\textrm{Bern}(p)$ random variables. And let
$\tilde{X}_{j}=(X_{j}-\mu)/\sigma$ for each $j=1,\dots,k$. Let
$\mathbf{X}=(\tilde{X}_{1},\dots,\tilde{X}_{k})$. Then for every
$\varepsilon\geqslant 2\max\\{|a_{i}|\\}\sigma^{-1}$, we have

$\mathbb{P}\big{(}\mathbf{X}\text{ is }3\varepsilon\text{-far from
normal}\big{)}\,\leqslant\,2\varepsilon^{-1}\,\exp\left(\frac{-\varepsilon^{2}k}{2}\right).$

###### Proof.

By (3.4), each random variable $\tilde{X}_{j}$ is $\varepsilon$-close to
normal, as $\varepsilon\geqslant 2\max\\{|a_{i}|\\}\sigma^{-1}$. They are also
iid, and so the result follows from Lemma 3.3. ∎

For example, if $|a_{i}|\leqslant 1$ for all $i$, then putting
$\varepsilon=2\sigma^{-1}$, we would have

$\mathbb{P}\left(\mathbf{X}\text{ is }(6\sigma^{-1})\text{-far from
normal}\right)\,\leqslant\,\sigma\,\exp\left(\frac{-2k}{\sigma^{2}}\right)\,.$

As we have discussed, the entries in the vector of synergies
$\mathcal{S}^{p}_{G}(u)$ are _not_ independent, and so we cannot directly
deduce Proposition 3.2 from Lemma 3.3. Instead, we fix a subset $I$ of the
non-neighbours of $u$, and consider the _relative synergies_ defined by

$S_{G}^{p}(u,w|I)\,:=\,d_{G}(u,w)\,-\,p|N_{G}(w)\cap(V\setminus
I)|\,-\,pd_{G[V\setminus I]}(w)\,+\,p^{2}(n-|I|-1)$

for $w\in I$. In some sense, this relative synergy contains “less information”
than the original synergy $S_{G}^{p}(u,w)$, as we no longer ask how many
neighbours $w$ has in $I$, instead replacing this value with its expected
value, $p(|I|-1)$. On the other hand, relative synergies are independent!

######  Lemma 3.5.

Let $u\in G$, let $I\subseteq V(G)\setminus(N_{G}(u)\cup\\{u\\})$ and let
$v,w\in I$. Then $S^{p}(u,v|I)$ and $S^{p}(u,w|I)$ are conditionally
independent and identically distributed, given $N_{G}(u)$.

###### Proof.

Since each edge of $G$ is in it independently from the other edges, for any
$x,y\in\mathbb{R}$, the events $\big{[}S^{p}(u,w|I)\leqslant x\big{]}$ and
$\big{[}S^{p}(u,v|I)\leqslant y\big{]}$ are independent, since they depend on
disjoint sets of edges (the edge $vw$ is not considered by the relative
synergy). It is clear from the definition that they are identically
distributed. ∎

###  3.2. Sampling

Given a vector $\textbf{x}:=(x_{i}:i\in I)$ and a subset $J\subseteq I$, we
write $\textbf{x}_{J}:=(x_{j}:j\in J)$ for the vector restricted to this
subset of the indices. The following lemma states that if a vector is far from
normal then the sample of it is also likely to be far from normal555There is
nothing special about the normal distribution, but we state the result for
normal as this is the case we require. One could also prove stronger bounds of
course.

######  Lemma 3.6.

Let $\varepsilon>0$, let $1\leqslant k\leqslant K$ and suppose that
$\varepsilon^{2}k\geqslant 2$. Let $\textbf{x}:=(x_{1},\dots x_{K})$ be a
vector which is $2\varepsilon$-far from normal, and let $I\subseteq[K]$ be a
random subset chosen uniformly from $k$-element subsets of $[K]$. Then

$\mathbb{P}\big{(}\textbf{x}_{I}\text{ is }\varepsilon\text{-far from
normal}\big{)}\,\geqslant\,\frac{1}{2}\,.$

###### Proof.

Reordering, if necessary, we may assume that $\textbf{x}=(x_{1},\dots,x_{K})$
is non-decreasing. As $d(\textbf{x},\Phi)\geqslant 2\varepsilon$, it follows
that for some $t\in\mathbb{R}$ we have $d_{t}(\textbf{x},\Phi)\geqslant
2\varepsilon$. Let $\ell$ be maximal such that $x_{\ell}\leqslant t$. The
condition $d_{t}(\textbf{x},\Phi)\geqslant 2\varepsilon$ gives us that

$\big{|}\ell-\Phi(t)K\big{|}\,>\,2\varepsilon K\,.$ (3.5)

We now consider the vector $\textbf{x}_{I}$. Let $Y$ be the random variable
$|I\cap[\ell]|$. Note that $d_{t}(\textbf{x}_{I},\Phi)=|Y-\Phi(t)k|/k$, and so
the vector $\textbf{x}_{I}$ is certainly $\varepsilon$-far from normal in the
case

$|Y-\Phi(t)k|\,\geqslant\,\varepsilon k\,.$ (3.6)

We note that $Y$ is distributed as a hypergeometric random variable,
$Y\sim\textrm{Hyp}(K,\ell,k)$, which has expected value $\mu=\ell k/K$, and
so, by (3.5), we have $|\mu-\Phi(t)k|\geqslant 2\varepsilon k$. Now, the
probability $\textbf{x}_{I}$ is _not_ $\varepsilon$-far from normal is at most

$\mathbb{P}\left(|Y-\Phi(t)k|\,<\,\varepsilon
k\right)\,\leqslant\,\mathbb{P}\left(|Y-\mu|\,>\,\varepsilon k\right)\,.$

For hypergeometric random variables, the variance satisfies
$\sigma^{2}\leqslant\mu\leqslant\ell k/K$. And so, it follows from Chebychev’s
inequality that this probability is at most

$\frac{\ell
k}{\varepsilon^{2}k^{2}K}\,\leqslant\,\frac{1}{\varepsilon^{2}k}\,\leqslant\,\frac{1}{2}\,.$

∎

In particular, this may be applied to realisations of random vectors
$\mathbf{X}\in\mathbb{R}^{K}$. Doing so yields the following corollary.

######  Corollary 3.7.

Let $\varepsilon>0$, let $1\leqslant k\leqslant K$ and suppose that
$\varepsilon^{2}k\geqslant 2$. Let $\mathbf{X}\in\mathbb{R}^{K}$ be a random
vector, and let $I\subseteq[K]$ be a random subset chosen uniformly from
$k$-element subsets of $[K]$. Then

$\mathbb{P}(\mathbf{X}\text{ is }2\varepsilon\text{-far from
normal})\,\leqslant\,2\,\mathbb{P}(\mathbf{X}_{I}\text{ is
}\varepsilon\text{-far from normal})\,.$

###  3.3. Proof of Proposition 3.2

Recall that $G\sim G(n,p)$. We omit $G$ from degree and synergy notations for
the remainder of the section. We use the following notation

$D(u)\,:=\,d(u)-\mathbb{E}[d(u)]\,=\,d(u)-p(n-1)$

and

$D(u,w)\,:=\,d(u,w)-\mathbb{E}[d(u,w)]\,=\,d(u,w)-p^{2}(n-2)\,.$

Before giving the proof, let us explain why the sampling trick is really
necessary. Given a vertex $u$ and its neighbourhood $N(u)$, we can write

$S^{p}(u,w)\,+pd(u)\,-\,p^{2}(n-2)\,=\,d(u,w)\,-\,pd(w)\,=\,\sum_{v\in
V\setminus\\{u,w\\}}a_{v}\xi_{v}$ (3.7)

where each $\xi_{v}$ is an iid copy of $\textrm{Bern}(p)$ and $a_{v}=1_{v\in
N(u)}-p$ for all $v\in V(G)\setminus\\{u,w\\}$. We would like to apply
Corollary 3.4. The problem is that, if we set $X_{w}$ equals to the sum in
(3.7), then the sums do not use disjoint sets of iid Bernoulli random
variables as we vary over $w$. So the sampling idea will be vital.

###### Proof of Proposition 3.2.

Fix a vertex $u\in G$ and reveal the neighbourhood $N(u)$. Recall
$\varepsilon=n^{-\beta}$, where $\beta\in(0,1/4)$. Except with probability at
most $\exp(-n^{1/2-2\beta+o(1)})$, we have $|D(u)|\leqslant\varepsilon
n^{3/4}$, by Chernoff’s inequality. Therefore we shall assume
$|D(u)|\leqslant\varepsilon n^{3/4}$ throughout the proof.

Let $k=n^{1/2}$. Let $I$ be a uniformly chosen $k$-element subset of
$(N(u)\cup\\{u\\})^{c}$.

For each $w\in I$, consider the relative synergy

$S^{p}(u,w|I)\,:=\,d(u,w)\,-\,pd(u)\,-\,p\big{|}N(w)\cap(V\setminus
I)\big{|}\,+\,p^{2}(n-|I|-1)\,.$

By a calculation similar to (3.7) we have

$S^{p}(u,w|I)\,+\,pd(u)\,-\,p^{2}(n-|I|-1)\,=\,\sum_{v\in
V\setminus(I\cup\\{u\\})}a_{v}\xi_{wv}\,\,=:\,X_{w}\,,$

where $a_{wv}=1_{v\in N(u)}-p$. Furthermore, as $\xi_{wv}$ is exactly the
indicator function of the edge $wv$, the sequence $(\xi_{wv}:w\in I,v\in
V\setminus(I\cup\\{u\\}))$ is a family of iid $\textrm{Bern}(p)$ random
variables.

As $I$ is simply a set of a fixed size $|I|=k$, and all vertices of $I$ are
equivalent, the choice of $w$ and $I$ does not affect the expected value or
variance of the random variable $X_{w}$. Let us define

$\mu_{u}\,:=\,\mathbb{E}\left[X_{w}\mid
N(u)\right]\,=\,p\,\sum_{i}a_{i}\,\,=\,pd(u)\,-\,p^{2}(n-k-1)$

and

$\displaystyle\sigma^{2}_{u}\,:=\,\textup{Var}(X_{w}\mid N(u))\,$
$\displaystyle=\,p(1-p)\,\sum_{v}a_{v}^{2}$
$\displaystyle=\,p(1-p)^{3}d(u)\,+\,p^{3}(1-p)(n-k-d(u)-1)\,.\hskip
22.76219pt$ (3.8)

For each $w\in I$ define the renormalised random variable

$\tilde{X}_{w}\,:=\,\frac{X_{w}\,-\,\mu_{u}}{\sigma_{u}}\,.$

By Corollary 3.4 (applied with $\varepsilon/12$), there is probability at most
$24\varepsilon^{-1}\exp(-\varepsilon^{2}k/288)=\exp(-n^{1/2-2\beta+o(1)})$,
that the vector $\mathbf{X}=(\tilde{X}_{w}:w\in I)$ is $(\varepsilon/4)$-far
from normal.

We now hope to relate the vector of normalised synergies
$\mathcal{S}^{p}_{G}(u)$ to $\mathbf{X}$, which we shall suppose is
$(\varepsilon/4)$-close to normal. The following claims will be useful.

Claim I: $|\sigma_{p}-\sigma_{u}|=O(\varepsilon n^{1/4})$.

Proof of Claim: For the duration of the proof we let $q:=1-p$. By (3.1) and
(3.8), and writing $d(u)=p(n-1)+D(u)$, we have that

$\displaystyle\sigma^{2}_{p}\,-\,\sigma^{2}_{u}\,$
$\displaystyle=\,pq\Big{[}pq(n-2)\,-\,q^{2}d(u)\,-\,p^{2}(n-k-d(u)-1)\Big{]}\phantom{\bigg{|}}$
$\displaystyle=\,pq\Big{[}pq(n-2)\,-\,q^{2}(p(n-1)+D(u))\,-\,p^{2}(qn-
k-D(u)-q)\Big{]}\phantom{\bigg{|}}$
$\displaystyle=\,pq\Big{[}p^{2}(k+D(u))\,-\,q^{2}D(u)\Big{]}\,+\,O(1)\phantom{\bigg{|}}$
$\displaystyle=\,O(\varepsilon n^{3/4})\,\phantom{\big{|}},$

as $k=O(\varepsilon n^{3/4})$ and we are assuming $D(u)=O(\varepsilon
n^{3/4})$, as explained above.

The claim now follows from the difference of squares formula
$(\sigma_{p}-\sigma_{u})(\sigma_{p}+\sigma_{u})=\sigma_{p}^{2}-\sigma_{u}^{2}$,
as $\sigma_{p}=\Omega(n^{1/2})$.

Claim II Except with probability at most $\exp(-n^{1/2-2\beta+o(1)})$, we have
that

$|S^{p}(u,w)-S^{p}(u,w|I)|\,\leqslant\,\varepsilon\sigma_{p}/8$

for all $w\in I$.

Proof of Claim: Comparing the definitions we see that

$S^{p}(u,w)-S^{p}(u,w|I)\,=\,p^{2}(k-1)\,-\,p|N(w)\cap I|\,.$

As $p(k-1)$ is the mean of the random variable $|N(w)\cap
I|\sim\mathbf{Bin}(k-1,p)$ it is easily verified using Chernoff’s inequality
that

$\mathbb{P}\left(|S^{p}(u,w)-S^{p}(u,w|I)|\,>\,\frac{\varepsilon\sigma_{p}}{8}\right)\,\leqslant\,\exp(-\Omega(\varepsilon^{2}n/k))\,=\,\exp(-n^{1/2-2\beta+o(1)})\,.$

The claim now follows by a union bound over the $k=\exp(n^{o(1)})$ vertices
$w\in I$.

Claim III If $|\tilde{X}_{w}|\leqslant n^{1/8}$ then

$\big{|}\tilde{S}^{p}(u,w)\,-\,\tilde{X}_{w}\big{|}\,\leqslant\,\frac{\varepsilon}{4}$

provided $n$ is sufficiently large.

Proof of Claim: We begin by noting that $X_{w}-\mu_{u}=S^{p}(u,w|I)$, so that
$\tilde{X}_{w}=S^{p}(u,w|I)/\sigma_{u}$. Using Claim I, it follows that

$\displaystyle\tilde{S}^{p}(u,w)\,-\,\tilde{X}_{w}\,$
$\displaystyle=\,\frac{S^{p}(u,w)}{\sigma_{p}}\,-\,\frac{S^{p}(u,w|I)}{\sigma_{u}}$
$\displaystyle=\,\frac{S^{p}(u,w)-S^{p}(u,w|I)}{\sigma_{p}}\,\pm\,O(\varepsilon
n^{-1/4}\tilde{X}_{w})\,.$

Using the assumption on $\tilde{X}_{w}$, and Claim II, the absolute value of
this is at most $\varepsilon/8+O(\varepsilon n^{-1/8})$, which is at most
$\varepsilon/4$, for all sufficiently large $n$, as required.

As $\mathbf{X}=(\tilde{X}_{w}:w\in I)$ is $(\varepsilon/4)$-close to normal
and, by Claim III,
$\big{|}\tilde{S}^{p}(u,w)\,-\,\tilde{X}_{w}\big{|}\leqslant\varepsilon/4$
when $|\tilde{X}_{w}|\leqslant n^{1/8}$, the vector

$\big{(}\tilde{S}^{p}(u,w)\,:\,w\in I\big{)}$ (3.9)

is $(\varepsilon/2)$-close to normal666The values with absolute value greater
than $n^{1/8}$ may be ignored as there are at most $\varepsilon k/4+o(1)$ such
values in each tail.

Thus we have proved that, except with probability
$\exp(-n^{1/2-2\beta+o(1)})$, the vector (3.9) is $(\varepsilon/2)$-close to
normal.

Finally, we note that the vector (3.9) is simply a sample of $|I|=k$ uniform
random elements of
$\mathcal{S}^{p}_{G}(u)\,=\,\big{(}\tilde{S}^{p}_{G}(u,w)\,:\,w\in
V(G)\setminus(N(u)\cup\\{u\\})\big{)}$, and so, by Corollary 3.7, there is
most twice this probability, which is still $\exp(-n^{1/2-2\beta+o(1)})$, that
$\mathcal{S}^{p}_{G}(u)$ is $\varepsilon$-far from normal. ∎

##  4\. Relating Codegrees and Synergies

As we explained in the overview, our plan is to consider an event which biases
our selection towards edges with smaller synergy. The results of this section
relate synergies to codegrees, which is vital to our approach. We also prove
some properties of the graph $F_{-}$.

More concretely, our event will involve taking $(1+\alpha)/2$ proportion of
the remaining $m_{1}=m-m_{0}$ edges from $F_{-}$ rather than its complement
$F_{+}:=K_{n}\setminus(G_{0}\cup F_{-})$. One contribution to the final number
of triangles are those with two edges in $G_{0}$ and one in $G_{1}$.
Conditioned on this event this conditional expectation becomes

$\sum_{uv\in F_{-}}d_{G_{0}}(u,v)\frac{(1+\alpha)m_{1}}{N-m_{0}}+\sum_{uv\in
F_{+}}d_{G_{0}}(u,v)\frac{(1-\alpha)m_{1}}{N-m_{0}}\,.$

This clearly motivates are interest in the expression

$\sum_{uv\in F_{-}}d_{G_{0}}(u,v)\,-\,\sum_{uv\in F_{+}}d_{G_{0}}(u,v)\,.$

We now state the required result on this quantity. Let us fix for the
remainder of the article $\varepsilon:=n^{-1/5}$.

######  Proposition 4.1.

There exists $c>0$ such that the following holds. If $G_{0}$ is such that
$|d_{G_{0}}(u)-p_{0}n|\leqslant n^{1/2}\log n$ and $\mathcal{S}_{G_{0}}(u)$ is
$\varepsilon$-close to normal, for all vertices $u$, then

$\sum_{uv\in F_{-}}d_{G_{0}}(u,v)-\sum_{uv\in F_{+}}d_{G_{0}}(u,v)\leqslant-
cn^{5/2}.$

Assume, for the rest of this section, that for every $u\in V(G_{0})$ we have
$\mathcal{S}_{G_{0}}(u)$ is $\varepsilon$-close to normal. The next lemma
relates this quantity to an equivalent expression using codegrees, up to an
error term.

######  Lemma 4.2.

Let $D=max_{u}\\{|d_{G_{0}}(u)-p_{0}n|:u\in V(G_{0})\\}$. Then

$\begin{split}\sum_{uv\in F_{-}}d_{G_{0}}(u,v)-\sum_{uv\in
F_{+}}d_{G_{0}}(u,v)&\,=\,\sum_{uv\in F_{-}}S_{G_{0}}(u,v)-\sum_{uv\in
F_{+}}S_{G_{0}}(u,v)\pm 4p_{0}\varepsilon Dn^{2}.\\\ \end{split}$

We first require a lemma about the degrees of vertices in $F_{-}$.

######  Lemma 4.3.

For every vertex $u$ we have

$d_{F_{-}}(u)\,=\,\left(\frac{1}{2}\pm
2\varepsilon\right)(n-d_{G_{0}}(u)-1)\,.$

###### Proof.

We begin by noting that the normal density $\phi(t)$ satisfies
$\phi(t)\geqslant 1/3$ for all $|t|\leqslant 1/10$. So that, in particular,
$\Phi(3\varepsilon)\geqslant 1/2+\varepsilon$. Let $\lambda>0$ be such that
$\Phi(\lambda)=1/2+\varepsilon$. We have $\lambda\leqslant 3\varepsilon$.

Recall that $F_{-}$ consists of the pairs of $K_{n}\setminus G_{0}$ with
synergy $S_{G_{0}}(u,v)$ below the median. Let $\tilde{\mu}$ be the value of
this median.

As each $\mathcal{S}_{G_{0}}(u)$ is $\varepsilon$-close to normal, we have for
all vertices $u$, that at least

$(\Phi(\lambda)-\varepsilon)(n-d_{G_{0}}(u)-1)\,=\,\frac{1}{2}(n-d_{G_{0}}(u)-1)$

pairs $uv\in E(K_{n}\setminus G_{0})$ have
$S_{G_{0}}(u,v)\leqslant\lambda\sigma$. Summing over vertices $u$, it follows
that at least $(N-m_{0})/2$ pairs $uv\in E(K_{n}\setminus G_{0})$ have
$S_{G_{0}}(u,v)\leqslant\lambda\sigma$. In particular,
$\tilde{\mu}\leqslant\lambda\sigma$. And, by a similar argument,
$\tilde{\mu}\geqslant-\lambda\sigma$.

In particular, by monotonicity $\Phi(\tilde{\mu})=1/2\pm\varepsilon$.

As $\mathcal{S}_{G_{0}}(u)$ is $\varepsilon$-close to normal we have

$d_{F_{-}}(u)\,=\,(\Phi(\tilde{\mu})\pm\varepsilon)(n-d_{G_{0}}(u)-1)\,=\,\left(\frac{1}{2}\pm
2\varepsilon\right)(n-d_{G_{0}}(u)-1)\,.$

∎

We may now prove the previous lemma.

###### Proof of Lemma 4.2.

Our objective is to bound the absolute value of the expression

$\sum_{uv\in F_{-}}d_{G_{0}}(u,v)\,-\,\sum_{uv\in
F_{+}}d_{G_{0}}(u,v)\,-\,\sum_{uv\in F_{-}}S_{G_{0}}(u,v)\,+\,\sum_{uv\in
F_{+}}S_{G_{0}}(u,v)\,.$ (4.1)

By the definition of synergy, and as $|F_{-}|=|F_{+}|$, this expression is
precisely

$\sum_{uv\in F_{-}}p_{0}d_{G_{0}}(u)+p_{0}d_{G_{0}}(v)-\sum_{uv\in
F_{+}}p_{0}d_{G_{0}}(u)+p_{0}d_{G_{0}}(v).$ (4.2)

As $d_{G_{0}}(u)$ occurs $d_{F_{-}}(u)$ times in the first sum and
$d_{F_{+}}(u)$ times in the second sum, the expression (4.1) is precisely

$p_{0}\,\sum_{u\in
V(G)}d_{G_{0}}(u)\big{(}d_{F_{-}}(u)\,-\,d_{F_{+}}(u)\big{)}$

As $|F_{-}|=|F_{+}|$, we may subtract the constant term $p_{0}n$ from every
degree $d_{G_{0}}(u)$. So that (4.1) is precisely

$p_{0}\,\sum_{u\in
V(G)}\big{(}d_{G_{0}}(u)-p_{0}n\big{)}\big{(}d_{F_{-}}(u)\,-\,d_{F_{+}}(u)\big{)}\,\leqslant\,4p_{0}\varepsilon
Dn^{2}\,,$

by Lemma 4.3. ∎

We now proceed to compute the value of $\sum_{uv\in F_{+}}S_{G_{0}}(u,v)$. The
computation for $\sum_{uv\in F_{-}}S_{G_{0}}(u,v)$ is almost identical and is
omitted. First we introduce the set $F_{+,0}=\\{uw\in E(K_{n}\setminus
G_{0}):S_{G_{0}}(u,w)\geqslant 0\\}$. The introduction of this set is useful
because since $\sum_{uv\in F_{+,0}}S_{G_{0}}(u,v)$ is easier to compute and is
further justified by the following lemma.

Recall that $\sigma_{p_{0}}^{2}=\textup{Var}(S_{G}^{p_{0}}(u,v))$, where
$G\sim G(n,p_{0})$, which we abbreviate to $\sigma^{2}$ for the remainder of
the section.

######  Lemma 4.4.

$\left|\sum_{F_{+,0}}S_{G_{0}}(u,v)-\sum_{F_{+}}S_{G_{0}}(u,v)\right|\,\leqslant\,9\varepsilon^{2}(N-m_{0})\sigma.$

###### Proof.

As $\Phi(0)=1/2$, for every vertex $u$ we have that

$d_{F_{+,0}}(u)\,=\,\left(\frac{1}{2}\pm\varepsilon\right)(n-d_{G_{0}}(u)-1)\,.$
(4.3)

We saw in the proof of Lemma 4.3 that the median of the synergies
$\tilde{\mu}$ satisfies $|\tilde{\mu}|\leqslant 3\varepsilon$. There are two
cases depending on whether $\tilde{\mu}>0$ or not. We consider the case
$\tilde{\mu}>0$, the other case is essentially identical.

As $\tilde{\mu}>0$, $F_{+}$ is contained in $F_{+,0}$. By (4.3) and Lemma 4.3
respectively we have

$e(F_{+,0})\,\leqslant\,\left(\frac{1}{2}+\varepsilon\right)(N-m_{0})\qquad\text{and}\qquad
e(F_{+})\,\geqslant\,\left(\frac{1}{2}-2\varepsilon\right)(N-m_{0})\,.$

Therefore there are at most $3\varepsilon(N-m_{0})$ _extra_ edges in
$F_{+,0}$. Furthermore, all such edges must have

$0\,\leqslant\,S_{G_{0}}(u,v)\,\leqslant\,\tilde{\mu}\,\leqslant\,3\varepsilon\sigma\,.$

It follows that

$\left|\sum_{F_{+,0}}S_{G_{0}}(u,v)-\sum_{F_{+}}S_{G_{0}}(u,v)\right|\,\leqslant\,3\varepsilon(N-m_{0})\,\cdot\,(3\varepsilon\sigma)\,=\,9\varepsilon^{2}(N-m_{0})\sigma\,,$

as required.∎

With the last lemma it only remains to prove a lower bound for the value of
$\sum_{F_{+,0}}S_{G_{0}}(u,v)$.

######  Lemma 4.5.

$\sum_{uv\in
F_{+,0}}S_{G_{0}}(u,v)\geqslant\frac{(1+o(1))\sigma}{\sqrt{2\pi}}(N-m_{0}).$

###### Proof.

Let $S$ be such that $\Phi(S)=1-\varepsilon$. Then, since
$1-\Phi(x)=\mathbb{P}(Z>x)$ and the standard normal distribution has the tail
inequality $\mathbb{P}(Z>x)\leqslant e^{-x^{2}/2}$, we have

$S\leqslant\sqrt{2\log\varepsilon^{-1}}.$

We remark that standard estimates show that
$\int_{S}^{\infty}\mathbb{P}\left(Z>x\right)dx\leqslant 2\varepsilon S$, and
recall that $\int_{0}^{\infty}\mathbb{P}\left(Z>x\right)dx\,=\,1/\sqrt{2\pi}$.
We shall combine these to obtain
$\int_{0}^{S}\mathbb{P}\left(Z>x\right)dx\,\geqslant\,1/\sqrt{2\pi}\,-\,2\varepsilon
S$.

Since for every $u\in V(G_{0})$ the sequence $\mathcal{S}_{G_{0}}(u)$ is
$\varepsilon$-close to normal, we have

$\big{|}|\\{w:S_{G_{0}}(u,w)>x\sigma\\}|-(1-\Phi(x))(n-d_{G_{0}}(u)-1)\big{|}\,\leqslant\,\varepsilon(n-d_{G_{0}}(u)-1).$

Hence,

$\begin{split}\sum_{uv\in
F_{+,0}}S_{G_{0}}(u,v)\,&=\,\frac{\sigma}{2}\sum_{u\in V(G)}\sum_{v\in
N_{F_{+,0}}(u)}\frac{S_{G_{0}}(u,w)}{\sigma}\\\ &=\,\frac{\sigma}{2}\sum_{u\in
V(G)}\int_{0}^{\infty}[\\#w:S_{G_{0}}(u,w)>x\sigma]dx\\\
&\geqslant\,\frac{\sigma}{2}\sum_{u\in
V(G)}(n-d_{G_{0}}(u)-1)\int_{0}^{S}(1-\Phi(x))-\varepsilon\,dx\\\
&\geqslant\,\sigma(N-m_{0})\left(\frac{1}{\sqrt{2\pi}}-3\varepsilon
S\right)\end{split}$

As $S\leqslant\sqrt{2\log\varepsilon^{-1}}$, then the error term is $o(1)$, as
required.

∎

We can finally prove Proposition 4.1. Lemma 4.2 shows that is enough to bound

$\sum_{uv\in F_{-}}S_{G_{0}}(u,v)-\sum_{uv\in
F_{+}}S_{G_{0}}(u,v)\pm\varepsilon p_{0}Dn^{2}.$

Lemmas 4.4 and 4.5 let us compute

$\begin{split}\sum_{F_{+}}S_{G_{0}}(u,v)\,&\geqslant\,\sum_{F_{+}}S_{G_{0}}(u,v)-3\varepsilon^{2}(N-m_{0})\sigma\\\
&\geqslant\,\frac{\sigma}{\sqrt{2\pi}}(N-m_{0})-3\varepsilon^{2}(N-m_{0})\sigma\\\
&=\,\left(\frac{1}{\sqrt{2\pi}}-o(1)\right)\sigma(N-m_{0})\end{split}$

Futhermore, $D\leqslant n^{1/2}\log n$ by hyphoteses. Hence, $\varepsilon
p_{0}Dn^{2}=o(n^{5/2})$, as $\varepsilon=n^{-1/5}$.

Finally, as the sum of the synergies of $F_{-}$ has the same results and
$\sigma=\Theta(n^{1/2})$, see A.1, there is a $C>0$ such that

$\sum_{uv\in F_{-}}S_{G_{0}}(u,v)-\sum_{uv\in
F_{+}}S_{G_{0}}(u,v)\pm\varepsilon p_{0}Dn^{2}\leqslant-Cn^{5/2}$

as claimed.

##  5\. Defining the event $E_{\alpha}$

In this section we define events $E_{\alpha}:\alpha>0$, which shall be used to
prove Proposition 2.1. (The value of $\alpha$ will be chosen appropriately as
a function of $\delta$.)

Recall that $\varepsilon:=n^{-1/5}$. Let $\eta>0$ be a constant which we
choose (sufficiently small) later. We shall assume that $N-(1-\eta_{n})m$ is
an even integer777This is a minor abuse of notation. Only the order of
magnitude of $\eta$ matters for our purposes, and this error is of the form
$\pm O(n^{-2}$) with respect to the size of $\eta$. for all sufficiently large
$n$.

Define $m_{0}:=(1-\eta)m$ and $m_{1}=\eta m$. As mentioned in Section 2 we may
generate $G_{m}$ using the Erdős-Rényi random graph process. In a slight abuse
of notation let $G_{0}:=G_{m_{0}}\sim G(n,m_{0})$ and let
$G_{1}:=G_{m}\setminus G_{m_{0}}\sim G(n,m_{1})$. That is, $G_{0}$ represents
the first $m_{0}$ edges of our random graph $G_{m}$, and $G_{1}$ represents
the remaining $m_{1}=m-m_{0}$ edges.

Before defining $E_{\alpha}$, let us mention some useful quasirandomness
properties for the first graph $G_{0}\sim G(n,m_{0})$.

By Lemma 4.6 of [GGS], see also Corollary 5.2 of [AGG], applied to
$G_{0}^{c}\sim G(n,N-m_{0})$, there exists an absolute constant $C_{D}$ such
that

$\sum_{u,w\in V(G_{0}^{c})}D_{G_{0}^{c}}(u,w)^{2}\,\leqslant\,C_{D}n^{3}\,$
(P1)

with high probability. We also have, by Proposition 3.1, that with high
probability

$\forall u\in V(G_{0})\quad\mathcal{S}_{G_{0}}(u)\,\,\text{is
}\varepsilon\text{-close to normal}\,.$ (P2)

The following properties concern degrees, codegrees, edge counts and triangle
counts. We omit the quantifications. It should be understood that the
properties are for all vertices $u$, pairs of vertices $u,w$, sets $U$, and
disjoint pairs of sets $U,V$ respectively. Let $p_{0}=m_{0}/N$.

$\big{|}d_{G_{0}}(u)\,-\,p_{0}n\big{|}\,\leqslant\,n^{1/2}\log{n}\phantom{\bigg{|}}$
(P3)
$\big{|}d_{G_{0}}(u,w)\,-\,p_{0}^{2}n\big{|}\,\leqslant\,n^{1/2}\log{n}\phantom{\bigg{|}}$
(P4)
$\left|e(G_{0}[U])\,-\,p_{0}\binom{|U|}{2}\right|\,\leqslant\,n^{3/2}\phantom{\Bigg{|}}$
(P5)
$\big{|}e(G_{0}[U,V])\,-\,p_{0}|U||V|\big{|}\,\leqslant\,n^{3/2}\phantom{\bigg{|}}$
(P6)

Let $E_{0}$ be the event that all eight properties (P1)-(P6) are satisfied by
the graph $G_{0}$. We shall in fact prove that $E_{0}$ has very small failure
probability, and this will be useful to bound the effect of conditioning on
$E_{0}$.

######  Lemma 5.1.

$\mathbb{P}(E_{0})\,\geqslant\,1-n^{-3}.$

###### Proof.

Let’s compute the probability of each property not happening. We may already
bound the probability that properties (P1) or (P2) do not hold. Lemma 4.6 of
[GGS] and Proposition 3.1 shows that, respectively,

$\mathbb{P}(P_{1}^{c})\leqslant
e^{-n}\qquad\text{and}\qquad\mathbb{P}(P_{2}^{c})\leqslant\exp(-n^{1/10+o(1)}).$

The bounds for the probabilities of (P3)-(P6) are all given by the Chernoff
bound for hypergeometric random variables. For example, by (2.5) and (2.6) of
[JLR], we have that, for all $t\leqslant\mu$,

$\mathbb{P}\left(|X-\mu|\,\geqslant\,t\right)\,\leqslant\,2\exp\left(\frac{-t^{2}}{2(\mu+t/3)}\right)\,\leqslant\,2\exp\left(\frac{-3t^{2}}{8\mu}\right)$

where $X$ is a hypergeometric random variable with mean $\mu$. Applying this
inequality, and appropriate union bounds we obtain

$\mathbb{P}(P3^{c}),\mathbb{P}(P4^{c})\,\leqslant\,n^{2}e^{-(\log
n)^{2}}\qquad\text{and}\qquad\mathbb{P}(P5^{c}),\mathbb{P}(P6^{c})\,\leqslant\,e^{-cn}\,,$

for some constant $c>0$.

As each of these bounds is smaller then $n^{-4}$, for all sufficiently large
$n$, it follows that $P(E_{0}^{c})\leqslant n^{-3}$, as claimed ∎

We now deduce that conditioning on $E_{0}$ has little effect on expected
values of functions $f:\mathcal{G}_{n,m}\to\mathbb{R}$, where
$\mathcal{G}_{n,m}$ is the set of graphs with $n$ vertices and $m$ edges.

######  Lemma 5.2.

Given a function $f:\mathcal{G}_{n,m}\to\mathbb{R}$, let
$\overline{F}:=\max\\{f(G):G\in\mathcal{G}_{n,m}\\}$ and
$\underline{F}:=\min\\{f(G):G\in\mathcal{G}_{n,m}\\}$. Then

$\Big{|}\mathbb{E}\big{[}f(G_{m})\,|\,E_{0}\big{]}\,-\,\mathbb{E}\big{[}f(G_{m})\big{]}\Big{|}\,\leqslant\,(\overline{F}-\underline{F})n^{-3}.$

###### Proof.

By conditioning, we have

$\begin{split}\mathbb{E}\big{[}f(G_{m})\big{]}\,&=\,\mathbb{P}(E_{0})\mathbb{E}\big{[}f(G_{m})|E_{0}\big{]}+\mathbb{P}(E_{0}^{c})\mathbb{E}\big{[}f(G_{m})|E_{0}^{c}\big{]}\\\
&\,=\mathbb{E}\big{[}f(G_{m})|E_{0}\big{]}+\mathbb{P}(E_{0}^{c})\big{(}\mathbb{E}\big{[}f(G_{m})|E_{0}^{c}\big{]}-\mathbb{E}\big{[}f(G_{m})|E_{0}\big{]}\big{)}\,.\end{split}$

The claimed bound now follows, as $\mathbb{P}(E_{0}^{c})\leqslant n^{-3}$, by
Lemma 5.1, and the difference between the conditional expectations has
absolute value at most $(\overline{F}-\underline{F})$. ∎

We shall soon be ready to define the event $E_{\alpha}$. Let us first recall
(from Section 2) that we let $f_{1},\dots f_{N-m_{0}}$ be the non-edges of
$G_{0}$ in non-decreasing order of synergy $S(u,w)$, and define

$F_{-}\,:=\,\left\\{f_{i}:i\in\left\\{1,\dots,\frac{N-m_{0}}{2}\right\\}\right\\}\,,$

that is $F_{-}$ is a graph consisting of the half of non-edges of $G_{0}$ with
smaller synergy.

######  Definition 5.3.

Let $E(\alpha)$ be the event888We again commit a slight abuse in assuming that
$(1+\alpha)m_{1}/2$ is an integer. This is a minor abuse of notation, as only
the order of magnitude of the deviation really matters for our argument. that
$|F_{-}\cap E(G_{1})|=(1+\alpha)m_{1}/2$.

######  Definition 5.4.

Let $E_{\alpha}:=E_{0}\cap E(\alpha)$

In other words, $E(\alpha)$ is the event that $G_{1}$ takes significantly more
of its edges in $F_{-}$ (the pairs of low synergy) than expected. Hence
$E_{\alpha}$ is simply the event that $G_{0}$ is well behaved (satisfying
(P1)-(P6)) _and_ this event $E(\alpha)$ occurs.

Let us remark that, as $E(\alpha)$ is independent of $G_{0}$ (and so also of
$E_{0}$), a conditional expectation with respect to $E_{\alpha}$ may be
calculated as

$\mathbb{E}\left[f(G)|E_{\alpha}\right]\,=\,\sum_{G^{\prime}_{0}}\mathbb{P}\left(G_{0}=G^{\prime}_{0}|E_{0}\right)\mathbb{E}\left[f(G)|E(\alpha),G_{0}\right]\,.$
(5.1)

We now proceed to prove a lower bound on the probability of $E_{\alpha}$.

######  Proposition 5.5.

Let $\eta,\lambda\in(0,1)$ and suppose that $\alpha=\alpha_{n}$ is a sequence
such that $\log{n}/n\ll\alpha\ll 1$. Then

$\mathbb{P}\left(E_{\alpha}\right)\,\geqslant\,\exp\left(-\lambda^{-1}\alpha^{2}n^{2}\right)$

for all sufficiently large $n$.

###### Proof.

As $E_{0}$ and $E(\alpha)$ are independent, and
$\mathbb{P}\left(E_{0}\right)=1+o(1)$ (by Lemma 5.1), it suffices to prove
that the claimed bound holds for the event $E(\alpha)$. The event $E(\alpha)$
corresponds to a random variable with hypergeometric distribution
$\textrm{Hyp}\big{(}N-m_{0},(N-m_{0})/2,m_{1}\big{)}$ taking the value
$(1+\alpha)\mu$. In the appendix we prove (Corollary B.2) that this
probability is at least $\exp(-\lambda^{-1}\alpha^{2}(N-m_{0}))$. The required
bound easily follows. ∎

We remark that conditioning on $E_{0}$ (or $E_{\alpha}$) also gives us the
following property on the degrees of vertices in $F_{-}$:

$d_{F_{-}}(u)\,=\,\left(\frac{1}{2}\pm
2\varepsilon\right)(n-d_{G_{0}}(u)-1)\,.$ (5.2)

Indeed Lemma 4.3 shows that this is a consequence of property (P2). As
$d_{F-}(u)+d_{F+}(u)=n-d_{G_{0}}(u)-1$, the same result follows for $F_{+}$.

##  6\. Completing the proof of Theorem 1.1

As outlined in Section 2, it suffices to prove Proposition 2.1, which we now
restate.

See 2.1

Fix a value of $\lambda\in(0,1)$. As we have discussed, the event $E$ we shall
use is one of the events $E_{\alpha}$ defined in the previous section. We
shall take $\alpha$ to be $\alpha=C^{\prime}\delta n^{1/2}$ for a constant
$C^{\prime}$ below.

By Proposition 5.5, it is clear that condition (i) of Proposition 2.1 holds
for the event $E_{\alpha}$, as long as we take
$C\geqslant\lambda^{-1}(C^{\prime})^{2}$. All that remains is to prove that

$\mathbb{E}\left[N_{\triangle}(G_{m})\,|\,E_{\alpha}\right]\,\leqslant\,(1-2\delta)\mu_{n,m}\,,$

and it will be done in this section.

We consider the triangles in four classes: those with three edges from
$G_{0}$, two edges from $G_{0}$ and one from $G_{1}$, one from $G_{0}$ and two
from $G_{1}$ or three from $G_{1}$. We will denote by $\triangle_{(3,0)}$,
$\triangle_{(2,1)}$, $\triangle_{(1,2)}$ and $\triangle_{(0,3)}$, the
respective counts.

Let $q_{0}:=1-p_{0}$ and $p_{1}:=\mathbb{P}\big{(}e\in E(G_{1})\big{)}=\eta
m/N$. Note that $p=p_{0}+p_{1}$. We shall deduce (ii) from the following four
lemmas.

######  Lemma 6.1.

$\mathbb{E}\left[\triangle_{(3,0)}|E_{\alpha}\right]\,=\,p_{0}^{3}\binom{n}{3}\,\pm\,1.$

######  Lemma 6.2.

There is a constant $c_{(2,1)}>0$ such that

$\mathbb{E}\left[\triangle_{(2,1)}|E_{\alpha}\right]\,\leqslant\,3p_{0}^{2}p_{1}\binom{n}{3}\,-\,c_{(2,1)}\,\eta\alpha
n^{5/2}\,\pm\,1.$

######  Lemma 6.3.

There is a constant $c_{(1,2)}>0$ such that

$\mathbb{E}\left[\triangle_{(1,2)}|E_{\alpha}\right]\,\leqslant\,3p_{0}p_{1}^{2}\binom{n}{3}\,+\,c_{(1,2)}\,\eta^{2}\alpha
n^{5/2}\,\pm\,1.$

######  Lemma 6.4.

There is a constant $c_{(0,3)}>0$ such that

$\mathbb{E}\left[\triangle_{(0,3)}|E_{\alpha}\right]\,\leqslant\,p_{1}^{3}\binom{n}{3}\,+\,c_{(0,3)}\,\eta^{3}\alpha
n^{5/2}\pm 1.$

We now prove that (ii) follows from the above lemmas. Given the constants
$c_{(2,1)}$, $c_{(1,2)}$ and $c_{(0,3)}$ of the lemmas, we now fix the value
of $\eta>0$ which we shall use.

As $\eta^{2}c_{(0,3)}\,+\,\eta c_{(1,2)}\,-\,c_{(2,1)}$ is increasing (for
$\eta\geqslant 0$), we may choose $\eta>0$ such that
$\eta^{2}c_{(0,3)}\,+\,\eta c_{(1,2)}\,-\,c_{(2,1)}\,=\,-c_{(2,1)}/2$. Let us
set $C^{\prime}=1/c_{(2,1)}\eta$.

###### Proof of (ii).

As
$\mathbb{E}[N_{\triangle}(G_{m})]=\mu_{n,m}=p^{3}\binom{n}{3}=(p_{0}+p_{1})^{3}\binom{n}{3}$,
the main terms sum to $\mu_{n,m}$. And so,

$\begin{split}\mathbb{E}[N_{\triangle}(G_{m})\,|\,E_{\alpha}]\,&=\,\mathbb{E}\left[\triangle_{(3,0)}|E_{\alpha}\right]+\mathbb{E}\left[\triangle_{(2,1)}|E_{\alpha}\right]+\mathbb{E}\left[\triangle_{(1,2)}|E_{\alpha}\right]+\mathbb{E}\left[\triangle_{(0,3)}|E_{\alpha}\right]\phantom{\Big{|}}\\\
&\leqslant\,\mu_{n,m}\,+\,\eta\alpha n^{5/2}\big{(}\eta^{2}c_{(0,3)}\,+\,\eta
c_{(1,2)}\,-\,c_{(2,1)}\big{)}\,\pm\,4\phantom{\Big{|}}\\\
&=\,\mu_{n,m}\,-\,\frac{c_{(2,1)}\eta\alpha n^{5/2}}{2}\,\pm\,4\end{split}$

Recalling that we shall choose $\alpha=C^{\prime}\delta n^{1/2}$, where
$C^{\prime}=1/c_{(2,1)}\eta$, we obtain

$\mathbb{E}[N_{\triangle}(G_{m})\,|\,E_{\alpha}]\,\leqslant\,\mu_{n,m}\,-\,\frac{\delta
n^{3}}{2}\,+\,4\,\leqslant\,\mu_{n,m}(1-2\delta).$

∎

A remark on the choice of constants:

  * •

The constants $c_{(2,1)},c_{(1,2)}$ and $c_{(0,3)}$ which occur in the lemmas
may depend only on $\lambda$.

  * •

We chose $\eta$ as a function of $c_{(2,1)},c_{(1,2)}$ and $c_{(0,3)}$.

  * •

We chose $C^{\prime}=1/c_{(2,1)}\eta$ as a function of $c_{(2,1)}$ and $\eta$.

  * •

The final constant $C$ of Proposition 2.1 may be taken to be
$C=\max\\{C^{\prime},\lambda^{-1}(C^{\prime})^{2}\\}$.

In order to complete the proof, we prove the lemmas above in the following
subsections. As $C\geqslant C^{\prime}$, we note in particular that

$\alpha\,=\,C^{\prime}\delta
n^{1/2}\,\leqslant\,\frac{C^{\prime}}{C}n^{-3/4}n^{1/2}\,\leqslant\,n^{-1/4}\,.$
(6.1)

###  6.1. Proof of Lemma 6.1

The first type of triangle, $\triangle_{(3,0)}$, is independent of $G_{1}$,
and so

$\mathbb{E}\big{[}\triangle_{(3,0)}\,|\,E_{\alpha}\big{]}\,=\,\mathbb{E}\big{[}\triangle_{(3,0)}\,|\,E_{0}\big{]}\,=\,p_{0}^{3}\binom{n}{3}\,\pm\,1.$
(6.2)

using Lemma 5.2 with $\max\\{\triangle_{(3,0)}\\}\leqslant n^{3}$ and
$\min\\{\triangle_{(3,0)}\\}\geqslant 0$.

###  6.2. Proof of Lemma 6.2

We recall that our whole strategy for creating fewer triangles relies on
creating fewer triangles of this type. We now show how this works.

Recall that $E_{\alpha}=E_{0}\cap E(\alpha)$, that is, $E_{\alpha}$ is the
intersection of $E_{0}$, the event that $G_{0}$ satisfies the properties
(P1)-(P6), and $E(\alpha)$, the event that (given the graph $F_{-}$ defined by
$G_{0}$) $G_{1}$ contains $(1+\alpha)m_{1}/2$ edges of $F_{-}$. In particular,
given $G_{0}$, on the event $E_{\alpha}$ each edge of $F_{-}$ is included in
$G_{1}$ with probability $(1+\alpha)m_{1}/(N-m_{0})$, and each edge of $F_{+}$
with probability $(1-\alpha)m_{1}/(N-m_{0})$.

For convenience, we use the notation $d(u,v)$ for $d_{G_{0}}(u,v)$, the
codegree of $u$ and $v$ in $G_{0}$, and $d(u)$ for $d_{G_{0}}(u)$, the degree
of $u$ in $G_{0}$. We have

$\begin{split}\mathbb{E}\left[\triangle_{(2,1)}|E_{\alpha}\right]&=\mathbb{E}\left[\sum_{uv\in
F_{-}}\frac{(1+\alpha)m_{1}}{N-m_{0}}d(u,v)\,+\,\sum_{uv\in
F_{+}}\frac{(1-\alpha)m_{1}}{N-m_{0}}d(u,v)\,\middle|\,E_{0}\right]\phantom{\scalebox{1.5}{\Bigg{|}}}\\\
&=\,\mathbb{E}\left[\triangle_{(2,1)}\,\middle|\,E_{0}\right]\,+\,\frac{p\eta\alpha}{1-p_{0}}\,\mathbb{E}\left[\sum_{uv\in
F_{-}}d(u,v)-\sum_{uv\in
F_{+}}d(u,v)\,\middle|\,E_{0}\right]\,,\phantom{\scalebox{1.5}{\Bigg{|}}}\end{split}$

where the second equality uses that the main term produces exactly the
expected value $\mathbb{E}[\triangle_{(2,1)}\,|\,E_{0}]$, and that $m_{1}=\eta
pN$.

As we are conditioning on $E_{0}$, we know that properties (P2) and (P3) hold
for $G_{0}$, and so by Proposition 4.1 we have

$\sum_{uv\in F_{-}}d(u,v)\,-\,\sum_{uv\in F_{+}}d(u,v)\,\leqslant\,-cn^{5/2}$

for some constant $c>0$, on the event $E_{0}$. Taking $c_{(2,1)}=cp$, and
using Lemma 5.2, we now have

$\begin{split}\mathbb{E}\left[\triangle_{(2,1)}|E_{\alpha}\right]\,&\leqslant\,3p_{0}^{2}p_{1}\binom{n}{3}\,-\,c_{(2,1)}\,\eta\alpha
n^{5/2}\,.\end{split}$

###  6.3. Proof of Lemma 6.3

We now proceed to the third type of triangles, $\triangle_{(1,2)}$. A triangle
of type $(1,2)$ consists of vertices $u,v,w$, such that $vw$ is an edge of
$G_{0}$ and both $uv$ and $uw$ are edges of $G_{1}$. So that

$\triangle_{(1,2)}\,=\,\sum_{u,v,w}1_{vw\in E(G_{0})}1_{uv,uw\in E(G_{1})}\,.$

Let $e(u):=e(G_{0}[V\setminus(N(u)\cup\\{u\\})])$ denote the number of edges
of $G_{0}$ amongst the non-neighbours of $u$. Each edge of $E(K_{n})\setminus
E(G_{0})$ is in $G_{1}$ with probability $r_{1}:=p_{1}/(1-p_{0})$, and each
such pair of edges is in $G_{1}$ with probability $r_{1}^{2}+O(n^{-2})$. It
follows that

$\mathbb{E}[\triangle_{(1,2)}|G_{0}]\,=\,r_{1}^{2}\sum_{u}e(u)\,\pm\,O(n)\,.$

If we condition only on the event $E_{0}$ then, as $r_{1}(1-p_{0})=p_{1}$, and
using Lemma 5.2, we have

$\displaystyle\mathbb{E}\left[\triangle_{(1,2)}|E_{0}\right]\,$
$\displaystyle=\,r_{1}^{2}\sum_{u}\mathbb{E}\left[e(u)|E_{0}\right]\,\pm\,O(n)$
$\displaystyle=\,r_{1}^{2}\sum_{u}\mathbb{E}\left[e(u)\right]\,\pm\,O(n)$
$\displaystyle=\,3p_{0}p_{1}^{2}\binom{n}{3}\,\pm\,O(n)\,.$

What changes when we condition on $E_{\alpha}$? As $E_{\alpha}=E_{0}\cap
E(\alpha)$, for a graph $G_{0}$ satisfying the conditions of $E_{0}$, the
conditioning affects the probabilities that the edges $uv$ and $uw$ are
included in $G_{1}$. As they will now depend on whether $uv$ and $uw$ belong
to $F_{-}$ or $F_{+}$. If both belong to $F_{-}$ then the probability
$r_{1}^{2}+O(n^{-2})$ is multiplied by a factor of $(1+\alpha)^{2}$. If one is
in $F_{-}$ and the other in $F_{+}$ then the factor is $(1+\alpha)(1-\alpha)$.
Finally, if both are in $F_{+}$ then the factor is $(1-\alpha)^{2}$.

Let us define $e_{-}(u):=e(G_{0}[N_{F_{-}}(u)])$ to be the number of edges of
$G_{0}$ in the $F_{-}$-neighbourhood of $u$. Respectively
$e_{\pm}(u):=e(G_{0}[N_{F_{-}}(u),N_{F_{+}}(u)])$ and
$e_{+}(u):=e(G_{0}[N_{F_{+}}(u)])$. Note that
$e(u)=e_{-}(u)+e_{\pm}(u)+e_{+}(u)$. Using this notation we see that for a
fixed graph $G_{0}$ satisfying $E_{0}$, we have

$\displaystyle\mathbb{E}\left[\triangle_{(1,2)}|E(\alpha),G_{0}\right]\,$
$\displaystyle=\,r_{1}^{2}\,\sum_{u}\,\Big{(}(1+\alpha)^{2}e_{-}(u)\,+\,(1+\alpha)(1-\alpha)e_{\pm}(u)\,+\,(1-\alpha)^{2}e_{-}(u)\Big{)}$
$\displaystyle=\,r_{1}^{2}\sum_{u}e(u)\,+\,2r_{1}^{2}\alpha\sum_{u}\big{(}e_{-}(u)-e_{+}(u)\big{)}\,+\,r_{1}^{2}\alpha^{2}\sum_{u}\big{(}e_{-}(u)+e_{+}(u)-e_{\pm}(u)\big{)}\,,$

up to an $\pm O(n)$ error on each line. Rather than conditioning on a fixed
graph $G_{0}$ we need to condition just that $G_{0}$ is in $E_{0}$. Doing so
corresponds to taking the conditional expected value. Let
$\mu_{-}=\mathbb{E}\left[e_{-}(u)|E_{0}\right]$,
$\mu_{+}=\mathbb{E}\left[e_{+}(u)|E_{0}\right]$ and
$\mu_{\pm}=\mathbb{E}\left[e_{\pm}(u)|E_{0}\right]$, noting of course that
these values are the same for all vertices $u$. And so

$\mathbb{E}[\triangle_{(1,2)}|E_{\alpha}]\,=\,p_{0}p_{1}^{2}\binom{n}{3}\,+\,2r_{1}^{2}\alpha\big{(}\mu_{-}\,-\,\mu_{+}\big{)}n\,+\,r_{1}^{2}\alpha^{2}\big{(}\mu_{-}\,+\,\mu_{+}\,-\,\mu_{\pm}\big{)}n\,\pm\,O(n)\,.$
(6.3)

In what follows, in the $O(\cdot)$ notation the implicit constant may only
depend on the constant $\lambda$ of Proposition 2.1 and is not allowed to
depend on other quantities such as our choices of $\eta$ or $C^{\prime}$. In
this context, we can state that $r_{1}=O(\eta)$.

As $r_{1}=O(\eta)$ and $\alpha\leqslant n^{-1/4}$ (see (6.1)), we can see from
(6.3) that it will suffice to prove that $\mu_{-}-\mu_{+}=O(n^{3/2})$ and
$\mu_{-}+\mu_{+}-\mu_{\pm}=O(n^{8/5})$. In fact, we can do much better than
that: we prove that for _every_ $G_{0}$ satisfying $E_{0}$ we have

$\sum_{u\in V(G_{0})}\big{(}e_{-}(u)\,-\,e_{+}(u)\big{)}\,=\,O(n^{5/2})\,,$
(6.4)

and

$e_{-}(u)\,+\,e_{+}(u)\,-\,e_{\pm}(u)\,=\,O(n^{8/5})\phantom{\Big{|}}$ (6.5)

for all vertices $u\in V(G_{0})$. Doing so will complete the proof of Lemma
6.3.

Let us first introduce some notation that encapsulates the idea of conditional
deviation. Let $\bar{d}(u):=(n-d(u)-1)/2$, half the number of non-edges of $u$
in $G_{0}$. Let $D_{+}(u):=d_{F_{+}}(u)-\bar{d}(u)$ and
$D_{-}(u):=d_{F_{-}}(u)-\bar{d}(u)$ be the deviations of these degrees. Using
the handshaking lemma twice, we see that

$\sum_{u\in V(G_{0})}D_{+}(u)\,=\,2e(F_{+})\,-\,(N-m_{0})\,=\,0\,.$

Similarly $\sum_{u}D_{-}(u)=0$.

Proof of (6.4) Let $G_{0}$ be a graph satisfying $E_{0}$, that is, satisfying
(P1)- (P6). By (5.2) (which is a consequence of (P2)) that
$|D_{+}(u)|,|D_{-}(u)|\leqslant 2\varepsilon n$ for all $u\in V(G_{0})$. The
other source of “error” in $e_{-}(u)$ and $e_{+}(u)$ comes from that deviation
of the edge count of $G_{0}$ in the respective neighbourhoods $N_{F-}(u)$ and
$N_{F+}(u)$. These deviations are bounded by $n^{3/2}$ by (P5). For example,
as $d_{F-}(u)=\bar{d}(u)+D_{-}(u)$, we have

$\displaystyle e_{-}(u)\,=\,e(G_{0}[N_{F-}(u)])\,$
$\displaystyle=\,\binom{d_{F_{-}}(u)}{2}\,\pm\,n^{3/2}$
$\displaystyle=\,\frac{\big{(}\bar{d}(u)+D_{-}(u)\big{)}^{2}}{2}\,\pm\,O(n^{3/2})$
$\displaystyle=\,\frac{\bar{d}(u)^{2}}{2}\,+\,\bar{d}(u)D_{-}(u)\,+\,\frac{D_{-}(u)^{2}}{2}\,\pm\,O(n^{3/2})\,.$
(6.6)

By a similar argument

$e_{+}(u)\,=\,\frac{\bar{d}(u)^{2}}{2}\,+\,\bar{d}(u)D_{+}(u)\,+\,\frac{D_{+}(u)^{2}}{2}\,\pm\,O(n^{3/2})\,.$
(6.7)

As $D_{+}(u)=-D_{-}(u)$, we have that $D_{+}(u)^{2}=D_{-}(u)^{2}$, and so
these terms cancel, and we see that

$e_{-}(u)\,-\,e_{+}(u)\,=\,\bar{d}(u)\big{(}D_{-}(u)-D_{+}(u)\big{)}\,\pm\,O(n^{3/2})\,=\,2\bar{d}(u)D_{-}(u)\,\pm\,O(n^{3/2})\,.$

We now sum this expression over $u\in V(G_{0})$. We shall write
$\bar{d}(u)=(n-d_{G_{0}}(u)-1)/2=(1-p_{0})(n-1)/2-D_{G_{0}}(u)/2$. We obtain

$\displaystyle\sum_{u\in V(G_{0})}\big{(}e_{-}(u)\,-\,e_{+}(u)\big{)}\,$
$\displaystyle=\,2\sum_{u}\bar{d}(u)D_{-}(u)\,\pm\,O(n^{5/2})$
$\displaystyle\,=\,(1-p_{0})n\sum_{u}D_{-}(u)\,-\,\sum_{u}D_{G_{0}}(u)D_{-}(u)\,\pm\,O(n^{5/2})$
$\displaystyle=\,O(n^{5/2})\,.\phantom{\big{|}}$

The final bound uses that $\sum_{u}D_{-}(u)=0$ and the estimates
$|D_{G_{0}}(u)|\leqslant n^{1/2}\log{n}$ by (P3) and $|D_{-}(u)|\leqslant
2\varepsilon n$, which we stated at the start of the proof of (6.4).

Proof of (6.5) We begin by considering $e_{\pm}(u)$. Using (P5), and the fact
that $D_{+}(u)=-D_{-}(u)$, we have

$\displaystyle e_{\pm}(u)\,$
$\displaystyle=\,e(G_{0}[N_{F-}(u),N_{F_{+}}(u)])\phantom{\big{|}}$
$\displaystyle=\,d_{F_{-}}(u)d_{F_{+}}(u)\,\pm\,n^{3/2}\phantom{\Big{|}}$
$\displaystyle=\,\big{(}\bar{d}(u)+D_{-}(u)\big{)}\big{(}\bar{d}(u)+D_{+}(u)\big{)}\,\pm\,n^{3/2}\phantom{\Big{|}}$
$\displaystyle=\,\bar{d}(u)^{2}\,-\,D_{-}(u)^{2}\,\pm\,n^{3/2}\,.\phantom{\big{|}}$
(6.8)

From (6.6), (6.7) and (6.8), we see that

$e_{-}(u)\,+\,e_{+}(u)\,-\,e_{\pm}(u)\,=\,2D_{-}(u)^{2}\,\pm\,O(n^{3/2})$

We now again use that $|D_{-}(u)|\leqslant 2\varepsilon n$, and
$\varepsilon=n^{-1/5}$. It follows immediately that
$e_{-}(u)\,+\,e_{+}(u)\,-\,e_{\pm}(u)=O(n^{8/5})$, as required.

###  6.4. Proof of Lemma 6.4

We now proceed to the final type of triangle, $\triangle_{(0,3)}$. A triangle
of type $(0,3)$ consists of a set of three vertices $u,v,w$, such that all
three pairs $uv,uw,vw$ appear as edges of $G_{1}$. So that

$\triangle_{(0,3)}\,=\,\sum_{\\{u,v,w\\}}1_{uv,uw,vw\in E(G_{1})}\,.$

Each edge of $E(K_{n})\setminus E(G_{0})$ is in $G_{1}$ with probability
$r_{1}:=p_{1}/(1-p_{0})$, and each such trio of edges is in $G_{1}$ with
probability $r_{1}^{3}+O(n^{-2})$. It follows that

$\mathbb{E}[\triangle_{(0,3)}|G_{0}]\,=\,r_{1}^{3}N_{\triangle}(G_{0}^{c})\,\pm\,O(n)\,.$

If we condition only on the event $E_{0}$ then, as $r_{1}(1-p_{0})=p_{1}$, and
using Lemma 5.2, we have

$\displaystyle\mathbb{E}\left[\triangle_{(0,3)}|E_{0}\right]\,$
$\displaystyle=\,r_{1}^{3}\mathbb{E}\left[N_{\triangle}(G_{0}^{c})|E_{0}\right]\,\pm\,O(n)$
$\displaystyle=\,r_{1}^{3}\mathbb{E}\left[N_{\triangle}(G_{0}^{c})\right]\,\pm\,O(n)$
$\displaystyle=\,p_{1}^{3}\binom{n}{3}\,\pm\,O(n)\,.$

What changes when we condition on $E_{\alpha}$? As $E_{\alpha}=E_{0}\cap
E(\alpha)$, for a graph $G_{0}$ satisfying the conditions of $E_{0}$, the
conditioning affects the probabilities that the edges $uv,uw$ and $vw$ are
included in $G_{1}$. As they will now depend on whether these pairs belong to
$F_{-}$ or $F_{+}$. If all three belong to $F_{-}$ then the probability
$r_{1}^{2}+O(n^{-2})$ is multiplied by a factor of $(1+\alpha)^{3}$. More
generally, the factor is $(1+\alpha)^{2}(1-\alpha)$ if just two are in
$F_{-}$, it is $(1+\alpha)(1-\alpha)^{2}$ if just one is in $F_{-}$, and is
$(1-\alpha)^{3}$ if all three are in $F_{+}$. For $i\in\\{0,1,2,3\\}$, let
$T_{i}$ denote the number of triangles in $G_{0}^{c}$, which have precisely
$i$ edges in $F_{-}$ and $3-i$ edges in $F_{+}$.

By the above discussion, we see that

$\begin{split}\mathbb{E}\left[\triangle_{(0,3)}|E(\alpha),G_{0}\right]\,&=\,p_{1}^{3}\binom{n}{3}\,\pm\,O(n)\\\
&+\alpha r_{1}^{3}\big{(}3T_{3}\,+\,T_{2}\,-\,T_{1}\,-\,3T_{0}\big{)}\\\
&+\,\alpha^{2}r_{1}^{3}\big{(}3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}\big{)}\\\
&+\,\alpha^{3}r_{1}^{3}\big{(}T_{3}-T_{2}+T_{1}-T_{0}\big{)}\,.\end{split}$
(6.9)

We shall prove for every choice of $G_{0}$ which satisfies $E_{0}$ (that is,
satisfies (P1)- (P6)) we have

$3T_{3}\,+\,T_{2}\,-\,T_{1}\,-\,3T_{0}\,=\,O(n^{5/2})$ (6.10)

and

$3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}\,=\,\frac{(1-p_{0})^{3}n^{3}}{2}\,-\,3N_{\triangle}(G_{0}^{c})\,\pm\,O(n^{13/5})\,.$
(6.11)

As in the previous subsection the implicit constants in the $O(\cdot)$
notation may only depend on the constant $\lambda$ and not on $\eta$ or
$C^{\prime}$.

Let us now observe that Lemma 6.4 would follow. Recall that $r_{1}=O(\eta)$.
If (6.10) holds then the second line of (6.9) is of the form
$O(\alpha\eta^{3}n^{5/2})$. Note also that the final line is trivially at most
$O(\alpha^{3}\eta^{3}n^{3})$, which is also $O(\alpha\eta^{3}n^{5/2})$, as
$\alpha\leqslant n^{-1/4}$ by (6.1). It follows that, if $G_{0}$ satisfies
(6.10) and (6.11), then

$\mathbb{E}\left[\triangle_{(0,3)}|E(\alpha),G_{0}\right]\,=\,p_{1}^{3}\binom{n}{3}\,\pm\,O\left(\alpha^{3}\eta^{3}\left[\frac{(1-p_{0})^{3}n^{3}}{2}\,-\,3N_{\triangle}(G_{0}^{c})\right]\right)\,\pm\,O(\alpha\eta^{3}n^{5/2})\,.$

The conditional expectation given the event $E_{\alpha}$ is obtained by
averaging this over $G_{0}$ satisfying $E_{0}$, as we commented above in
(5.1). By Lemma 5.2, and the fact that
$\mathbb{E}\left[N_{\triangle}(G_{0}^{c})\right]=(1-p_{0})^{3}\binom{n}{3}=(1-p_{0})^{3}n^{3}/6\pm
n^{2}$, the first error term is of the form $O(\alpha^{3}\eta^{3}n^{2})$. We
obtain that

$\mathbb{E}\left[\triangle_{(0,3)}|E_{\alpha}\right]\,=\,p_{1}^{3}\binom{n}{3}\,\pm\,O(\alpha\eta^{3}n^{5/2})\,,$

as required. Thus, to prove Lemma 6.4 it remains only to prove that (6.10) and
(6.11) hold for all graphs $G_{0}$ in $E_{0}$ (that is, satisfying (P1)-
(P6)).

Proof of (6.10) We begin by noting that
$3T_{3}\,+\,T_{2}\,-\,T_{1}\,-\,3T_{0}$ is the same value as that obtained by
summing over triangles of $G_{0}^{c}$ the number of edges in $F_{-}$ minus the
number of edges in $F_{+}$. Let $K_{3}(G)$ denote the set of triangles (a
triangle being considered a set of three edges) in a graph $G$. We have

$\begin{split}3T_{3}\,+\,T_{2}\,-\,T_{1}\,-\,3T_{0}\,&=\,\sum_{A\subset
K_{3}(G_{0}^{c})}|A\cap F_{-}|-|A\cap F_{+}|\\\ &=\,\sum_{uw\not\in
G_{0}}d_{G_{0}^{c}}(u,w)\big{(}1_{uw\in F_{-}}\,-\,1_{uw\in F_{+}}\big{)}\\\
&=\,\sum_{uw\in F_{-}}D_{G_{0}^{c}}(u,w)\,-\,\sum_{uw\in
F_{+}}D_{G_{0}^{c}}(u,w)\\\ &\leqslant\,\left((N-m_{0})\sum_{uw\in
G_{0}^{c}}D_{G_{0}^{c}}(u,w)^{2}\right)^{1/2}\,\\\ &\leqslant
C_{D}^{1/2}n^{5/2},\phantom{\big{|}}\end{split}$

where we used that $|F_{-}|=|F_{+}|$ for the third equality, the Cauchy-
Schwarz inequality for the first inequality and the fact that $G_{0}$
satisfies (P1) for the final inequality.

Proof of (6.11)

We may relate $3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}$ to the number of
monochromatic triangles in a two colouring of the edges of $G_{0}^{c}$.
Indeed, if edges of $F_{-}$ and $F_{+}$ are coloured red and blue
respectively, and $N_{MC}$ denotes the number of monochromatic triangles, then
we have

$3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}\,=\,4N_{MC}\,-\,N_{\triangle}(G_{0}^{c})\,.$
(6.12)

We now state a Goodman type result for monocromatic triangles in an arbitrary
coloured graph. The proof is essentially identical to that of Goodman’s
formula, but we include it for completeness.

######  Lemma 6.5.

Let $G$ be a graph and suppose its edges are red/blue coloured. Let $N_{MC}$
be the number of monocromatic triangles in this colouring and let $N_{R}(v)$
and $N_{B}(v)$ denote the red and blue neighbourhoods of $v$, respectively.
Then

$2N_{MC}\,=\,\sum_{v\in V(G)}e\big{(}G[N_{R}(v)]\big{)}+\sum_{v\in
V(G)}e\big{(}G[N_{B}(v)]\big{)}\,-\,N_{\triangle}(G).$

###### Proof.

Let’s count how much each type of triangle contributes to the RHS. A red
triangle contributes $3$ to the first sum, $0$ to the second and $-1$ to the
third one, giving a total of $2$. Similarly, a blue triangle contributes $0$,
$3$ and $-1$, giving a total of $2$. Now, let $uvw$ be a non-monocramatic
triangle in $G$. Without loss of generality suppose that $uv$ and $uw$ are red
and that $vw$ is blue. Then, this triangle adds $1$ (as $vw$ is an edge of
$G[N_{R}(u)]$) to the first sum, and $0$ and $-1$ to the other two sums. This
gives a total contribution of $0$. Therefore, the only triangles contributing
to the sum are monocromatic and each one is counted twice, as claimed. ∎

From the lemma and (6.12), we see that $3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}$
is precisely

$2\sum_{u}e\big{(}G_{0}^{c}[N_{F_{-}}(u)]\big{)}\,+\,2\sum_{u}e\big{(}G_{0}^{c}[N_{F+}(u)]\big{)}\,-\,3N_{\triangle}(G_{0}^{c})\,.$

We now use (P5) to control the number of edges in the neighbourhoods, and that
$2\binom{d}{2}=d^{2}+O(n)$ for any $d\leqslant n$. Doing so, and using the
notation $q_{0}:=1-p_{0}$, we see that $3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}$
is given by

$q_{0}\sum_{u}d_{F_{-}}(u)^{2}\,+\,q_{0}\sum_{u}d_{F+}(u)^{2}\,-\,3N_{\triangle}(G_{0}^{c})\,\pm\,O(n^{5/2})$

We may now write $d_{F_{-}}(u)=\bar{d}(u)+D_{-}(u)$, as in the previous
subsection. Our expression for $3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}$ becomes

$q_{0}\sum_{u}\big{(}\bar{d}(u)+D_{-}(u)\big{)}^{2}\,+\,q_{0}\sum_{u}\big{(}\bar{d}(u)+D_{+}(u)\big{)}^{2}\,-\,3N_{\triangle}(G_{0}^{c})\,\pm\,O(n^{5/2})\,.$

As $D_{+}(u)=-D_{-}(u)$, the linear term will cancel, leaving

$\displaystyle q_{0}$
$\displaystyle\sum_{u}\big{(}\bar{d}(u)^{2}\,+\,D_{-}(u)^{2}\big{)}\,+\,q_{0}\sum_{u}\big{(}\bar{d}(u)^{2}\,+\,D_{+}(u)^{2}\big{)}\,-\,3N_{\triangle}(G_{0}^{c})\,\pm\,O(n^{5/2})$
$\displaystyle=\,2q_{0}\sum_{u}\bar{d}(u)^{2}\,+\,2q_{0}\sum_{u}D_{-}(u)^{2}\,-\,3N_{\triangle}(G_{0}^{c})\,\pm\,O(n^{5/2})$

We shall now write
$\bar{d}(u)=(n-d_{G_{0}}(u)-1)/2=q_{0}(n-1)/2-D_{G_{0}}(u)/2$. As the linear
term in $D_{G_{0}}(u)$ cancels, our expression for
$3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}$ becomes

$\frac{q_{0}^{3}n^{3}}{2}\,+\,\frac{q_{0}}{2}\sum_{u}D_{G_{0}}(u)^{2}\,+\,2q_{0}\sum_{u}D_{-}(u)^{2}\,-\,3N_{\triangle}(G_{0}^{c})\,\pm\,O(n^{5/2})\,.$

Finally, using that $|D_{-}(u)|\leqslant 2\varepsilon n=O(n^{4/5})$ due to
(P2) (see (5.2)) and (P3) to control to control $|D_{G_{0}}(u)|$, we see that

$3T_{3}\,-\,T_{2}\,-\,T_{1}\,+\,3T_{0}\,=\,\frac{q_{0}^{3}n^{3}}{2}\,-\,3N_{\triangle}(G_{0}^{c})\,\pm\,O(n^{13/5})\,,$

which completes the proof of (6.11).

## References

##  Appendix A Standard Deviations

During Section 3 we defined the following parameter

$\sigma_{p}^{2}\,:=\,\textup{Var}\big{(}S_{G_{p}}^{p}(u,w)\mid uw\not\in
E(G_{p})\big{)}.$

We deduce its value in the following claim.

######  Claim A.1.

$\sigma_{p}^{2}=p^{2}(1-p)^{2}(n-2).$

###### Proof.

First, recall that $\mathbb{E}\left[S_{G_{p}}^{p}(u,w)\mid uw\not\in
E(G_{p})\right]=0$ and hence
$\sigma_{p}^{2}=\mathbb{E}[S_{G_{p}}^{p}(u,w)^{2}\mid uw\not\in E(G_{p})]$. As
$S_{G_{p}}^{p}(u,w)$ can be written as $\sum_{v\in V\setminus\\{u,w\\}}Y_{v}$
where $Y_{v}$ are iid random variables which take values

$\begin{matrix}(1-p)^{2}\qquad&\text{with probability}\qquad&p^{2}\\\
p(1-p)\qquad&&2p(1-p)\\\ p^{2}\qquad&&(1-p)^{2}.\end{matrix}$

Using independence,

$\begin{split}\mathbb{E}[S_{G_{p}}^{p}(u,w)^{2}]\,=\,\mathbb{E}\left[\left(\sum_{v\in
V\setminus\\{u,w\\}}Y_{v}\right)^{2}\right]\,&=\,\sum_{v\in
V\setminus\\{u,w\\}}\mathbb{E}\big{[}Y_{v}^{2}]\\\
&=\,p^{2}(1-p)^{2}(n-2),\phantom{big|}\end{split}$

as claimed. ∎

##  Appendix B Hypergeometrics

The following lemma gives a lower bound for the tail of the hypergeometric
distribution in the case that exactly half of the population count as
“successes”. We remark that now that we are in the appendix we use $p$ for the
density of a random set (and not $m/N$, as in the rest of the article).

######  Lemma B.1.

Let $p,\alpha>0$ and let $M\in\mathbb{N}$ be such that $(1+\alpha)pM$ is an
integer. Let $A$ be a uniformly random subset of $2pM$ elements of $[2M]$.
Then

$\mathbb{P}\left(|A\cap[M]|=(1+\alpha)pM\right)\,\geqslant\,\exp\left(\frac{-p}{1-p}\alpha^{2}M\,-\,\frac{p-2p^{2}+2p^{3}}{(1-p)^{2}}\alpha^{3}M\,\pm\,O(\log{M})\right)\,.$

######  Remark.

In particular, if $\alpha^{3}M\geqslant\log{M}$, then this bound is of the
form $\exp(-p\alpha^{2}M/(1-p)\,+\,O(\alpha^{3}M))$.

###### Proof.

We begin by noting that the probability in question is simply

$\mathbb{P}\left(|A\cap[M]|=(1+\alpha)pM\right)\,=\,\frac{\binom{M}{(1+\alpha)pM}\binom{M}{(1-\alpha)pM}}{\binom{2M}{2pM}}\,.$

We now use Stirling’s approximation $n!\sim\sqrt{2\pi n}(n/e)^{n}$, which
gives, in this context, that

$\binom{n}{an}\,=\,n^{O(1)}\frac{n^{n}}{(an)^{an}(n(1-a))^{n(1-a)}}\,=\,\frac{n^{O(1)}}{a^{an}(1-a)^{(1-a)n}}\,.\phantom{\Bigg{|}}$

And so the probability is given by

$\displaystyle\frac{M^{O(1)}p^{2pM}(1-p)^{2(1-p)M}}{((1+\alpha)p)^{(1+\alpha)pM}((1-\alpha)p)^{(1-\alpha)pM}(1-p-p\alpha)^{(1-p-p\alpha)M}(1-p+p\alpha)^{(1-p+p\alpha)M}}$

We note that the $p$ terms cancel. If we also divide top and bottom by
$(1-p)^{2(1-p)M}$ we obtain

$M^{O(1)}(1+\alpha)^{-(1+\alpha)pM}(1-\alpha)^{-(1-\alpha)pM}\left(1-\frac{p\alpha}{(1-p)}\right)^{-(1-p-p\alpha)M}\left(1+\frac{p\alpha}{(1-p)}\right)^{-(1-p+p\alpha)M}$

which, by the difference of two squares $(1-\alpha^{2})=(1-\alpha)(1+\alpha)$,
becomes

$M^{O(1)}(1-\alpha^{2})^{-(1-\alpha)pM}(1+\alpha)^{-2\alpha
pM}\left(1-\frac{p^{2}\alpha^{2}}{(1-p)^{2}}\right)^{-(1-p-p\alpha)M}\left(1+\frac{p\alpha}{(1-p)}\right)^{-2\alpha
pM}\,.$

As $1+\alpha\leqslant e^{\alpha}$ and $1-\alpha\leqslant e^{-\alpha}$, it
follows that the probability is at least

$\exp\left(\alpha^{2}M\left[p-2p+\frac{p^{2}}{(1-p)}-\frac{2p^{2}}{(1-p)}\right]\,-\,\alpha^{3}M\left[p+\frac{p^{3}}{(1-p)^{2}}\right]\,\pm\,\log{M}\right)$

This simplifies to

$\exp\left(-\alpha^{2}M\left[p+\frac{p^{2}}{(1-p)}\right]\,-\,\alpha^{3}M\left[p+\frac{p^{3}}{(1-p)^{2}}\right]\,\pm\,\log{M}\right)$

which is equal to the desired expression. ∎

We shall only require this much weaker result, which we state as a corollary.

######  Corollary B.2.

Given $\lambda>0$, for all $p\leqslant 1-\lambda$ the following holds. Let $X$
be distributed as the hypergeometric random variable
$\textrm{Hyper}(M,M/2,pM)$ and let $M^{-1/2}\log{M}\ll\alpha\ll 1$. Then, for
all sufficiently large $M$, we have

$\mathbb{P}\left(X=(1+\alpha)pM\right)\,\geqslant\,\exp(-\lambda^{-1}\alpha^{2}M)\,.$

###### Proof.

The random variable $X$ is distributed as $|A\cap[M]|$, the random variable
considered in Lemma B.1. It follows that

$\mathbb{P}\left(X=(1+\alpha)pM\right)\,\geqslant\,\exp\left(\frac{-p}{1-p}\alpha^{2}M\,-\,\frac{p-2p^{2}+2p^{3}}{(1-p)^{2}}\alpha^{3}M\,\pm\,O(\log{M})\right)\,.$

By the conditions on $\alpha$ both the second and third terms are
$o(\alpha^{2}M)$. As the $p/(1-p)<\lambda^{-1}$, the claimed bound holds for
all sufficiently large $M$. ∎

We remark that an alternative proof of Lemma B.1, that would be even more
precise, could be obtained by comparison with the conditioned Binomial
distribution. Let $A_{p}$ be the binomial random subset of $[2M]$ in which
each element is included independently with probability $p$. One may observe
that

$\mathbb{P}\left(|A\cap[M]|=(1+\alpha)pM\right)\,=\,\mathbb{P}\left(|A_{p}\cap[M]|=(1+\alpha)pM\,\mid\,|A_{p}|=2pM\right)\,.$

And so this probability is given by

$\displaystyle\frac{\mathbb{P}\left(|A_{p}\cap[M]|=(1+\alpha)pM,|A_{p}|=2pM\right)}{\mathbb{P}\left(|A_{p}|=2pM\right)}$
$\displaystyle=\,\mathbb{P}\left(|A_{p}|=2pM\,\mid\,|A_{p}\cap[M]|=(1+\alpha)pM\right)\frac{\mathbb{P}\left(|A_{p}\cap[M]|=(1+\alpha)pM\right)}{\mathbb{P}\left(|A_{p}|=2pM\right)}\phantom{Bigg|}$
$\displaystyle=\,M^{O(1)}\,\mathbb{P}\left(|A_{p}\cap[M]|=(1-\alpha)pM\right)\mathbb{P}\left(|A_{p}\cap[M]|=(1+\alpha)pM\right)\,.\phantom{Bigg|}$

One may then understand this probability in terms of the known tail bounds on
the binomial distribution, such as that stated as Theorem 1.13 in [GGS], which
was adapated from [Bah].

††footnotetext: This study was financed in part by the Coordenação de
Aperfeiçoamento de Pessoal de Nível Superior – Brasil (CAPES) – Finance Code
001