1. Introduction
Let G(n,p) be the Erdős–Rényi random graph on the vertex set
$[n]=\{1,2,\ldots,n\}$
, where each edge of
$K_n$
is included independently with probability p. Our interest lies in the random variable
$X_H$
that counts the number of copies of a fixed graph H in G(n, p). The study of subgraph counts goes back to the 1960s with the seminal paper of Erdős and Rényi [
Reference Erdős and Rényi6
], where they showed that the threshold for the appearance of a fixed graph H in G(n, p) is of order
$n^{-1/m(H)}$
, with
$m(H)\;:\!=\;\max\{e(J)/v(J) \;:\; J\subset H\}$
. When p is at the threshold, Barbour [
Reference Barbour1
] and, independently, Karoński and Ruciński [
Reference Karoński and Ruciński14
] showed that
$\mathbb{P}\left(X_H=x\right)$
is asymptotically equal to the probability that a Poisson random variable is equal to x.
The distribution of
$X_H$
past the threshold is also well understood. To explain that, we write
$\mu_H \;:\!=\; \mathbb{E}\left(X_H\right)$
and
$\sigma_H^2 \;:\!=\; \mathbin{{\mathbb{V}}\mkern-2mu{\text{ar}}\left(X_H\right)}$
, and we let
$X_H^{*}\;:\!=\;(X_H-\mu_H)/\sigma_H$
be the normalised subgraph count. We say that
$X_H^{*}$
converges in distribution to a random variable X, or write
$X_H^{*} \xrightarrow{d} X$
for short, if for every
$x \in \mathbb{R}$
we have
$\mathbb{P}\left(X_H^{*} \lt x\right) \to \mathbb{P}\left(X \lt x\right)$
as n tends to infinity. Early developments in this subject (see [
Reference Karoński and Ruciński14, Reference Nowicki and Wierman16
]) culminated in the work of Ruciński [
Reference Ruciński20
], who showed that
$X_H^{*}$
converges in distribution to the standard normal random variable N(0, 1) if and only if
$p \gg n^{-1/m(H)}$
and
$n^2(1-p)\gg 1$
. Later, Barbour, Karoński and Ruciński [
Reference Barbour, Karoński and Ruciński2
] were able to substantially improve the bounds on the error function in the central limit theorem for
$X_H$
. In the 1990s, Janson [
Reference Janson12
] built upon the techniques used in [
Reference Nowicki and Wierman16
] to study central limit theorems for joint distributions of subgraph counts.
A fairly natural question which arises from the work of Ruciński [
Reference Ruciński20
] is whether
$\mathbb{P}\left(X_H = x\right)$
is asymptotically equal to the density of the normal random variable
$N(\mu_{H},\sigma_{H})$
at x, for every x in the support of
$X_H$
. A positive answer for this question has been referred to as a local central limit theorem. In 2015, Röllin and Ross [
Reference Röllin and Ross18
] showed that if
$n^{-1} \ll p = O(n^{-1/2})$
, then a local central limit theorem holds for triangle counts. Later, this result was extended by Gilmer and Kopparty [
Reference Gilmer and Kopparty11
] for triangle counts and every constant
$p \in (0,1)$
. They also conjectured that a local central limit theorem should hold for
$X_H$
for every connected graph H as long as
$p \gg n^{-1/m(H)}$
and
$n^2(1-p)\gg 1$
. Our main theorem below states that indeed the Gilmer–Kopparty conjecture is true for triangle counts by establishing the first local central limit theorem above the so-called
$m_2$
-density threshold – specifically at
$n^{-1/2}$
for triangle counts – and thus closing the gap in the results mentioned above.
Theorem 1·1. Let X be the number of triangles in G(n, p), with
$\mu = \mathbb{E}\left(X\right)$
and
$\sigma^2=\mathbin{{\mathbb{V}}\mkern-2mu{\text{ar}}\left(X\right)}$
, and let
$\varepsilon\in (0,1)$
be any constant. If
$p\in (4n^{-1/2}, 1/2)$
, then
where
$\mathcal{L}$
is the support of
$X^{*}$
.
As mentioned before, a local central limit theorem for triangle counts was obtained by Röllin and Ross [
Reference Röllin and Ross18
] in the range where
$n^{-1} \ll p = O(n^{-1/2})$
. This result was extended by Gilmer and Kopparty [
Reference Gilmer and Kopparty11
] for constant
$p \in (0,1)$
. Our contribution is in the range where
$Cn^{-1/2}\le p \le 1/2$
, for some constant
$C\gt0$
. We believe that the lower bound of p is related, in the general setting, to the so-called
$m_2$
-density. As a consequence of Theorem 1·1, we were also able to obtain a quantitative bound on the
$\ell_1$
-distance between the normalised triangle count
$X^*_{K_3}$
and the associated normal distribution in the regime
$p=\Omega(n^{-1/2})$
.
Theorem 1·2. Let X be number of triangles in G(n, p), with
$\mu = \mathbb{E}\left(X\right)$
and
$\sigma^2=\mathbin{{\mathbb{V}}\mkern-2mu{\text{ar}}\left(X\right)}$
, and let
$\varepsilon\in (0,1)$
be any constant. If
$p \in (4n^{-1/2},1/2)$
, then
\begin{align} {} {} {}\sum \limits_{x\in \mathbb{N}}\left|\thinspace \frac{1}{\sqrt{2\pi \sigma^2}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}- \mathbb{P}\left(X = x\right) \right| = O\left(\dfrac{p^{1/2}}{ n^{1/2-\varepsilon}}\right). {} {}\end{align}
One interesting consequence of a local limit theorem concerns the phenomena called anti-concentration. Since concentration inequalities play a crucial rôle in probabilistic combinatorics, it is compelling to ask how small an interval we can expect a random variable to be in. Theorem 1·1 answers this question by showing that
$\mathbb{P}\left(X=x\right)=O(\sigma^{-1})$
for every
$x \in \mathbb{N}$
. We emphasise that the implied constant in the O-notation is independent of both x and p. Thus, with high probability X is not contained in any fixed interval of length
$o(\sigma)$
.
Corollary 1·1. Let X be number of triangles in G(n, p),
$\sigma^2=\mathbin{{\mathbb{V}}\mkern-2mu{\text{ar}}\left(X\right)}$
and
$\varepsilon \in(0,1)$
be any constant. If
$n^{-1}\ll p\leq 1-\varepsilon$
, then with high probability X is not contained in any fixed interval of length
$o(\sigma)$
.
Local central limit theorems for general subgraph counts were established for p constant. Berkowitz [
Reference Berkowitz3, Reference Berkowitz4
] extended the results of Gilmer and Kopparty [
Reference Gilmer and Kopparty11
] by obtaining quantitative local limit theorems for clique counts when p is constant. More precisely, they showed that the supremum in (1·1) not only goes to zero but decays polynomially fast for clique counts. Around the same time, Fox, Kwan and Sauermann [
Reference Fox, Kwan and Sauermann8, Reference Fox, Kwan and Sauermann9
] showed an almost-optimal anti-concentration result on
$X_H$
for every connected graph H. That is, they showed that if
$p \in (0,1)$
is constant and H is a connected graph, then
$\max_{x \in \mathbb{Z}} \mathbb{P}\left(X_H = x\right) \le \sigma_H^{-1+o(1)}$
. This result was strengthened by Sah and Sawhney [
Reference Sah and Sawhney21
], who obtained a quantitative local central limit theorem for
$X_H$
for every connected graph H and constant
$p \in (0,1)$
. Fortunately for the authors of this paper, their techniques seem to break down at some point as p tends to 0 and new ideas were necessary to establish a local central limit theorem in the sparse range.
In the proof of Theorem 1·1, as in previous approaches [
Reference Berkowitz3, Reference Berkowitz4, Reference Gilmer and Kopparty11, Reference Sah and Sawhney21
], we use the Fourier inversion formula to transform our problem into estimating the difference of characteristic functions of
$X^*$
and of the normal distribution, i.e.
$\big|\mathbb{E}\left(e^{itX^*/\sigma}\right)-e^{-t^2/2}\big|$
for
$t\in[-\pi \sigma, \pi \sigma]$
. For t roughly in the range
$ [-(p^2n)^{1/2},(p^2n)^{1/2}]$
, we apply the Stein’s Method following the steps of Barbour, Karoński and Ruciński [
Reference Barbour, Karoński and Ruciński2
]. For larger values of t, we split this difference using the triangle inequality and the problem is reduced into estimating
$|\mathbb{E}\left(e^{itX^*}\right)|$
for
$t\in [(p^2n)^{1/2},\pi\sigma]$
, which is the core of this paper. In this regime, we use a decoupling trick that allows us to get rid of some dependencies among triangles and compare
$|\mathbb{E}\left(e^{itX^*/\sigma}\right)|$
with the characteristic function of a sum of signed dilated binomials.
The rest of this paper is organised as follows. In Section 2 we prove Theorems 1·1 and 1·2 from our main technical theorems, which analyse the integral of the characteristic function of X across distinct regions of the real line, and we give an overview of their proof; Sections 3, 4 and 5 are dedicated to the proofs of these main technical theorems.
2. Proof of main results and overview
The first step in the proof of Theorem 1·1 is the following theorem, which is a consequence of a result of Barbour, Karoński and Ruciński [
Reference Barbour, Karoński and Ruciński2
, lemma 1] and the so-called Stein’s method [
Reference Ross19
, theorem 3·1]. See Section 4 for a proof. For convenience, we denote by
$\mathcal{N}(x) = ({1}/{\sqrt{2\pi}}e^{-x^2/2})$
the density of the standard normal random variable N(0, 1).
Theorem 2·1. Let X be the number of triangles in G(n, p), with
$\mu = \mathbb{E}\left(X\right)$
and
$\sigma^2=\mathbin{{\mathbb{V}}\mkern-2mu{\text{ar}}\left(X\right)}$
, and let
$K=K(n)\ge 2$
. If
$p \in (n^{-1/2},1/2)$
we have
\[\sup_{x \in \mathcal{L} }\big|\thinspace \mathcal{N}(x)-\sigma\cdot \mathbb{P}\left(X^{*} = x\right) \big| \leq 2\int\limits_{K}^{\pi \sigma}|\mathbb{E}\left(e^{itX^*}\right)|dt+2e^{-K}+ O\left(\frac{K}{np^{1/2}}\right),\]
where
$\mathcal{L}$
is the support of
$X^{*}$
.
In order to bound
$\int\limits_{K}^{\pi \sigma}|\mathbb{E}\left(e^{itX^*}\right)|dt$
, we split the integral into two parts and use our following two theorems, which are the main technical results of our paper. Theorem 2·2 and Theorem 2·3 shall be proven in Sections 5 and 6, respectively.
Theorem 2·2. Let
$n \in \mathbb{N}$
,
$\gamma \in (0,1/8)$
and
$p \in (4n^{-1/2}, 1/2)$
. For every
$(2^{21}p^2n)^{1/2+\gamma}\lt t \lt \sigma/2^{10}$
we have
Theorem 2·3. Let
$n \in \mathbb{N}$
and
$p\in (n^{-1/2},1/2)$
. For every
$\sigma/2^{12} \lt t \le \pi \sigma$
we have
Now we are ready to prove Theorem 1·1.
Proof of Theorem
1·1. As mentioned before, a local central limit theorem for triangle counts was obtained by Röllin and Ross [
Reference Röllin and Ross18
] in the range where
$n^{-1} \ll p = O(n^{-1/2})$
and extended by Gilmer and Kopparty [
Reference Gilmer and Kopparty11
] for constant
$p \in (0,1)$
. Thus, it suffices to show Theorem 1·1 for
$p \in (4n^{-1/2},1/2)$
.
Let
$\gamma \in (0,1/8)$
and set
$K \;:\!=\; (\log n)^{\frac{8}{\gamma}} (p^2 n)^{\frac{1}{2}+\gamma }$
. It follows from Theorem 2·2 and Theorem 2·3 that
\begin{align} {} {} {}\int\limits_{K}^{\pi \sigma}|\mathbb{E}\left(e^{itX^*}\right)|dt & \le \int\limits_{K}^{ \sigma/2^{10}}|\mathbb{E}\left(e^{itX^*}\right)|dt + \sigma\exp(-\Omega(\sqrt{n})) \nonumber\\[5pt] {} {} {}& \le \int\limits_{K}^{ \sigma/2^{10}} e^{-t^{2\gamma}} dt + \exp(-\Omega(\sqrt{n})) \nonumber \\[5pt] {} {} {}& \le {} {} {}\exp(-\Omega(\log n)^{8}). {} {}\end{align}
As
$e^{-K} \le \exp(-(\log n)^8)$
for all sufficiently large n, it follows from Theorem 2·1 combined with (2·1) that
\begin{align*} {} {} {}\sup_{x \in \mathcal{L} }\big|\thinspace \mathcal{N}(x)-\sigma\cdot \mathbb{P}\left(X^{*} = x\right) \big| {} {} {}&\le \exp(-\Omega(\log n)^{8}) + O \left(\dfrac{(\log n)^{\frac{8}{\gamma}} (p^2 n)^{\frac{1}{2}+\gamma }}{np^{\frac{1}{2}}} \right)\\[5pt] &\le n^{-\frac{1}{2}+2\gamma}p^{\frac{1}{2}+2\gamma}. {} {}\end{align*}
Now we are ready to prove Theorem 1·2.
Proof of Theorem
1·2. Let
$\mathcal{L}$
be the support of
$X^{*}=({X-\mu})/{\sigma}$
,
$\gamma \in (0,1)$
and
$M = (\log n)^8$
. We first change variables and split the sum into two parts:
\begin{align} {} {} {}&\sum \limits_{x\in \mathbb{N}}\left|\thinspace \frac{1}{\sqrt{2\pi \sigma^2}}e^{-\frac{(x-\mu)^2}{2\sigma^2}}- \mathbb{P}\left(X = x\right) \right| =\frac{1}{\sigma} {} {} {}\sum \limits_{\substack{x\in \mathcal{L} }}\left|\thinspace \frac{1}{\sqrt{2\pi}}e^{-x^2/2} - \sigma\cdot\mathbb{P}\left(X^* = x\right) \right| \nonumber \\[5pt] {} {} {}& \qquad \quad \le \frac{1}{\sigma}\sum \limits_{\substack{x\in \mathcal{L} \\[5pt] |x| \lt M}}\left|\thinspace \mathcal{N}(x) - \sigma \cdot\mathbb{P}\left(X^* = x\right) \right| + {} {} {}\sum \limits_{\substack{x\in \mathcal{L} \\[5pt] |x| \gt M}} \dfrac{\mathcal{N}(x)}{\sigma} +\mathbb{P}\left(X^* \geq M\right) \nonumber \\[5pt] {} {} {}& \qquad \quad\le O(M n^{-\frac{1}{2}+\gamma}p^{\frac{1}{2}+\gamma}) + e^{-M} + \mathbb{P}\left(|X^*| \ge M\right). {} {}\end{align}
In the last inequality, in the first term we used Theorem 1·1 and that the sum has
$O(\sigma M)$
terms.
We now would like to apply Kim–Vu’s inequality [
Reference Kim and Vu15
] to bound
$\mathbb{P}\left(|X^*| \ge M\right)$
(see Theorem 3A in [
Reference Janson and Ruciński13
] or Theorem 3·3 below). Let
$x_{e}$
denote the indicator function of the event that
$e \in E(G(n,p))$
. We can write X as
where the sum is over all edges
$e,f,g \in E(K_n)$
which form a triangle. For a set
$A \subseteq \{x_{e}\;:\; e \in E(K_n)\}$
, note that the partial derivative
$\partial_{A}(X)$
is a non-zero polynomial if and only if
$A \subseteq \{ x_{e},x_{f},x_{g}\}$
, for some edges e, f, g which form a triangle. By writing
$e=uv$
,
$f=vw$
and
$g=wu$
, we obtain
As
$\partial_{\emptyset}(X)= X$
, it follows from the definition of
$\mathbb{E}_j$
in (3·1) that
$\mathbb{E}_0(X) = O(n^3p^3)$
and
$\mathbb{E}_1(X)=O(np^2)$
. As the variance
$\sigma^2$
of X is of the same order as the expected number of
$K_4^{-}$
when
$p\ge n^{-1/2}$
, we have
$\sigma^2= \Theta(n^4p^5)$
. This implies that
$\mathbb{E}_0(X) \mathbb{E}_1(X) = O(\sigma^2)$
, and hence it follows from Kim–Vu’s inequality that
By combining (2·2) and (2·3), we conclude that the left-hand side of (2·2) is at most
$O(n^{-\frac{1}{2}+2\gamma}p^{\frac{1}{2}+\gamma})$
.
2·1. Proof overview
Our strategy relies on relating the characteristic function of X to that of a sum of independent, weighted Bernoulli random variables. Therefore, in order to reach higher values of t, we must relate X to a sum of Bernoulli random variables with progressively smaller weights.
This motivates the introduction of what we call the
$\alpha$
-function. Let
$G^0$
and
$G^1$
be two independent copies of G(n, p). For and edge e and
$i\in \{0,1\}$
we write
$x_e^i=\unicode{x1D7D9}_{e\in G^i}$
and for a set of edges A, we write
$x_A^i=(x_e^i)_{e\in A}$
. Let
$m=m(n)$
be a positive integer and let
$P_1 \cup P_2 \cup P_3$
be a partition of [n] with
$|P_1|= \lfloor (n-m)/2 \rfloor$
,
$|P_2|= \lceil (n-m)/2 \rceil$
and
$|P_3|=m$
. For simplicity, we set
$A = \{uv\;:\; u \in P_1, v \in P_2\}$
,
$B_i = \{uv\;:\; u \in P_i, v \in P_3\}$
for
$i \in \{1,2\}$
and
$B=B_1\cup B_2$
. We omit the dependencies of these sets on the partition, as they are clear from context. Finally, for
$uv \in A$
define
That is,
$\alpha_f$
is a sum of
$\pm 1$
terms over the common neighbours of f in
$G^0\Delta G^1$
, the symmetric difference between
$G^0$
and
$G^1$
. Note that the expression
$x_{uw}^{0}-x_{uw}^{1}$
assigns value
$+1$
to edges in
$G^0\setminus G^1$
and
$-1$
to edges in
$G^1\setminus G^0$
. Now, define
In Lemma 5·1 we use a decoupling trick to show that
Vaguely speaking, the
$\pm 1$
signs from
$\alpha$
come from replacing the square of the absolute value of a complex number by the product of itself with its conjugate. We aim to show that a constant proportion of the edges
$f\in A$
attain a typical value of
$\alpha_f$
. Even though
$\alpha_f$
has expectation 0, we show that with high probability many
$f\in A$
satisfy
$|\alpha_f| = \Theta (pm^{1/2})$
as long as
$pm^{1/2}$
is a large enough constant. By conditioning on these events, we show inside the proof of Theorem 2·2 that
For this to be integrable with respect to t, m has to be slightly larger than
$p^2n^2/t^2$
. We emphasise that m, which is the size of the part
$P_3$
, can be any parameter between 1 and n and is allowed to be a function of t. On the other hand, we also ask that
$t\alpha_f/2\pi \sigma \leq 1/2$
, as argued before, or equivalently that
$t= O(\sigma/m^{1/2})$
. By decreasing the order of magnitude of m from n to
$1/p^2$
we are then able to show in Theorem 2·2 that
for all
$(p^2n)^{1/2+\gamma}\lt t\lt \sigma/2^{10}$
, for any
$\gamma\gt0$
.
We are only left with the case
$t=\Theta(\sigma)$
. To be able to reach the value of t up to
$\pi \sigma$
we still use the
$\alpha$
function, but we must create a situation where the typical value of
$|\alpha_f|$
is 1. We then explore the role of a single vertex, i.e. the case where
$P_3=\{v\}$
. In this case,
$\alpha$
is just a signed sum over the edges in
$N(v,G^0)\Delta N(v,G^1)$
. Since this set has roughly pn vertices, each of the
$\Theta((pn)^2)$
pairs inside of it are candidates for having its
$|\alpha_f|=1$
. Therefore,
$\alpha$
becomes a sum of roughly
$(pn)^2$
Bernoulli random variables with
$\pm 1$
weights. We use that in the proof of Theorem 2·3 to show that
for all
$\sigma/2^{12} \leq t \leq \pi \sigma$
, which finishes the sketch of proof of Theorem 2·3.
3. Toolbox
In this section, we state the probabilistic tools used in the proof of our main theorem. The first one gives us a bound on the characteristic function of Binomial random variables. For a proof, see Lemma 1 in [
Reference Gilmer and Kopparty11
]. Below,
$\|x\|$
denotes the distance from x to the nearest integer.
Lemma 3·1. Let
$p \in [0,1]$
,
$n \in \mathbb{N}$
and
$t \in \mathbb{R}$
. If B is a p-Bernoulli random variable, then
The next lemma states the well-known Chernoff’s inequality. For a proof, see [ Reference Frieze and Karoński10 , theorem 23·6].
Lemma 3·2 (Chernoff’s inequality). Let Y be a binomial random variable. For every
$t \ge 0$
, we have
Let P be a random polynomial in terms of the indicators
$\{\unicode{x1D7D9}_{e \in G}\;:\; e \in K_n\}$
. For a set
$A \subseteq \binom{[n]}{2}$
, let
$\partial_A P $
be the partial derivative of P with respect to the variables in A. When
$A = \emptyset$
, we simply set
$\partial_A P = P$
. For
$j \in \{0,1,\ldots,\text{deg}(P)\}$
, define
The theorem of Kim and Vu [ Reference Kim and Vu15 ] for random polynomials of degree three can be stated as follows (see [ Reference Janson and Ruciński13 , theorem 3A]).
Theorem 3·3 (Kim–Vu’s inequality). Let P be a random polynomial of degree d whose variables belong to the set
$\{\unicode{x1D7D9}_{e \in G}\;:\; e \in K_n\}$
. For every
$r \gt 1$
, we have
Our last ingredient is the Paley–Zygmund inequality [ Reference Paley and Zygmund17 ], which gives an lower bound for the probability that a random variable is greater than a constant proportion of its expectation.
Theorem 3·4 (Paley–Zygmund inequality). Let
$\theta \in (0,1)$
and
$S \ge 0$
be a random variable with finite variance. Then,
4. Stein’s method
In this section we combine some results surrounding the so-called Stein’s Method [
Reference Ross19
] in the particular case of triangle counts in G(n, p) and use it to prove Theorem 2·1. We define
$\mathcal{W} \;:\!=\; \{ h\;:\;\mathbb{R}\rightarrow \mathbb{R} \;:\; |h(x)-h(y)|\leq |x-y| \text{ }\forall x,y\in \mathbb{R}\}$
to be the set of 1-Lipschitz functions. For random variables X, Y we define
and call it the Wasserstein metric.
Lemma 4·1 [
Reference Ross19
, theorem 3·1]. Let
$\mathcal{F}=\{f\;:\;\mathbb{R}\rightarrow \mathbb{R} \;:\; |f|,|f''|\leq 2, |f'|\leq \sqrt{2/\pi} \}$
. If X is a random variable and N is the standard normal distribution, then
Barbour, Karoński and Ruciński [ Reference Barbour, Karoński and Ruciński2 ] proved a quantitative central limit theorem for subgraph counts in G(n, p) using the Stein’s Method. In one of their intermediate results, they give an upper bound on the right-hand side of the inequality given by Lemma 4·1, which we state below.
Lemma 4·2 [
Reference Barbour, Karoński and Ruciński2
, lemma 1]. Let X be the number of triangles in G(n, p). If
$n^{-\frac{1}{2}} \le p \le 1/2$
then for every bounded function
$f\;:\;\mathbb{R}\rightarrow \mathbb{R}$
with bounded first and second derivatives we have
where
$B=\sup_x|f''(x)|$
.
Let us just briefly explain how to derive our Lemma 4·2 from the results in [
Reference Barbour, Karoński and Ruciński2
]. By combining Lemma 1 in [
Reference Barbour, Karoński and Ruciński2
] with the upper bound on
$\varepsilon$
for triangle counts given by their equation (3.10), we obtain the following result. For every
$n^{-1/2} \le p \le 1/2$
and every bounded function
$f\;:\; \mathbb{R} \to \mathbb{R}$
with bounded first and second derivatives, we have
where
$B=\sup_x|f''(x)|$
,
$\sigma^2 = \mathbin{{\mathbb{V}}\mkern-2mu{\text{ar}}\left(X\right)}$
and
$\psi = \min \{n^{v(H)}p^{e(H)}\;:\; H \subseteq K_3, e(H) \ge 1\}$
. Recall that
$X^{*}$
denotes the random variable
$(X-\mathbb{E}\left(X\right))/\sigma$
. It is not hard to check that if
$n^{-\frac{1}{2}} \le p \le 1/2$
, then
$\psi = \Theta(n^2p)$
and
$\sigma = \Theta(n^2p^{\frac{5}{2}})$
, and hence the right-hand side of (4·1) is
$O(B/(np^{1/2}))$
.
We are now ready to prove Theorem 2·1.
Proof of Theorem
2·1. We start with the well-known Fourier inversion formula for
$X^*$
(for a proof, see [
Reference Feller7
, page 511]), which is
\[\mathbb{P}\left(X^{*}=y\right) = \dfrac{1}{2\pi \sigma} \int \limits_{-\pi \sigma}^{\pi \sigma} e^{-ity}\mathbb{E}\left(e^{itX^*}\right)dt\]
for every y in the support of
$X^{*}$
. It is well known that
\[\mathcal{N}(x)=\frac{1}{2\pi} \int\limits_{-\infty}^{\infty}e^{-itx}e^{-t^2/2}dt.\]
This can be seen by using that the characteristic function of the standard normal random variable N(0, 1) is
$e^{-t^2/2}$
([
Reference Durrett5
, example 3·3·5]) together with the Fourier inversion formula for variables with integrable characteristic function over
$\mathbb{R}$
([
Reference Durrett5
, theorem 3·3·14]).
Now we start the analysis on the main quantity of interest:
\begin{align} {} \big|\thinspace \mathcal{N}(x)-\sigma\cdot \mathbb{P}\left(X^{*} = x\right) \big| \leq \int\limits_{-\pi \sigma}^{\pi \sigma} |\mathbb{E}\left(e^{itX^*}\right)-e^{-t^2/2}|dt + 2\int\limits_{\pi \sigma}^{\infty} e^{-t^2/2}dt. {}\end{align}
We now split the first term on the right-hand side of (4·2) according to the values of K. For
$|t|\gt K$
we use the triangle inequality and the fact that
$|\mathbb{E}\left(e^{itX^*}\right)|$
and
$e^{-t^2/2}$
are even functions to obtain
\begin{equation}\big|\thinspace \mathcal{N}(x)-\sigma\cdot \mathbb{P}\left(X^{*} = x\right) \big| \leq2\int\limits_{K}^{\pi \sigma}|\mathbb{E}\left(e^{itX^*}\right)|dt + \int\limits_{-K}^{K}|\mathbb{E}\left(e^{itX^*}\right)-e^{-t^2/2}|dt + 2\int\limits_{K}^{\infty}e^{-t^2/2}dt.\end{equation}
For the third term on the right-hand side of the equation above we have
\begin{equation} {}\int\limits_{K}^{\infty} e^{-t^2/2}dt\leq \int\limits_{K}^{\infty} \frac{t}{K} e^{-t^2/2}dt = \dfrac{e^{-K^2/2}}{K} \le e^{-K}\end{equation}
for all
$K\ge 2$
.
The characteristic function of the normal distribution is given by
$\mathbb{E}\left(e^{itN}\right)=e^{-t^2/2}$
. By using this and splitting
$\mathbb{E}\left(e^{itX^*}\right)$
and
$\mathbb{E}\left(e^{itN}\right)$
into its real and imaginary parts, we can bound the second term on the right-hand side of (4·3) by
\begin{align*} \int\limits_{-K}^{K} |\mathbb{E}\left(e^{itX^*}\right)-e^{-t^2/2}|dt \leq \int\limits_{-K}^{K} \big|\mathbb{E}\big(\text{cos}(tX^*)-\text{cos}(tN)\big)\big|dt + \int\limits_{-K}^{K} \big|\mathbb{E}\big(\text{sin}(tX^*)-\text{sin}(tN)\big)\big|dt.\end{align*}
As the cosine and sine functions are 1-Lipschitz, for every
$t \in \mathbb{R}$
we have
for both
$h = \cos$
and
$h = \sin$
. Moreover, as cosine and sine have second derivatives bounded by 1, we can combine Lemmas 4·1 and 4·2 to obtain
\begin{equation} \int\limits_{-K}^{K} |\mathbb{E}\left(e^{itX^*}\right)-e^{-t^2/2}|dt = O\left(\frac{K}{np^{1/2}}\right).\end{equation}
Combining the bounds obtained in (4·4) and (4·5) into (4·3) we conclude our proof.
5. The decoupling trick in the regime
$ (p^2n)^{1/2+\gamma}\leq t \leq \sigma/2^{10}$
In this section, we prove Theorem 2·2. Our approach is to first bound
$\left|\mathbb{E}\left[e^{itX/\sigma}\right]\right|$
by relating it to the characteristic function of certain weighted Bernoulli random variables, and then applying Lemma 3·1. Since we expect a constant proportion of the edges in G(n, p) to participate in
$\Theta(np^2)$
triangles, one might initially hope that by revealing some edges of G(n, p), we could bound
$\left|\mathbb{E}\left[e^{itX/\sigma}\right]\right|$
via the characteristic function of a random variable of the form
$\sum_{j=1}^{cn^2} C_j \unicode{x1D7D9}_{\{e_j \in G(n,p)\}},$
where the coefficients
$C_j$
are of order
$\Theta({np^2}/{\sigma})$
. However, this method yields a satisfactory bound only for
$|t| \lt \sigma/(np^2)$
. To address this limitation, we introduce a decoupling trick that connects the triangle count to a finite sum of “signed triangles”. After revealing some of the variables, we are left with a sum of weighted Bernoulli random variables with small coefficients.
5·1. The
$\alpha$
function
We start with some notation. Let
$G^0$
and
$G^1$
be two independent copies of G(n, p) with vertex set [n]. For
$i \in \{0,1\}$
and a set
$A\subseteq \binom{[n]}{2}$
, denote by
$x^i_A$
the vector
$(\unicode{x1D7D9}_{e \in G^i}\;:\; e \in A)$
and by
$x^{0,1}_A$
the concatenation of the vectors
$x^0_A$
and
$x^1_A$
. For a 0-1 random vector y, we write
$\mathbb{E}_{y}$
to denote the expectation operator with respect to y. If y equals
$x^0_{\binom{[n]}{2}}$
or
$x^1_{\binom{[n]}{2}}$
, we omit y from the expectation operator. Finally, for a 0-1 vector x indexed by
$\binom{[n]}{2}$
, we denote
where the summation runs over all triples
$e, f, g \in \binom{[n]}{2}$
that form a triangle.
Let
$m=m(n)$
be a positive integer. We say that a partition
$[n]= P_1 \cup P_2 \cup P_3$
with
$|P_1|= \lfloor (n-m)/2 \rfloor$
,
$|P_2|= \lceil (n-m)/2 \rceil$
and
$|P_3|=m$
is an m-endowed partition of [n]. For simplicity, we set
$A = \{uv\;:\; u \in P_1, v \in P_2\}$
,
$B_i = \{uv\;:\; u \in P_i, v \in P_3\}$
for
$i \in \{1,2\}$
and
$B=B_1\cup B_2$
. We omit the dependencies of these sets on the partition, as they are clear from context. Finally, for
$uv \in A$
define
and
We emphasise that
$\alpha$
does not depend on
$x^1_A$
.
The next lemma uses
$\alpha$
to bound
$|\mathbb{E}\left(e^{itX/\sigma }\right)|$
and is essentially a corollary of Lemma 6 in [
Reference Berkowitz4
]. We include the proof here for completeness. The idea of using two independent copies of G(n, p) to bound
$|\mathbb{E}\left(e^{itX/\sigma }\right)|$
was introduced by Gilmer and Kopparty [
Reference Gilmer and Kopparty11
] and it has been used since then in local central limit theorems for subgraph counts (see [
Reference Berkowitz4, Reference Sah and Sawhney21
]). This is what we refer to as a decoupling trick. Our innovation is to apply this technique by bounding
$|\mathbb{E}\left(e^{itX/\sigma }\right)|$
in terms of
$\alpha$
and by varying m from
$1/p^2$
to
$n/2$
, thereby covering a wider range and dealing with the technical aspects of the sparse regime of G(n, p).
Lemma 5·1. Let
$m \lt n$
be two positive integers and
$P_1\cup P_2 \cup P_3$
be an m-endowed partition of [n]. For every
$t \in \mathbb{R}$
and
$p=p(n)\in (0,1)$
, we have
As
$\alpha$
does not depend on
$x^1_A$
, both sides of the inequality in the lemma above are fixed quantities and not functions of any random variables.
Proof of Lemma 5·1. By the Cauchy–Schwartz inequality, we have
Now, observe that we can write
\begin{equation} {} {} {} {} {} {}\begin{split} {} {} {} {}\left|\mathbb{E}_{x_{B_1}^0} ( e^{it X(x^0) /\sigma})\right|^2 & = {} {} {} {}\mathbb{E}_{x_{B_1}^0} \left( e^{it X(x^0) /\sigma}\right) \cdot \mathbb{E}_{x_{B_1}^0} \left( e^{-it X(x^0) /\sigma}\right)\\[5pt] {} {} {} {}&= \mathbb{E}_{x_{B_1}^0} \left( e^{it X(x^{0}_{B_1^c},x_{B_1}^{0})/\sigma}\right) \cdot \mathbb{E}_{x_{B_1}^1} \left( e^{-it X(x_{B_1^c}^{0},x_{B_1}^{1})/\sigma}\right) \\[5pt] {} {} {} {}& = \mathbb{E}_{x_{B_1}^{0,1}} \left( e^{it( X(x_{B_1^{c}}^{0},x_{B_1}^{0}) - X(x_{B_1^{c}}^{0},x_{B_1}^{1}))/\sigma}\right), {} {} {}\end{split} {} {}\end{equation}
where we denote
$B_1^c \;:\!=\; \binom{[n]}{2} \setminus B_1$
. In the second equality above, we used that
$x^0_{B_1}$
and
$x^1_{B_1}$
independent and identically distributed (i.i.d). In the third equality, we used that
$x^0_{B_1}$
and
$x^1_{B_1}$
are i.i.d. combined with the fact that
$x_{B_1^{c}}^{0}$
does not depend on neither
$x^0_{B_1}$
nor
$x^1_{B_1}$
. To simplify notation, let
$\beta \;:\!=\; X(x_{B_1^{c}}^{0},x_{B_1}^{0}) - X(x_{B_1^{c}}^{0},x_{B_1}^{1})$
. By combining (5·3) and (5·4), we obtain
\begin{equation} {} {} {}\begin{split} {} {} {} {}\left|\mathbb{E}\left(e^{itX(x^0)/\sigma }\right)\right|^2 & \le \mathbb{E}_{x^0_{B_1^c}} \mathbb{E}_{x_{B_1}^{0,1}} ( e^{it \beta/\sigma })\\[5pt] {} {} {} {}& = \mathbb{E}_{x_{B_1}^{0,1}} \mathbb{E}_{x^0_{B_1^c}} ( e^{it \beta/\sigma }). {} {} {}\end{split} {} {}\end{equation}
By representing
$\beta$
as a sum of monomials, one can see that the monomials corresponding to triangles without edges in
$B_1$
are eliminated. Moreover, each triangle of the form uvw with
$v \in P_1$
,
$u \in P_2$
and
$w \in P_3$
gives a contribution of
$x_{uv}^{0}x_{vw}^{0}(x^0_{vw}-x^1_{vw})$
to
$\beta$
. By simplicity, let
$C= \binom{P_1}{2} \cup B_1 \cup \binom{P_3}{2}$
. Thus, we can write
\begin{align} {} {} {}\beta = P\big(x_{C}^{0,1}\big)+ {} {} {}\sum \limits_{\substack{v \in P_1,\\ u \in P_2,\\ w \in P_3}}x_{uv}^{0}x_{uw}^{0}\big(x^0_{vw}-x^1_{vw}\big), {} {}\end{align}
where P is some polynomial.
By applying the Cauchy–Schwartz inequality in (5·5), we obtain
\begin{align} {} {} {}\left|\mathbb{E}\left(e^{itX(x^0)/\sigma }\right)\right|^4 & \le {} {} {}\mathbb{E}_{x_{B_1}^{0,1}} \left|\mathbb{E}_{x^0_{B_1^c}} ( e^{it \beta/\sigma })\right|^2\nonumber\\[5pt] {} {} {}& \le {} {} {}\mathbb{E}_{x_{B_1}^{0,1}} \mathbb{E}_{x^0_{B_1^c \cap B_2^c}} \left|\mathbb{E}_{x^0_{B_2}} ( e^{it \beta/\sigma })\right|^2. {} {}\end{align}
Define
$\tilde{\beta}$
as the polynomial
$\beta$
with the vector
$x_{B_2}^0$
replaced by
$x_{B_2}^1$
. Thus, we have
Similarly as before, the difference
$\beta-\tilde{\beta}$
eliminates all monomials which do not depend on
$B_2$
. In particular,
$P(x_C^{0,1})$
completely disappears. From (5·6) we obtain that
\begin{align} {} {} {}\beta-\tilde{\beta}&= {} {} {}\sum \limits_{\substack{v \in P_1,\\ u \in P_2,\\ w \in P_3}}x_{uv}^{0}\big(x_{uw}^{0}-x_{uw}^{1}\big)\big(x^0_{vw}-x^1_{vw}\big)= \alpha. {} {}\end{align}
Note that
$\alpha$
only uses randomness from
$x_{B_1}^{0,1}$
,
$x_{B_2}^{0,1}$
and
$x_A^0$
. As
$B = B_1 \cup B_2$
and
$A \subseteq B_1^c \cap B_2^c$
, by combining (5·7), (5·8) and (5·9) we obtain
This completes our proof.
5·2. On the typical values of
$\alpha$
Throughout this subsection, all probabilities will be with respect to
$x_B^0$
and
$x_B^1$
, where we recall that
$B = \{vw\;:\; v \in P_1 \cup P_2 \text{ and } w \in P_3\}$
. Let us start by calculating
$\mathbb{E}\left(\alpha_{uv}^2\right)$
for an edge
$uv \in A$
. To simplify notation, we denote
$f=uv$
and for
$j \in P_3$
we write
Note that
$\mathbb{E}\left(X_j\right) = 0 $
and
$X_j,X_{j'}$
are independent whenever
$j\neq j'$
. Moreover,
$X_j^2 = |X_j|$
, as
$X_j$
can only take values in
$\{-1,0,1\}$
. Then, we have
The value of
$\alpha_f^2$
is closely related to the number of common neighbours of a pair of vertices in G(n, p). As we allow p to be of order
$n^{-1/2}$
, it is not true that with high probability we have
$\alpha_f^2 = \Theta(p^2m)$
for every
$f \in A$
. However we are able to show that as long as
$m = \Omega(p^{-2})$
with very high probability we have
$\alpha_f^2 = \Theta(p^2m)$
for a constant proportion of edges in A.
Lemma 5·2. Let
$n, m \in \mathbb{N}$
and
$p = p(n)\in (0,1)$
be such that
$p^{-2}(1-p)^{-2}\le m \le n/2$
. Let
$P_1 \cup P_2 \cup P_3$
be an m-endowed partition of [n] and
$A'\subset A$
be the set of pairs f such that
With probability at least
$1-\exp (-\Omega(n))$
we have
$|A'| \geq |A|/2^{7}$
.
Proof. We start by providing a lower bound for the probability that
$\alpha_f^2 \ge \mathbb{E}\left(\alpha_f^2\right)/2$
. We have
By the Payley–Zigmund inequality (c.f. Theorem 3·2), we have
\begin{equation} {} {} {} {} {} {} \mathbb{P}\left(\alpha_f^2 \ge \dfrac{\mathbb{E}\left(\alpha_f^2\right)}{2}\right) {} {} {}\ge \dfrac{\left(\mathbb{E}\left(\alpha_f^2\right)\right)^2}{4\mathbb{E}\left(\alpha_f^4\right)}= \frac{4p^4(1-p)^4m^2}{\mathbb{E}\left(\alpha_f^4\right)}. {} {}\end{equation}
As the random variables
$(X_j)_{j \in P_3}$
are independent and
$\mathbb{E}\left(X_j^2\right)=\mathbb{E}\left(X_j^4\right)=4p^2(1-p)^2$
, the fourth moment of
$\alpha_f$
is given by
\begin{align*} {} {} {}\mathbb{E}\left(\alpha_f^4\right) &= 6\sum \limits_{i,j \in \binom{P_3}{2}}\mathbb{E}\left(X_i^2 X_j^2\right)+ \sum \limits_{j\in P_3} \mathbb{E}\left(X_j^4\right)\\[5pt] {} {} {}& = 6\binom{m}{2}(\mathbb{E}\left(X_1^2\right))^2+m\mathbb{E}\left(X_1^4\right)\\[5pt] {} {} {}& \le 48 p^4(1-p)^4 m^2 + 4p^2(1-p)^2m \le 2^6 p^4(1-p)^4 m^2. {} {}\end{align*}
In the last inequality, we used that
$p^2(1-p)^2m\ge 1$
. By plugging this into (5·10), we obtain
\begin{align} {} {} {}\mathbb{P}\left(\alpha_f^2 \ge \dfrac{\mathbb{E}\left(\alpha_f^2\right)}{2}\right) \ge 2^{-4}. {} {}\end{align}
Recall the definition of A
′ provided in the statement. By Markov’s inequality we have
$\mathbb{P}\left(\alpha_f^2\ge 2^{5} \mathbb{E}\left(\alpha_f^2\right)\right) \le 2^{-5}$
. We combine it with (5·11) to get that
\begin{align} {} {} {}\mathbb{P}\left(f\in A'\right)\ge \mathbb{P}\left(\dfrac{\mathbb{E}\left(\alpha_f^2\right)}{2} \le \alpha_f^2 \le 2^5\mathbb{E}\left(\alpha_f^2\right) \right) \ge 2^{-4}-2^{-5} = 2^{-5}. {} {}\end{align}
Recall that
$A = \{uv\;:\; u \in P_1, v \in P_2\}$
, where
$|P_1| = \lfloor (n-m)/2 \rfloor$
and
$|P_2| = \lceil (n-m)/2 \rceil$
. Let
$M_1, M_2, \ldots, M_{|P_1|}$
be
$|P_1|$
disjoint matchings of size
$|P_1|$
in A. For each
$i \in [|P_1|]$
, define
$Z_i = \sum_{f \in M_i} \unicode{x1D7D9}_{\{f\in A'\}}$
. Observe that for each
$i \in [|P_1|]$
the collection
$(\unicode{x1D7D9}_{\{f\in A'\}})_{f \in M_i}$
is composed by independent random variables. Then, by Chernoff’s inequality (c.f. Lemma 3·2), we have
for all
$i \in [|P_1|]$
and n sufficiently large. The last inequality follows from (5·12) combined with
$|P_1|\ge (n-m)/4\ge n/8$
. As
$\mathbb{E}\left(Z_i\right)\ge 2^{-5}|P_1|$
, it follows that
with probability at least
$1-n\exp(-2^{-13}n)$
. This proves our lemma.
5·3. Putting pieces together
We now finalise the argument by seeing
$\alpha$
as a sum of independent Bernoullis with weight
$\Theta(\sqrt{p^2m})$
, after revealing the edges in B.
Proof of Theorem
2·2. Let
$p\in(4n^{-1/2},1/2)$
and m be any integer such that
$4/p^2 \le m \le n/2$
. By Lemma 5·1, we have
Define
\[A'=A'(x_B^{0,1}) \;:\!=\; \left\{f\in A \;:\; \alpha_f \in \left(\frac{\sqrt{p^2m}}{2}, 2^{4}\sqrt{p^2m}\right)\right\}.\]
As the set A
′ only depends on the outcome
$x_{B}^{0,1}$
, we have
\begin{align} {} {} {}|\mathbb{E}_{x_A^0} ( e^{it\alpha/\sigma } )| = |\mathbb{E}_{x_{A\setminus A'}^{0}} \mathbb{E}_{x_{A'}^0} ( e^{it\alpha/\sigma } )| & \le \mathbb{E}_{x_{A\setminus A'}^{0}}|\mathbb{E}_{x_{A'}^0} ( e^{it\alpha/\sigma } )| \nonumber \\[5pt] {} {} {} & = \left |\mathbb{E}_{x_{A'}^0} \Big ( e^{it/\sigma \cdot \sum \limits_{f \in A'} \alpha_f x_f^{0} } \Big ) \right |. {} {}\end{align}
In the last equality, we used that
$\alpha = \sum_{f \in A}\alpha_f x_f^0$
and that the random variables
$(x_f^0)_{f \in A}$
are independent, with coefficients
$(\alpha_f)_{f \in A}$
not depending on
$x_A$
. By Lemma 3·1, it follows that
\begin{align*} {} {} {}\left |\mathbb{E}_{x_{A'}^0} \Big ( e^{it/\sigma \cdot \sum \limits_{f \in A'} \alpha_f x_f^{0} } \Big ) \right | \le {} {} {}\prod \limits_{f \in A'} \left(1-8p(1-p)\left \| \dfrac{t\alpha_f}{2\pi \sigma} \right \|^2 \right). {} {}\end{align*}
As
$\alpha_f \le 2^4\sqrt{p^2m}$
for every
$f \in A'$
, we have
$\|t\alpha_f/(2\pi \sigma)\|=t\alpha_f/(2\pi \sigma)$
whenever
$0 \le t \le \pi \sigma/(2^4\sqrt{p^2m})$
. As
$p \le 1/2$
, it follows that
\begin{align} {} {} {}\left |\mathbb{E}_{x_{A'}^0} \Big ( e^{it/\sigma \cdot \sum \limits_{f \in A'} \alpha_f x_f^{0} } \Big ) \right | {} {} {}&\le {} {} {}\exp \left( -\sum \limits_{f \in A'} \dfrac{pt^2\alpha_f^2}{\pi^2 \sigma^2} \right) \nonumber\\[5pt] {} {} {}& \le \exp \left( - \dfrac{t^2p^3m|A'|}{4\pi^2 \sigma^2} \right) {} {}\end{align}
for every
$0 \le t \le \pi \sigma/(2^4\sqrt{p^2m})$
. In the last inequality, we used that
$\alpha_f^2 \ge p^2m/4$
for every
$f \in A'$
. By combining (5·14) and (5·15), we obtain
for every
$0 \le t \le \pi \sigma/(2^4\sqrt{p^2m})$
. In the last inequality, we used that
$\sigma^2 \le n^4p^5$
for
$p \ge 4n^{-1/2}$
.
As
$4n^{-1/2}\le p \le 1/2$
, we have
$\mathbb{E}\left(\alpha_f^2\right) \in (p^2m,4p^2m)$
. Moreover, as
$4/p^2 \le m \le n/2$
, Lemma 5·2 implies that the set A
′ has size at least
$|A'|\ge 2^{-7}|A|\ge 2^{-13}n^2$
with probability at least
$1-\exp(-\Omega(n))$
. By combining with (5·13) with (5·16), it follows that
for every
$0 \le t \le \pi \sigma/(2^4\sqrt{p^2m})$
.
Let
$\delta\in (0,2/5)$
be a constant. The next step is to ensure that the right-hand side of (5·17) decays ‘fast’ if
$ (p^2n)^{\frac{1}{2-\delta}}\lt t\lt\sigma/2^8$
. With this in mind, for each integer
$m \in (4/p^2,n/2)$
we define the interval
\[I_m \;:\!=\; \left(\left(\dfrac{2^{19}p^2n^2}{ m}\right)^{\frac{1}{2-\delta}}, \frac{\sigma}{2^8pm^{1/2}} \right)\]
and set
$I = \cup_{m} I_m$
, where the union is over
$m \in (4/p^2,n/2)\cap \mathbb{N}$
. As
$(\alpha +\beta)^{1/4}\le \alpha^{1/4}+\beta^{1/4}$
for every
$\alpha, \beta \ge 0$
, it follows from (5·17) that for every
$t \in I $
we have
Now, we claim that
$\big((2^{21}p^2 n)^{\frac{1}{2-\delta}},\sigma/2^{10}\big) \subseteq I$
. First, note that the right-hand endpoint of
$I_{\lceil 4/p^2 \rceil}$
is greater than
$\sigma/2^{10}$
and the left-hand endpoint of
$I_{\lfloor n/2 \rfloor}$
is smaller than
$(2^{21}p^2 n)^{\frac{1}{2-\delta}}$
. As the extreme values of
$I_m$
are decreasing in m, it suffices to show that
$I_m\cap I_{m+1} \neq \emptyset$
for every
$m \in (4/p^2,n/2-1)\cap \mathbb{N}$
. This is equivalent to
\begin{align} {} {} {}\left(\dfrac{2^{19}p^2n^2}{ m}\right)^{\frac{1}{2-\delta}} \le \frac{\sigma}{2^8p(m+1)^{1/2}}. {} {}\end{align}
By simplicity, let
$\gamma\gt0$
be such that
$1/2 + \gamma = (2-\delta)^{-1}$
. As
$m \ge 1$
, it follows that
$(m+1)^{1/2}/m^{1/2+\gamma} \le 2^{1/2}$
. Moreover, as
$\sigma \ge 2^{-4}n^4p^5$
, (5·18) holds if
$2^{22+19\gamma} \le (np)^{3-2\gamma}$
, which is true for all
$\gamma \in (0,1)$
and sufficiently large n. As
$\delta \in(0,2/5)$
implies
$\gamma \in (0,1/8)$
and
$\delta \ge 2\gamma$
, we conclude that
for every
$t \in \big((2^{21}p^2 n)^{1/2+\gamma},\sigma/2^{10}\big)$
.
6. The role of a single vertex in the regime
$\sigma/2^{12} \leq t \leq \pi \sigma$
Here we prove Theorem 2·3, which covers the last regime where t has the same order of
$\sigma$
. Recall the definition of
$\alpha_f$
and
$\alpha$
given in (5·1) and (5·2), respectively. Here we still use the
$\alpha$
function as a tool for bounding
$|\mathbb{E}\left(e^{itX/\sigma}\right)|$
, but we consider the case where
$P_3$
consists of a single vertex. As in Section 5·2, we start by proving an analogue of Lemma 5·2. Recall that for an m-partition
$P_1 \cup P_2 \cup P_3$
of [n], we set
$A = \{uv\;:\; u \in P_1, v \in P_2\}$
.
Lemma 6·1. Let
$n \in \mathbb{N}$
,
$P_1 \cup P_2 \cup P_3$
be an 1-endowed partition of [n] and
$p=p(n) \in (0,1/2)$
. Let
$A'\subset A$
be the set of pairs f such that
$|\alpha_f|=1$
. We have
$|A'|\geq(pn)^2/2^4$
with probability at least
$1-\exp(-pn/2^4)$
.
Proof. Let us set
$P_3 = \{w\}$
. For an edge
$f=uv \in A$
we have
In words,
$|\alpha_f|=1$
if and only if u and v are in the symmetric difference of
$N_{G^0}(w)$
and
$N_{G^1}(w)$
, denoted by
$N_{G^0}(w)\Delta N_{G^1}(w)$
. Under the probabilities distributions of
$G^0$
and
$G^1$
, we have that
$|N_{G^0}(w)\Delta N_{G^1}(w)|$
has distribution
$\text{Bin}(n-1, 2p(1-p))$
. Thus, by Chernoff’s inequality (c.f. Lemma 3·2) we obtain
We conclude that the set A
′ of pairs
$f=uv$
such that
$|\alpha_f| = 1$
has size at least
with probability at least
$1-\exp(-pn/2^4)$
, as desired.
Now we are ready to prove Theorem 2·3.
Proof of Theorem
2·3. The proof follows in the same fashion as in the proof of Theorem 2·2. Let
$P_1 \cup P_2 \cup P_3$
be an 1-partition of [n]. Let
$A'\subseteq A$
be the set of pairs f such that
$|\alpha_f|=1$
. Recall that A
′ only depends on
$x_B^{0,1}$
. By combining Lemma 3·1 with Lemma 5·1, we have
\begin{align*} {} {} {}|\mathbb{E}\left(e^{itX/\sigma }\right)|^4 \le \mathbb{E}_{x_B^{0,1}} |\mathbb{E}_{x_{A}^0} ( e^{it\alpha/\sigma } )| {} {} {}&\le \mathbb{E}_{x_B^{0,1}} |\mathbb{E}_{x_{A'}^0} ( e^{it\alpha/\sigma } )|\\[5pt] {} {} {}&\le {} {} {}\mathbb{E}_{x_B^{0,1}} \left (\prod \limits_{f \in A'} \left(1-8p(1-p)\left \| \dfrac{t\alpha_f}{2\pi \sigma} \right \|^2 \right) \right). {} {}\end{align*}
As
$t\leq \pi\sigma$
and
$|\alpha_f|=1$
for
$f\in A'$
, we have
$\| t\alpha_f/(2\pi \sigma)\| = t\alpha_f/(2\pi \sigma)$
. As
$p \le 1/2$
, we obtain
By Lemma 6·1, we have
$|A'| \ge (pn)^2/2^4$
with probability at least
$1-\exp(-pn/2^4)$
. As
$(\alpha +\beta)^{1/4}\le \alpha^{1/4}+\beta^{1/4}$
for every
$\alpha, \beta \ge 0$
and
$p \ge n^{-1/2}$
, it follows from (6·1) that
\begin{align*} {} {}|\mathbb{E}\left(e^{itX/\sigma }\right)| &\le \exp \left(-\dfrac{p^3n^2t^2}{2^{10}\sigma^2}\right)+\exp(-pn/2^6)\\[5pt] {} {}& \le \exp\left(-\Omega(\sqrt{n}) \right), {}\end{align*}
which completes the proof.
Acknowledgements
We would like to thank Rob Morris and Tibor Szabó for helpful suggestions which improved the presentation of this paper. We are also grateful to the referee for their careful reading and insightful comments, which have further refined the manuscript.
















