# Characterizing the fourth-moment phenomenon of monochromatic subgraph counts
via influences

Nitya Mani  and  Dan Mikulincer  Mani & Mikulincer: Department of Mathematics,
MIT<EMAIL_ADDRESS>
###### Abstract.

We investigate the distribution of monochromatic subgraph counts in random
vertex $2$-colorings of large graphs. We give sufficient conditions for the
asymptotic normality of these counts and demonstrate their essential necessity
(particularly for monochromatic triangles). Our approach refines the fourth-
moment theorem to establish new, local influence-based conditions for
asymptotic normality; these findings more generally provide insight into
fourth-moment phenomena for a broader class of Rademacher and Gaussian
polynomials.

##  1\. Introduction

The study of local properties of large-scale graphs plays a pivotal role in
computer science, statistics, and probability. In some cases, such local
properties allow us to infer information about the global structure of the
associated graph [21]. In other cases, restricting to neighborhoods can reduce
the complexity of statistical or computational tasks over the entire graphs
[4]. In this work, we focus on the task of subgraph counting and study the
distribution of monochromatic subgraphs for random vertex colorings.

Consider a sequence of simple undirected graphs $G_{n}=(V(G_{n}),E(G_{n}))$,
with vertex sets $V(G_{n})=\\{1,2,\ldots,v(G_{n})\\}$ and edge sets
$E(G_{n})$. Further, let $H=(V(H),E(H))$ be some connected reference graph.
Our object of study is the _monochromatic subgraph count_ statistic
$T(H,G_{n})$; the number of monochromatic copies of $H$ in $G_{n}$ with a
random vertex coloring. That is, for some $c\in\mathbb{N}$, independently
color each vertex $v\in V(G_{n})$ uniformly at random, using $c$ colors. We
say that a copy of $H$ in $G_{n}$ is monochromatic if all of its vertices have
the same color. The statistic $T(H,G_{n})$ is a sum of simple indicator random
variables, and, depending on the graph structure, these indicators may appear
independent, leading to a central limit theorem. We aim to make this intuition
precise and establish simple (largely necessary and sufficient) conditions on
the underlying graph sequence $G_{n}$ that imply the asymptotic normality of
the statistic $T(H,G_{n})$. (Other settings, where the limiting distribution
is typically not Gaussian, e.g. the Poisson regime or dense $G_{n}$ regime,
have also been studied [8, 7, 2, 5, 10]).

As a motivating example, consider the case where $H=K_{2}$, i.e. $H$ is a
single edge. For a random coloring of $V(G_{n})$, $T(K_{2},G_{n})$ counts the
number of monochromatic edges in $G_{n}$. If we envision $G_{n}$ as describing
say, a social network, then $T(K_{2},G_{n})$ counts the number of pairs of
friends in $G_{n}$ that have the same color, thus generalizing the classical
birthday paradox. Such generalizations were previously studied in a variety of
works [2, 1, 12, 15, 16, 20, 19, 18]. The asymptotic distribution of
$T(K_{2},G_{n})$ exhibits various universality phenomena. In particular, using
the method of moments, Bhattacharya, Diaconis, and Mukherjee [5] concluded
that $T(K_{2},G_{n})$ is asymptotically normal whenever $e(G_{n})\to\infty$
and the fourth moment of a suitably normalized version of $T(K_{2},G_{n})$
converges to $3$ (the fourth moment of the normal distribution).

The principle that a central limit theorem for non-linear functions of random
fields can arise as a consequence of convergence of the corresponding sequence
of fourth moments arises in a variety of problems. The celebrated fourth-
moment phenomenon was first observed for Wiener-Itô stochastic integrals in
[29], and [25] later proved a quantitative version. In subsequent years, the
fourth-moment approach has appeared as a governing principle in the field of
normal approximations. In particular, it has proven widely influential in
proving central limit theorems in the Wiener space111The book [26] provides a
survey on the topic, and the website
https://sites.google.com/site/malliavinstein/home holds an up-to-date list of
related results..

Returning to the problem of monochromatic subgraph counts, beyond edges, the
fourth-moment phenomenon was observed for monochromatic triangles [6] when
$c\geq 5$, and for general monochromatic subgraphs $H$ when $c\geq 30$ [14].
Thus, when $c\geq 30$, in order for $T(H,G_{n})$ to be asymptotically normal,
it is necessary and sufficient that $\mathbb{E}\left[T(H,G_{n})^{4}\right]$
converges to an appropriate quantity. This idea has continued to be
generalized in [9].

It is tempting to expect that sufficiency of the fourth-moment condition
continues to hold with a small number of colors. However, in the
aforementioned results [6, 14], some lower bound on the number of colors turns
out to be necessary for the validity of the fourth-moment phenomenon. The
necessity can be seen in [6, Section 4.2] which provides examples of families
of graphs $(G_{n})_{n\in\mathbb{N}}$, where the fourth moment of a suitably
normalized version of $T(H,G_{n})$ (using $2$ colors) converges to $3$, but
$T(H,G_{n})$ can be readily seen to not be asymptotically normal. These
examples raise the following natural question:

  * _Suppose that the vertices of $G_{n}$ are colored with a small number of colors. Can one find a necessary and sufficient condition on $G_{n}$ to ensure the asymptotic normality of $T(H,G_{n})$?_

It is precisely this question that we tackle, focusing on $c=2$, the smallest
non-trivial number of colors. At the technical level, we refine and leverage
the machinery of the fourth-moment theorem and adapt it to polynomial
functionals of Bernoulli variables. This refinement reveals a new type of
easy-to-verify local properties of $G_{n}$. Combining these properties with
established _global_ moment considerations allows us to distill the above-
mentioned failures of the fourth-moment phenomenon for $T(H,G_{n})$. Our main
contributions are as follows.

  1. (1)

For triangles ($H=\triangle$), we completely characterize the asymptotic
normality of $T(\triangle,G_{n})$. We establish a new _influence_ condition
that together with the fourth-moment condition determines whether
$T(\triangle,G_{n})$ is approximately normal. Our new condition is easy to
check, is combinatorial in nature, and is inspired by the notion of influences
from Boolean analysis. Informally, it requires that a single edge cannot
appear in too many different triangles.

  2. (2)

In the general setting, when $H$ is not a triangle, we show that the influence
condition remains sufficient and conjecture that it is also necessary. We
provide some evidence for this conjecture by relaxing the influence condition.

  3. (3)

We also prove new quantitative convergence rates for the normalized version of
$T(H,G_{n})$. When the influences of the graph are small, our rates turn out
to be faster than the known results in the literature. Our result is rather
general and applies to other related problems, such as monochromatic
hypergraph counts and edge colorings.

  4. (4)

Finally, as a technical tool that may be of independent interest, we extend
the fourth-moment phenomenon to a broader class of Rademacher and Gaussian
polynomials, which do not necessarily belong to a single chaos.

###  1.1. Setup and Main Results

Given a subgraph $H$ and a sequence of graphs $\\{G_{n}\\}_{n\in\mathbb{N}}$,
we shall henceforth use $T(H,G_{n})$ to denote the number of monochromatic
copies of $H$ in $G_{n}$ when we $2$-color the vertices $v\in V(G_{n})$,
uniformly at random, with independent colors
$X_{v}\sim\operatorname{Rad}(\frac{1}{2})$222Here
$\operatorname{Rad}(\frac{1}{2})$ stands for the Rademacher distribution, i.e.
the uniform distribution on $\\{-1,1\\}$.. More formally, we have:

(1.1) $\displaystyle
T(H,G_{n}):=\frac{1}{|\operatorname{Aut}(H)|}\sum_{\mathbf{s}\in
V(G_{n})_{V(H)}}\mathbf{1}\\{X_{=\mathbf{s}}\\}\underbrace{\prod_{(i,j)\in
E(H)}a_{s_{i}s_{j}}(G_{n})}_{=:a_{H,\mathbf{s}}(G_{n})},$

where

  * –

$V(G_{n})_{r}:=\\{\mathbf{s}=(s_{1},\ldots,s_{r})\in V(G_{n})^{r}:s_{i}\text{
distinct}\\}$.

  * –

$\operatorname{Aut}(H)$ is the automorphism group of $H$, the group of vertex
permutations $\sigma$ such that $(i,j)\in E(H)$ if and only if
$(\sigma(i),\sigma(j))\in E(H)$.

  * –

We let $A(G_{n})=(a_{ij}(G_{n}))_{i,j\in V(G_{n})}$ be the adjacency matrix of
$G_{n}$, so that $a_{ij}=\mathbf{1}\\{(i,j)\in E(G_{n})\\}$

  * –

$\mathbf{1}\\{X_{=\mathbf{s}}\\}:=\mathbf{1}\\{X_{s_{1}}=\cdots=X_{s_{r}}\\}$
is the indicator variable that all of the vertices of $\mathbf{s}\in
V(G_{n})_{r}$ have the same color.

Throughout, we assume $H$ is simple and connected and that $v(H)=r\geq 2$. We
denote the centered and rescaled version of $T(H,G_{n})$ by

(1.2) $\displaystyle
Z(H,G_{n}):=\frac{T(H,G_{n})-\mathbb{E}[T(H,G_{n})]}{\sigma_{H}(G_{n})},\quad\sigma_{H}(G_{n}):=\sqrt{\operatorname{Var}[T(H,G_{n})]}.$

We also let

(1.3) $\displaystyle N(H,G_{n}):=\frac{1}{|\operatorname{Aut}(H)|}\sum_{s\in
V(G_{n})_{r}}\prod_{(i,j)\in E(H)}a_{s_{i}s_{j}}(G_{n}),$

be the number of copies of $H$ in $G_{n}.$

The following definition will be instrumental in characterizing the asymptotic
distribution of $Z(H,G_{n})$.

######  Definition 1.1 (Influential vertices and edges).

Given an integer $k\in[r]$ and $\mathbf{w}=(w_{1},\ldots,w_{k})\in
V(G_{n})_{k}$ (ordered) let $D_{\mathbf{w}}(H,G_{n})$ be the number of copies
of $H$ in $G_{n}$ that include vertices $w_{1},\ldots,w_{k}$. More precisely,

(1.4) $\displaystyle
D_{\mathbf{w}}(H,G_{n}):=\frac{1}{\operatorname{Aut}(H)}\sum_{\mathbf{s}\in
V(G_{n})_{r}:\mathbf{s}\supset\mathbf{w}}a_{H,\mathbf{s}}(G_{n}).$

We say that vertex $w\in V(G_{n})$ is an $\varepsilon$-influential vertex if
$D_{w}(H,G_{n})\geq\varepsilon\sigma_{H}(G_{n})$. We say that a pair of
vertices $\mathbf{w}=(w_{1},w_{2})\in V(G_{n})_{2}$ is
$\varepsilon$-influential pair if
$D_{\mathbf{w}}(H,G_{n})\geq\varepsilon\sigma_{H}(G_{n})$. If
$e=\\{w_{1},w_{2}\\}\in E(G_{n})$, we will sometimes also call $\mathbf{w}$ an
$\varepsilon$-influential edge and denote its influence as $D_{e}(H,G_{n})$.

When $\varepsilon$ can be taken to a be constant in $n$, we typically omit the
“$\varepsilon$” and simply refer to collections of vertices as influential. As
we shall show in Lemma 2.3, 1.1 is intimately related to the notion of
influence from Boolean analysis [30, Chapter 2.2]. This notion also bears
similarity to the local counts used in [4] and a similar notion studied in
[27] (discussed further in Section 1.2).

#### Quantitative central limit theorems under a low-influence condition.

Our main idea is to compare $Z(H,G_{n})$ (which turns out to be a polynomial
in Rademacher variables) to a polynomial in Gaussian variables. In some sense,
we replace the $2$-coloring of $G_{n}$ with a continuous Gaussian “coloring”.
This comparison, facilitated by the _Invariance Principle_ of [23], allows us
to invoke known results about central limit theorems for polynomials in
Gaussian spaces. In particular, we shall rely on the fourth-moment theorem of
Nualart and Peccati [29].

The first hurdle we encounter is that known results in Gaussian spaces, such
as the ones in [29], mostly revolve around polynomials belonging to a Wiener
chaos, i.e. Hermite polynomials. Since $Z(H,G_{n})$ is not a Hermite
polynomial in general, we begin by extending the fourth-moment theorem to
certain families of multi-linear polynomials that do not necessarily belong to
a single Wiener chaos. For polynomials belonging to this family, we generalize
the quantitative version of the fourth moment theorem given in [24] to prove
3.2, giving a necessary condition on such polynomials to ensure that the
fourth-moment theorem holds.

Among other examples, 3.2 holds for multi-linear polynomials with positive
coefficients. Since $Z(H,G_{n})$ is such a polynomial, this allows us to
obtain our main quantitative convergence theorem, 3.1, which bounds the
$W_{1}$ and $d_{2}$ distances (defined in Eqs. 2.1 and 2.3) between $Z(H,G)$
and a standard Gaussian in terms of the fourth-moment discrepancy
$\mathbb{E}[Z(H,G_{n})^{4}]-3$ and the maximum influence of a vertex
$\max_{w\in V(G_{n})}D_{w}(H,G_{n}).$

Previous work establishing a fourth-moment theorem $Z(H,G_{n})$ (for
$H=\triangle$ in [6] and for general $H$ in [14]) used martingale central
limit theorems to derive convergence rates in the Kolmogorov distance:

$d_{\mathrm{kol}}(Z(H,G),\mathcal{Z}):=\sup\limits_{t\in\mathbb{R}}\left|\mathbb{P}\left(Z(H,G)\leq
t\right)-\mathbb{P}\left(\mathcal{Z}\leq t\right)\right|,$

where $\mathcal{Z}\sim\mathscr{N}(0,1)$ is a standard Gaussian. Since
$d_{\mathrm{kol}}(Z(H,G),\mathcal{Z})$ can be bounded in terms of $W_{1}$ or
$d_{2}$, informally, when there are no influential vertices, we have the
following consequence of 3.1.

######  Theorem 1.2 (Informal).

Let $\\{G_{n}\\}$ be a sequence of graphs with no influential vertices
(asymptotically) and let $H$ be a fixed connected simple graph. Then,

$d_{\mathrm{kol}}(Z(H,G_{n}),\mathcal{Z})\lesssim\min\left((\mathbb{E}\left[Z(H,G_{n})^{4}\right]-3)^{\frac{1}{12}},\max\limits_{w\in
V(G_{n})}D_{w}(H,G_{n})(\mathbb{E}\left[Z(H,G_{n})^{4}\right]-3)^{\frac{1}{8}}\right).$

Moreover, if $H=\triangle$ is a triangle, we obtain

$d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})\lesssim(\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]-3)^{\frac{1}{8}}.$

######  Remark.

1.2 is based on a rather general convergence result for polynomials in
Rademacher random variables. Thus the obtained bounds also apply, mutatis
mutandis, to similar problems. For example, a similar bound also holds if the
colors are not chosen uniformly, or for variants in which we consider an edge
coloring of $G_{n}$, rather than a vertex coloring, or when allowing $G_{n}$
to be a hypergraph. In another neighboring problem, related to motif
estimation [4], one asks to count the number of monochromatic subgraphs of a
_given_ color. Up to the change in the definition of $Z(H,G_{n})$, the bound
in 1.2 applies to this version verbatim. We further elaborate on this problem
in Section 1.2.

In the setting of $2$-coloring graphs with no influential vertices, we are
able to bypass the difficulties encountered by the previous martingale
arguments. Our result improves on the rates obtained in [14], where the
authors achieved a convergence rate of
$\approx(\mathbb{E}\left[Z(H,G)^{4}\right]-3)^{\frac{1}{20}}$. To our
knowledge, these are the best-known rates in this setting. Notably, 1.2 offers
a substantial improvement when $H=\triangle$, arguably one of the more
fundamental cases. Furthermore, as will be evident from 3.1, our rates further
improve when considering the $W_{1}$ and $d_{2}$ metrics.

#### Characterizing the asymptotic normality of monochromatic triangles counts
with pairwise influences.

In the above result, we impose the sufficient condition that $\\{G_{n}\\}$
lacks influential vertices. There are numerous examples of interest satisfying
this condition, such as vertex-transitive graphs, some sparse graphs, and
certain types of random graphs. However, a moment of thought will reveal that
this condition is not necessary. For example, take $G_{n}$ to be a star on $n$
vertices, and $H=K_{2}$ an edge. Then, as a sum of independent variables
$Z(K_{2},G_{n})\xrightarrow{n\to\infty}\mathcal{N}(0,1)$, yet the middle
vertex is clearly influential. More generally, if each $G_{n}$ has a single
influential vertex, by the symmetry of the colors (and conditioning on the
color of $v$, $X_{v}$), one may see that 1.2 continues to hold for
$Z(H,G_{n})$. Keeping this in mind, one might expect that if all influential
vertices are “sufficiently far away from each other” (and so do not interact
in fourth-moment calculations), then the fourth-moment theorem should continue
to hold. This suggests that the true obstruction of a fourth moment theorem
might be having subsets of nearby vertices $\mathbf{w}$ that are as a
collection, influential.

In our next result, we apply this argument to triangles, when $H=\triangle$.
In this case, we strengthen 3.1 by showing that a necessary and sufficient
condition for the fourth moment theorem to hold is that $G_{n}$ lacks
influential edges.

######  Theorem 1.3.

Consider a sequence of graphs $\\{G_{n}\\}$ with $\mathcal{I}_{n}$ the
corresponding sets of influential vertices, and let
$\sigma_{\triangle}=\sqrt{\mathrm{Var}(T(\triangle,G_{n}))}.$ Suppose that
$\sup_{n}|\mathcal{I}_{n}|<\infty$ and $\mathcal{Z}\sim\mathscr{N}(0,1)$ is a
standard Gaussian.

  1. (1)

If for every $n$, there exists $e\in E(G_{n})$ such that

$\lim\sup_{n\to\infty}\frac{D_{e}(\triangle,G_{n})}{\sigma_{\triangle}}>0$

Then,

$\lim\sup_{n\to\infty}d(Z(\triangle,G_{n}),\mathcal{Z})>0.$

  2. (2)

Conversely, let $M_{n}:=\max\limits_{e\in
E(G_{n})}\frac{D_{e}(\triangle,G_{n})}{\sigma_{\triangle}}.$ Then, for
$\mathcal{Z}\sim\mathscr{N}(0,1)$,

$d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})\lesssim\left(M_{n}^{\frac{1}{2}}+(\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]-3)\right)^{\frac{1}{5}}.$

Putting 1.3 in words, as long as the number of influential vertices is bounded
uniformly over $n$, for $Z(\triangle,G_{n})$ to be asymptotically normal, it
is _necessary and sufficient_ that $G_{n}$ contains no influential edges and
that $\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]\xrightarrow{n\to\infty}3.$
Thus, 1.3 gives a complete characterization of sequences $\\{G_{n}\\}$ for
which the monochromatic triangle count is approximately normal. We remark that
1.3 includes the additional condition of having a bounded number of
influential vertices. We regard this as a technical condition that seems to be
an artifact of the proof of necessity.

#### Towards a characterization of general monochromatic subgraph counts.

Regarding more general subgraph counts, we establish sufficiency of having no
influential pairs. Since every vertex participating in an influential pair is
necessarily an influential vertex, this condition is weaker than the condition
imposed by 1.2, thus yielding a stronger result.

######  Theorem 1.4.

Consider a sequence of graphs $\\{G_{n}\\}$, a graph $H$, and let
$\sigma_{H}=\sigma_{H}(G_{n}).$ If $M_{n}:=\max\limits_{\mathbf{w}\in
V(G_{n})_{2}}\frac{D_{\mathbf{w}}(\triangle,G_{n})}{\sigma_{H}},$ then, for
$\mathcal{Z}\sim\mathscr{N}(0,1)$,

$d_{\mathrm{kol}}(Z(H,G_{n}),\mathcal{Z})\lesssim\left(M_{n}^{2}+(\mathbb{E}\left[Z(H,G_{n})^{4}\right]-3)\right)^{\frac{1}{20}}.$

We now discuss possible generalizations of the first part of 1.3. Our proof of
the necessity condition for triangles proceeds by representing
$Z(\triangle,G_{n})$ as a quadratic polynomial in Rademacher variables. Such a
quadratic representation is absent for general $H$ and so there is no way to
generalize the proof verbatim. However, we conjecture that some adaptation to
polynomials of higher degree should exist and that the above phenomenon holds
more generally:

######  Conjecture 1.5.

Given a fixed graph $H$ and graph sequence $\\{G_{n}\\}$, if for all $N$,
there exists some $n>N$ such that $G_{n}$ has an influential pair of vertices
$\mathbf{w}=(v,w)\in V(G_{n})_{2}$, then
$Z(H,G_{n})\centernot{\xrightarrow{\text{in law}}}\mathscr{N}(0,1)$.

We believe that a careful case analysis of possible tail behaviors of
polynomials in Rademacher variables is the key to proving 1.5. While such an
analysis seems to be beyond the scope of this work, we provide some evidence
for its validity. In 5.8 we show that the conjecture holds with respect to a
stronger notion of influence. In this stronger notion, we ask that a single
pair of vertices be incident to a constant fraction of the copies of $H$ in
$G_{n}$.

One possible approach to prove 1.5 is to establish some discrepancy between
lower-order moments of $Z(H,G_{n})$ and the standard Gaussian. However, the
counterexamples to the fourth-moment phenomenon in [6] are all graphs with a
single influential pair, where
$\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]=3$, in line with 1.3. In
Section 5.3 we show that trying to look at higher fixed moments is likely also
doomed to fail. We provide an explicit construction of a graph containing an
influential edge, such that $Z(\triangle,G_{n})$ matches the first $6$ moments
of the standard Gaussian but where $Z(\triangle,G_{n})$ is not asymptotically
Gaussian. The implication here is that a solution to 1.5 should probably look
at more refined statistics of $Z(H,G_{n})$ which capture the actual behavior
of the tails.

There is another natural approach to try which leads to a very natural
question. When $c\geq 30$, using the results from [4], it is not hard to show
that the existence of an influential pair implies
$\mathbb{E}\left[Z(H,G_{n})^{4}\right]-3>\varepsilon>0$. Hence with many
colors, an influential pair precludes a CLT. This begs the following question
about the monotonicity of the CLT with respect to the number of colors.

######  Question 1.6.

Let $c^{\prime},c\in\mathbb{N}$ with $c^{\prime}>c$, and suppose that when
using $c$ colors, $Z(H,G_{n})\xrightarrow{\text{in law}}\mathscr{N}(0,1).$ Is
it still true that $Z(H,G_{n})\xrightarrow{\text{in law}}\mathscr{N}(0,1),$
when the vertices of $G_{n}$ are colored using $c^{\prime}$ colors instead?

A positive answer to 1.6 coupled with the previous observation would provide a
positive answer to 1.5. It seems plausible that 1.6 is true; the more colors
used the lower in magnitude the correlations between the different copies of
$H$ in $G_{n}$. Common wisdom about the CLT suggests that it should be easier
to approximate $Z(H,G_{n})$ by a Gaussian in this case.

###  1.2. Related Works

The idea of representing $Z(H,G_{n})$ as a polynomial in Rademacher variables
appeared before in [5]. In the paper, the authors observed that for
monochromatic edges, the fourth-moment phenomenon for $Z(K_{2},G_{n})$ could
be reduced to a fourth-moment phenomenon for a homogeneous quadratic
polynomial in Rademacher variables. Note, however, that in light of 1.4, there
is a qualitative difference between counting monochromatic edges and any other
shape. When $H=K_{2}$, and $e(G_{n})\to\infty$, no edge is influential.

More generally, fourth-moment theorems for polynomials in Rademacher random
variables were studied before in [17] (see also [11] for an earlier result).
In the paper, the authors focus on _homogeneous_ polynomials and employ a
discrete variant of the Malliavin calculus to derive comparable bounds to our
3.1. Notably, the maximal influence also plays an important role in their
results. Using similar techniques, the paper [33] later extended the
convergence result to a multivariate setting in the asymptotic regime. As our
approach is different and relies on the Invariance Principle, we are able to
address a somewhat more general setting and consider non-homogeneous
polynomials. Not only that, by restricting our attention to polynomials
induced by monochromatic subgraph counts we identify the pairwise influence
condition from 1.3 and 1.4, rather than the single variable influence, as the
main quantity governing the validity of the central limit theorem.

We finish by discussing the related problem of subgraph sampling and motif
estimation. In this problem, given a large graph $G$ and a reference graph
$H$, one wishes to estimate the $N(H,G)$. To reduce the complexity, a natural
approach is to subsample the vertices of $G$ with some probability $p$ and
obtain a new graph $\tilde{G}$. It is then a standard procedure to obtain an
unbiased estimator for $N(H,G)$ from $N(H,\tilde{G})$. To make the connection
with the present setting, when coloring $G$ with $c$ colors, we take
$p=\frac{1}{c}$, and $N(H,\tilde{G})$ becomes the number of monochromatic
copies of $H$ of a _given_ fixed color. Thus, the subgraph sampling statistic
is an asymmetric version of the monochromatic subgraph count statistic. From a
statistical point of view, for a sequence of graphs $\\{G_{n}\\}$,
establishing the asymptotic normality of $N(H,\tilde{G_{n}})$ is important for
applications such as hypothesis testing.

The asymptotic normality of $N(H,\tilde{G_{n}})$ was extensively studied in
[4], where the authors proved a fourth-moment theorem when $c\geq 20$
(equivalently when $p\leq\frac{1}{20}$). Similar to the case of monochromatic
subgraphs, this result leaves open the question of asymptotic normality for
small $c$. When $c=2$, as mentioned above, $N(H,\tilde{G_{n}})$ can also be
represented as a polynomial in Rademacher variables, and so Theorem 3.1
applies almost verbatim. We thus get a fourth-moment theorem when $G$ does not
have influential vertices. In contrast to our problem, due to the asymmetric
nature of $N(H,\tilde{G_{n}})$ we do not expect that the existence, or lack,
of an influential pair, will play an important role. As an example, consider
$G_{n}$ a star on $n$ vertices, which has an influential vertex and no
influential pairs, and $H=K_{2}$ an edge. It is readily seen that
$N(H,\tilde{G_{n}})$ is not asymptotically normal. For $N(H,\tilde{G_{n}})$,
it seems reasonable to expect that the fourth-moment phenomenon will be
completely determined by the existence of influential vertices.

### Acknowledgements

We are grateful to Elchanan Mossel for enlightening discussions concerning the
Invariance Principle and for being involved in the early stages of this
project. We also thank Sayan Das and Zoe Himwich for helpful discussions. NM
was supported by a Hertz Graduate Fellowship and the NSF GRFP DMS #2141064.

##  2\. Preliminaries

### Notation

Let us first fix some notation we shall use in the sequel. Throughout
$\\{G_{n}\\}$ is a sequence of simple undirected graphs, with
$G_{n}=(V(G_{n}),E(G_{n}))$ having $v(G_{n})$ vertices and $e(G_{n})$ edges.
We assume $e(G_{n})\to\infty$ and take $H$ to be a simple connected graph on
$r$ vertices and view $r$ as fixed when $n\to\infty$. We denote by
$V(G_{n})_{r}$ the set of ordered $r$-tuples of distinct vertices from
$G_{n}$. We take $T(H,G_{n}),Z(H,G_{n}),$ and $N(H,G_{n})$ as defined in Eq.
1.1, Eq. 1.2, and Eq. 1.3 respectively.

We use $a(n)\lesssim b(n)$ to denote that there is some constant $C>0$ such
that $a(n)\leq Cb(n)$ for all $n$ and define $a(n)\gtrsim b(n)$ analogously.
We allow the implicit constant $C$ to depend on the graph $H$ and its size
$r$, but not on other parameters such as $n$, or the graph $G_{n}$. For
$k\in\mathbb{N}$ we set $[k]=\\{1,2,\ldots,k\\}$, and for a set $S$ we denote
by $\binom{S}{m}$ the collection of unordered $m$-subsets of $S$, and by
$\binom{S}{\leq m}$ the collection of unordered subsets of $S$ of size at most
$m$.

###  2.1. Normal Approximations for Polynomials

Our aim in this section is to introduce some background and useful results
concerning the central limit theorem for polynomial functionals. While some of
the mentioned results hold in greater generality, we shall only focus on
multi-linear polynomials with either Gaussian or Rademacher variables, as
required in our setting. For this, we shall use the standard index notation
for multi-linear polynomials.

For $I\subset[n]$ an index set, and $x=(x_{1},\dots,x_{n})\in\mathbb{R}^{n}$,
we set $x^{I}=\prod\limits_{i\in I}x_{i}$. Thus, every multi-linear polynomial
$F:\mathbb{R}^{n}\to\mathbb{R}$ of degree $d$ can be written as,
$F(x)=\sum\limits_{|I|\leq d}\alpha_{I}x^{I}$, where $\\{\alpha_{I}\\}$ are
some set of coefficients. If $F$ is homogeneous of degree $d$, then
$\alpha_{I}=0$ whenever $|I|<d$.

The first result we present is the fourth-moment theorem of Nualart and
Peccati [29]. In our setting, the theorem deals with a sequence
$\\{F_{k}\\}_{k\geq 0}$ of homogeneous multi-linear polynomials of degree $d$
and an $n$-dimensional standard Gaussian vector $\mathcal{N}$. According to
the theorem, as $k\to\infty$, $F_{k}(\mathcal{N})$ converges in law to a
Gaussian if and only if
$\mathbb{E}\left[F_{k}(\mathcal{N})^{2}\right]\xrightarrow{k\to\infty}\sigma^{2}$,
for some $\sigma>0$, and
$\mathbb{E}\left[F_{k}(\mathcal{N})^{4}\right]\xrightarrow{k\to\infty}3\sigma^{4}$.
The quantity $3\sigma^{4}$ is precisely the $4^{\mathrm{th}}$ moment of a
Gaussian with variance $\sigma^{2}$. In this regard, the upshot of the theorem
is the following: a priori, a central limit theorem for $F_{k}(N)$
necessitates the convergence of all moments; however, as long as the variance
stabilizes, it suffices for the $4^{\mathrm{th}}$ moment to converge.

We shall require a quantitative and multivariate form of the fourth-moment
theorem, as it appears in [24]. To state this quantitative version we first
need to introduce the Wasserstein distance (the reader is referred to [32,
Chapter 6] for an in-depth exposition of Wasserstein distances). If $X$ and
$Y$ are two random vectors in $\mathbb{R}^{m}$, we define their Wasserstein
distance as,

(2.1) $W_{1}(X,Y):=\inf\limits_{(X,Y)}\mathbb{E}\left[\|X-Y\|\right],$

where the infimum runs over all couplings of $X$ and $Y$, that is, random
vectors in $\mathbb{R}^{2m}$ whose marginals on the first (resp. last) $m$
coordinates have the same law as $X$ (resp. $Y$). According to the Kantrovich-
Rubinstein duality, the Wasserstein distance can also be formulated as the
divergence over all $1$-Lipschitz functions,

(2.2)
$W_{1}(X,Y)=\sup\limits_{\begin{subarray}{c}f:\mathbb{R}^{m}\to\mathbb{R}\\\
f\text{ is
}1\text{-Lipschitz}\end{subarray}}\left|\mathbb{E}\left[f(X)\right]-\mathbb{E}\left[f(Y)\right]\right|.$

In light of this characterization, we shall also consider the weaker and
smoother $d_{2}$ distance:

$d_{2}(X,Y)=\sup\limits_{\begin{subarray}{c}f:\mathbb{R}^{m}\to\mathbb{R}\\\
\|f\|_{C_{2}}\leq
1\end{subarray}}\left|\mathbb{E}\left[f(X)\right]-\mathbb{E}\left[f(Y)\right]\right|.$

Above $\|f\|_{C_{2}}:=\max\\{\|\nabla
f\|_{\infty},\|\nabla^{2}f\|_{\infty}\\}.$ In other words, $\|f\|_{C_{2}}\leq
1$ implies that $f$ and $\nabla f$ are $1$-Lipschitz. By (2.2) it is now clear
that,

(2.3) $d_{2}(X,Y)\leq W_{1}(X,Y).$

As will be soon evident, when dealing with random variables having small
variances, it is sometimes beneficial to use the $d_{2}$ distance over the
Wasserstein distance. For monochromatic subgraph counts, the $d_{2}$ distance
will help us deal with influential shapes. A key property of both distances is
that convergence in $W_{1}$, and hence also in $d_{2}$, implies convergence in
law.

######  Theorem 2.1.

[24, Theorem 1.5]. Let $m\geq 1$, and for $i\in[m]$, let
$F_{i}:\mathbb{R}^{n}\to\mathbb{R}$ be a homogeneous multi-linear polynomial
of degree $d_{i}>0$, with $d_{i}\neq d_{j}$ for $i\neq j$. Further let
$\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{m})$, and define the $m\times m$
diagonal matrix
$\Sigma:=\mathrm{diag}\left(\mathbb{E}\left[F_{1}(\mathcal{N})^{2}\right],\dots,\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]\right)$.
Taking
$\widetilde{F}:=(F_{1}(\mathcal{N}),\dots,F_{m}(\mathcal{N}))\in\mathbb{R}^{m}$
and $\widetilde{\mathcal{N}}\sim\mathscr{N}(0,\Sigma)$, if we let

$\displaystyle\Delta(F):=$
$\displaystyle\Bigg{[}\sum\limits_{i=1}^{m}\sqrt{2d_{i}4^{d_{i}}\left(\mathbb{E}\left[F_{i}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{i}(\mathcal{N})^{2}\right]^{2}\right)}$
$\displaystyle+$ $\displaystyle\sum\limits_{i\neq
j}\bigg{(}\sqrt{2\mathbb{E}\left[F_{j}(\mathcal{N})^{2}\right]}\left(\mathbb{E}\left[F_{i}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{i}(\mathcal{N})^{2}\right]^{2}\right)^{\frac{1}{4}}$
$\displaystyle\ \ \ \ \ \ \
+d_{j}2^{d_{j}}\sqrt{2(d_{i}+d_{j})!\left(\mathbb{E}\left[F_{i}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{i}(\mathcal{N})^{2}\right]^{2}\right)}\bigg{)}\Bigg{]},$

then

$\displaystyle W_{1}(\widetilde{F},\widetilde{N})$
$\displaystyle\leq\sqrt{\|\Sigma\|_{\operatorname{op}}}\cdot\|\Sigma^{-1}\|_{\operatorname{op}}\cdot\Delta(F),$
$\displaystyle d_{2}(\widetilde{F},\widetilde{N})$
$\displaystyle\leq\Delta(F).$

######  Remark.

We remark that 2.1 is more general and applies to Hermite polynomials, or
iterated stochastic integrals, on the Wiener space. Since multi-linear and
homogeneous polynomials are also Hermite polynomials we chose to state the
theorem this way, with slightly worse but simpler constants, as best befits
our needs.

The fourth moment theorem (2.1) deals with a Gaussian approximation of
polynomials with Gaussian variables. However, in our problem, $T(H,G)$ is a
polynomial in Rademacher random variables. We are thus interested in studying
the law of $F(X)$ when $F:\mathbb{R}^{n}\to\mathbb{R}$ is some multi-linear
polynomial and $X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes n}$ is an
$n$-dimensional random vector with independent Rademacher entries. As it turns
out, the Gaussian is universal for this problem, in the sense that if
$F(\mathcal{N})$ is approximately Gaussian, then the same is also true for
$F(X)$, c.f. [27]. The converse is not true in general though, and one can
find a polynomial $F$, such that $F(X)$ can be well approximated by a
Gaussian, while $F(\mathcal{N})$ cannot. It is precisely these kinds of
polynomials which we shall need to handle. To distinguish between the
different cases, our main tool will be the Invariance Principle of Mossel,
O’Donnell, and Oleszkiewicz [23].

Before stating the theorem, for a multi-linear polynomial
$F:\mathbb{R}^{n}\to\mathbb{R}$, $F(x)=\sum\limits_{|I|\leq
d}\alpha_{I}x^{I}$, we define the _influence_ of a subset $J\subseteq[n]$ of
variables, as

(2.4) $\mathrm{inf}_{J}(F)=\sum\limits_{J\subseteq I}\alpha_{I}^{2}.$

If $J=\\{i\\}$ is a singleton, we will also write
$\mathrm{inf}_{J}(F)=\mathrm{inf}_{i}(F).$ The Invariance Principle then says
that as long as there are no influential variables, $F(\mathcal{N})$ and
$F(X)$ behave roughly the same.

######  Theorem 2.2.

[30, Corollary 11.68] Let $F:\mathbb{R}^{n}\to\mathbb{R}$ be a multi-linear
polynomial of degree $d$ and let
$\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{n})$ and
$X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes n}$. Then, if
$\mathrm{Var}(F(\mathcal{N}))=1$,

$W_{1}(F(X),F(\mathcal{N}))\lesssim
2^{d}\left(\max\limits_{i\in[n]}\mathrm{inf}_{i}(F)\right)^{\frac{1}{4}}.$

###  2.2. Monochromatic Counts as Multi-linear Polynomials

We shall now show how the monochromatic count $T(H,G)$ can be represented as a
multi-linear polynomial. To see this, for a fixed _connected_ graph $H$ on
vertex set $V(H)$, and $r:=v(H)$ we define the $H$-indicator polynomial,
$\mathbb{I}_{H}:\mathbb{R}^{r}\to\mathbb{R}$. For the definition of
$\mathbb{I}_{H}$, we index the coordinates of $\mathbb{R}^{r}$ by $V(H)$, and
write

$\mathbb{I}_{H}(x):=\prod\limits_{v\in
V(H)}(x_{v}+1)+(-1)^{r}\prod\limits_{v\in
V(H)}(x_{v}-1)=2\sum\limits_{i=0}^{\lfloor\frac{r}{2}\rfloor}\sum\limits_{\begin{subarray}{c}U\subset
V(H)\\\ |U|=2i\end{subarray}}\prod\limits_{u\in U}x_{u}.$

The equality follows by noticing that all odd-degree monomials must vanish.

We now record several facts concerning the polynomial $\mathbb{I}_{H}$. First,
it is a multi-linear polynomial of degree at most $r$, and its $m$-homogeneous
component is given by

(2.5)
$\mathbb{I}_{H,m}(x)=\begin{cases}2\sum\limits_{\begin{subarray}{c}U\subset
V(H)\\\ |U|=m\end{subarray}}\prod\limits_{u\in U}x_{u}&m\equiv 0\pmod{2}\\\
0&m\equiv 1\pmod{2}.\end{cases},$

Second, it is indeed an indicator in the following sense: when restricted to
$2$-colorings of $H$, encoded by $x\in\\{\pm 1\\}^{r}$, we have
$\mathbb{I}_{H}(x)=2^{r}$ if $x=\mathbf{1}=(1,\dots,1)$ or $x=-\mathbf{1}$,
and $\mathbb{I}_{H}(x)=0$ otherwise. Finally, $\mathbb{I}_{H}$ does not depend
on the actual graph structure of $H$, only on the number of vertices of $H$,
and is invariant to permutations of its coordinates. We note here that if
$X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes r}$, then

(2.6) $\mathbb{E}[\mathbb{I}_{H}(X)]=\mathbb{I}_{H,0}=2.$

######  Example.

Suppose that $H=\triangle$ is a triangle on the vertex set $\\{u,v,w\\}$. In
that case

(2.7)
$\mathbb{I}_{\triangle}(x_{u},x_{v},x_{w})=2(x_{u}x_{v}+x_{u}x_{w}+x_{v}x_{w}+1).$

It is easy to see that
$\mathbb{I}_{\triangle}(\mathbf{1})=\mathbb{I}_{\triangle}(-\mathbf{1})=8$,
and that $\mathbb{I}_{\triangle}(-1,1,1)=0$, with the same being true for all
other $2$-colorings.

With this definition of $\mathbb{I}_{H}$, we can now rewrite (1.1) as,

(2.8) $T(H,G):=\frac{1}{2^{r}|\operatorname{Aut}(H)|}\sum_{\mathbf{s}\in
V(G)_{r}}\mathbb{I}_{H}(x|_{\mathbf{s}})a_{H,\mathbf{s}}(G),$

where $x|_{\mathbf{s}}=(x_{v})_{v\in\mathbf{s}}$. Equivalently, if
$\mathcal{H}(G)$ stands for the set of all (unlabeled) copies of $H$ inside
$G$ and $x\in\\{\pm 1\\}^{v(G)}$ is a $2$-coloring of $V(G)$ we can also write
$T(H,G)$ in a more standard polynomial form as

$F_{H,G}(x)=\frac{1}{2^{r}}\sum\limits_{\mathbf{s}\in\mathcal{H}(G)}\mathbb{I}_{H}(x|_{\mathbf{s}}).$

Note that the choice of ordering in $\mathbf{s}$ does not matter, since
$\mathbb{I}_{H}$ is invariant to permutations of its coordinates. In light of
2.2, our next goal is to understand the influences of $F_{H,G}(x)$. Since the
entries of $x$ are indexed by $V(G)$, we can identify index sets of $F_{H,G}$
and subsets $\mathbf{w}\subset V(G)$ and write in multi-linear form,

$F_{H,G}(x)=\sum\limits_{\mathbf{w}\in{\binom{V(G)}{\leq
r}}}\alpha_{\mathbf{w}}x^{\mathbf{w}}.$

Let us now express $\alpha_{\mathbf{w}}$ in terms of the graph structure of
$G$. Looking at (2.5), it is clear that when $|\mathbf{w}|$ is even,
$x^{\mathbf{w}}$ appears in the sum precisely once for every copy of $H$ in
$G$ that includes $\mathbf{w}$. In other words,
$\alpha_{\mathbf{w}}=\frac{1}{2^{r-1}}D_{\mathbf{w}}(H,G)$, as in (1.4). When
$|\mathbf{w}|$ is odd then $\alpha_{\mathbf{w}}=0$, and we obtain the
expression,

(2.9) $F_{H,G}(x)=\frac{1}{2^{r-1}}\sum\limits_{i=0}^{\lfloor
r/2\rfloor}\sum\limits_{\mathbf{w}\in\binom{V(G)}{2i}}D_{\mathbf{w}}(H,G)x^{\mathbf{w}}.$

We can now make the connection between the influence of a single variable, as
defined by (2.4), and the influence of a vertex, as in (1.4).

######  Lemma 2.3.

With the above notation, for any $v\in V(G)$,

$\mathrm{inf}_{v}(F_{H,G})\leq\frac{1}{2^{r-1}}D^{2}_{v}(H,G).$

###### Proof.

From the representation in (2.9) we get,

$\mathrm{inf}_{v}(F_{H,G})=\frac{1}{4^{r-1}}\sum\limits_{\begin{subarray}{c}v\in\mathbf{w}\\\
|\mathbf{w}|\equiv 0\text{ mod }2\end{subarray}}D^{2}_{\mathbf{w}}(H,G).$

By inclusion, it is also clear that for any $\mathbf{w}\in V(G)$ that contains
$v$, $D_{\mathbf{w}}(H,G)\leq D_{v}(H,G)$. Moreover, for any $m\leq r$,

$\sum\limits_{\begin{subarray}{c}v\in\mathbf{w}\\\
|\mathbf{w}|=m\end{subarray}}D_{\mathbf{w}}(H,G)=\binom{r-1}{m-1}D_{v}(H,G).$

The coefficient $\binom{r-1}{m-1}$ counts the number of ways $v$ can be
extended to a subset of size $m$ inside a copy of $H$. Combining the above
observations,

$\mathrm{inf}_{v}(F_{H,G})\leq\frac{D_{v}(H,G)}{4^{r-1}}\sum\limits_{i=1}^{r/2}\sum\limits_{\begin{subarray}{c}v\in\mathbf{w}\\\
|\mathbf{w}|=2i\end{subarray}}D_{\mathbf{w}}(H,G)=\frac{D^{2}_{v}(H,G)}{4^{r-1}}\sum\limits_{i=1}^{r/2}\binom{r-1}{2i-1}\leq\frac{D^{2}_{v}(H,G)}{2^{r-1}}.$

∎

##  3\. A Fourth Moment Theorem for Monochromatic Counts

In this section, we prove our main quantitative convergence results, which
show that for graphs with no influential vertices, the fourth-moment condition
suffices for a central limit theorem to hold for $Z(H,G_{n})$. Let
$F:\mathbb{R}^{n}\to\mathbb{R}$,
$\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{n})$, and write
$\widetilde{F}=\frac{F-\mathbb{E}\left[F[\mathcal{N}]\right]}{\sqrt{\mathrm{Var}(F(\mathcal{N}))}}$,
for the normalized version of the function $F$.

######  Theorem 3.1.

Let $H$ be a fixed connected $r$-vertex graph and $G$ another graph. For
$Z(H,G)$ defined in (1.2), $\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{v(G)})$,
$X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes r}$, and
$\mathcal{Z}\sim\mathscr{N}(0,1)$, set

$m_{4}(H,G):=\sqrt{\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}},$

where $F_{H,G}$ is as in (2.9). Then,

$\displaystyle W_{1}(Z(H,G),\mathcal{Z})$
$\displaystyle\lesssim\max\limits_{v\in
V(G)}\left[\left(\frac{D_{v}^{2}(H,G)}{{\mathrm{Var}(F_{H,G}(X))}}\right)^{\frac{1}{4}}+D_{v}(H,G)m_{4}(H,G)\right],$
$\displaystyle d_{2}(Z(H,G),\mathcal{Z})$
$\displaystyle\lesssim\max\limits_{v\in
V(G)}\left[\left(\frac{D_{v}^{2}(H,G)}{{\mathrm{Var}(F_{H,G}(X))}}\right)^{\frac{1}{4}}+m_{4}(H,G)\right].$

Let us make some remarks concerning 3.1. First, if a sequence of graphs
$\\{G_{n}\\}_{n\geq 0}$ has no influential vertices, then, by definition,

$\max\limits_{v\in
V(G_{n})}\left(\frac{D_{v}^{2}(H,G_{n})}{{\mathrm{Var}(F_{H,G}(X))}}\right)^{\frac{1}{4}}\xrightarrow{n\to\infty}0.$

Recall now that convergence in $d_{2}$ implies convergence in distribution.
Hence for $Z(H,G_{n})\xrightarrow[\text{in law}]{n\to\infty}\mathcal{Z}$ is it
sufficient (and also necessary) that
$m_{4}(G_{n},H)\xrightarrow{n\to\infty}0.$ The fourth-moment discrepancy
$m_{4}$ is defined in terms of the Gaussian measure. However, when there are
no influential vertices, by 2.2, one could replace the Gaussian variables with
Rademacher ones, expressing the fourth moment of $Z(H,G)$ and arrive
asymptotically at the same expression.

The proof of 3.1 will be conducted in several steps. We shall first prove a
central limit theorem for the polynomial $F_{H,G}$ with Gaussian variables and
then use the Invariance Principle from 2.2 to replace the Gaussian variables
with Rademacher ones.

###  3.1. Normal Approximation for non-homogeneous polynomials

We begin by extending the fourth-moment theorem to non-homogeneous
polynomials. For a multi-linear polynomial of degree $d$,
$F:\mathbb{R}^{n}\to\mathbb{R}$, given by $F(x)=\sum_{I\in{\binom{[n]}{\leq
d}}}\alpha_{I}x^{I}$, denote by $F_{m}$ its degree $m$ homogeneous component,
whenever $m\leq d$. In other words,
$F_{m}(x)=\sum_{I\in\binom{[n]}{m}}\alpha_{I}x^{I}$. We now derive a necessary
condition on multi-linear polynomials to ensure that the fourth-moment theorem
holds.

######  Proposition 3.2.

Let $F:\mathbb{R}^{n}\to\mathbb{R}$ be a degree $d$ multi-linear polynomial,
and for $m\leq d$, let $F_{m}$ be its degree $m$ homogeneous component.
Further, let $\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{n})$, and suppose that
the following conditions are met:

  * •

$\mathbb{E}\left[F(\mathcal{N})\right]=0$ and
$\mathbb{E}\left[F(\mathcal{N})^{2}\right]=1$.

  * •

For every distinct $m,m^{\prime},m^{\prime\prime},m^{\prime\prime\prime}\leq
d$, we have the following inequalities

$\displaystyle\mathbb{E}$
$\displaystyle\left[F_{m}(\mathcal{N})F^{3}_{m^{\prime}}(\mathcal{N})\right]\geq
0,$ $\displaystyle\mathbb{E}$
$\displaystyle\left[F_{m}(\mathcal{N})F_{m^{\prime}}(\mathcal{N})F^{2}_{m^{\prime\prime}}(\mathcal{N})\right]\geq
0,$ (3.1) $\displaystyle\mathbb{E}$
$\displaystyle\left[F_{m}(\mathcal{N})F_{m^{\prime}}(\mathcal{N})F_{m^{\prime\prime}}(\mathcal{N})F_{m^{\prime\prime\prime}}(\mathcal{N})\right]\geq
0.$

Then, if $\mathcal{Z}\sim\mathscr{N}(0,1),$

$\displaystyle W_{1}(F(\mathcal{N}),\mathcal{Z})$ $\displaystyle\leq
C_{d}\cdot\max\limits_{m\leq
d}\mathbb{E}\left[F^{2}_{m}(\mathcal{N})\right]^{-1}\cdot\left(\sqrt{\mathbb{E}\left[F(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[F(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right),$
$\displaystyle d_{2}(F(\mathcal{N}),\mathcal{Z})$ $\displaystyle\leq
C_{d}\left(\sqrt{\mathbb{E}\left[F(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[F(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right),$

where $C_{d}>0$ depends only on $d$.

###### Proof.

The main idea of the proof is to use 2.1. To utilize the theorem, we shall
need to bound the fourth moment of $F(\mathcal{N})$ in terms of the fourth
moment of its homogeneous components. Towards this, we first note that the
assumption $\mathbb{E}[F(\mathcal{N})]=0$ implies $F_{0}=0$, and so,

$\displaystyle\mathbb{E}\left[F(\mathcal{N})^{4}\right]=\mathbb{E}\left[\left(\sum\limits_{m=1}^{d}F_{m}(\mathcal{N})\right)^{4}\right]\geq\sum\limits_{m=1}^{d}\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]+6\sum\limits_{m\neq
m^{\prime}}\mathbb{E}\left[F_{m}(\mathcal{N})^{2}F_{m^{\prime}}(\mathcal{N})^{2}\right],$

where the inequality follows since all missing terms were assumed to be
positive. Now, observe that as multi-linear and homogeneous polynomials, for
every $m\neq m^{\prime}$, $F_{m}$ and $F_{m^{\prime}}$ are Hermite polynomials
and belong to some Wiener chaos. By [22, Theorem 1], their squares are
positively correlated,
$\mathbb{E}\left[F_{m}(\mathcal{N})^{2}F_{m^{\prime}}(\mathcal{N})^{2}\right]\geq\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]\mathbb{E}\left[F_{m^{\prime}}(\mathcal{N})^{2}\right].$
Combining this inequality with the previous bound yields,

$\displaystyle\mathbb{E}\left[F(\mathcal{N})^{4}\right]\geq\sum\limits_{m=1}^{d}\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]+6\sum\limits_{m\neq
m^{\prime}}\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]\mathbb{E}\left[F_{m^{\prime}}(\mathcal{N})^{2}\right].$

On the other hand, it is readily seen that
$\mathbb{E}\left[F_{m}(\mathcal{N})F_{m^{\prime}}(\mathcal{N})\right]=0$,
whenever $m\neq m^{\prime}$, and so
$1=\mathbb{E}\left[F(\mathcal{N})^{2}\right]=\sum\limits_{m=1}^{d}\mathbb{E}\left[F^{2}_{m}(\mathcal{N})\right].$
So,

$3=3\left(\sum\limits_{m=1}^{d}\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]\right)^{2}=3\sum\limits_{m=1}^{d}\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}+6\sum\limits_{m\neq
m^{\prime}}\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]\left[F_{m^{\prime}}(\mathcal{N})^{2}\right],$

and

(3.2)
$\sum\limits_{m=1}^{d}\left(\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}\right)\leq\mathbb{E}\left[F(\mathcal{N})^{4}\right]-3.$

Now, in order to invoke 2.1, let $\widetilde{\mathcal{N}}$ be a
$d$-dimensional Gaussian with independent coordinates such that
$\mathbb{E}\left[\widetilde{\mathcal{N}}\right]=0$ and
$\mathbb{E}\left[\widetilde{\mathcal{N}}_{m}^{2}\right]=\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]$.
Set, $\widetilde{F}=\\{F_{m}(\mathcal{N})\\}_{m=1}^{d}$,
$m(F):=\max\limits_{m}\mathbb{E}\left[F^{2}_{m}(\mathcal{N})\right]^{-1}$ and
observe $\max\limits_{m\leq
d}\mathbb{E}\left[F^{2}_{m}(\mathcal{N})\right]\leq\mathbb{E}\left[F^{2}(\mathcal{N})\right]=1$.
Thus, according to 2.1, if $\Delta(F)$ is as in the theorem,

$\displaystyle\Delta(F)\leq$
$\displaystyle\sum\limits_{m=1}^{d}\sqrt{2d4^{d}\left(\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}\right)}$
$\displaystyle+$ $\displaystyle\sum\limits_{m\neq
m^{\prime}}\sqrt{2\mathbb{E}\left[F_{m^{\prime}}(\mathcal{N})^{2}\right]}\left(\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}\right)^{\frac{1}{4}}+d2^{d}\sqrt{2(2d)!\left(\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}\right)}$
$\displaystyle\leq$
$\displaystyle\sqrt{2d^{2}4^{d}\sum\limits_{m=1}^{d}\left(\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}\right)}+2d\left(\sum\limits_{i=m}^{d}\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}\right)^{\frac{1}{4}}$
$\displaystyle+\sqrt{8^{d}(2d)!\sum\limits_{m=1}^{d}\left(\mathbb{E}\left[F_{m}(\mathcal{N})^{4}\right]-3\mathbb{E}\left[F_{m}(\mathcal{N})^{2}\right]^{2}\right)}$
$\displaystyle\leq$ $\displaystyle\sqrt{4\cdot
8^{d}(2d)!\left(\mathbb{E}\left[F(\mathcal{N})^{4}\right]-3\right)}+2d\left(\mathbb{E}\left[F(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}.$

The second inequality uses the elementary inequality
$\sum_{i=1}^{d}\sqrt{x_{i}}\leq\sqrt{d\sum_{i=1}^{d}x_{i}}$, valid whenever
$x_{i}\geq 0$. The third inequality is (3.2).

To finish the proof, suppose that $(\widetilde{F},\widetilde{\mathcal{N}})$
are coupled with the optimal $W_{1}$ coupling, and let $\bf{1}$ be the all
ones vector. So, by 2.1, since $F=\sum\limits_{m=1}^{d}F_{m}$,

$\displaystyle W_{1}(F(\mathcal{N}),\mathcal{Z})$
$\displaystyle\leq\mathbb{E}\left[\left|\langle\widetilde{F},{\bf{1}}\rangle-\langle\widetilde{\mathcal{N}},{\bf
1}\rangle\right|\right]=\mathbb{E}\left[\left|\langle\widetilde{F}-\widetilde{\mathcal{N}},{\bf{1}}\rangle\right|\right]$
$\displaystyle\leq\|{\bf
1}\|\cdot\mathbb{E}\left[\|\widetilde{F}-\widetilde{\mathcal{N}}\|\right]=\sqrt{d}\cdot
W_{1}(\widetilde{F},\widetilde{\mathcal{N}})\leq C_{d}\cdot
m(F)\cdot\Delta(F).$

A similar argument works for $d_{2}$, by noting that if $\|h\|_{C_{2}}\leq 1$
for some $h:\mathbb{R}\to\mathbb{R}$, then
$\widetilde{h}(x):=h(\langle{\bf{1}},x))$, satisfies
$\|\widetilde{h}\|_{C_{2}}\leq d.$ ∎

We now demonstrate several examples of polynomials that satisfy the conditions
in (• ‣ 3.2).

######  Lemma 3.3.

Let $F:\mathbb{R}^{n}\to\mathbb{R}$ be a multi-linear polynomial of degree
$d$, given by $F(x)=\sum\limits_{I\in{\binom{[n]}{\leq d}}}\alpha_{I}x^{I}$.
Suppose that for every $I\in{\binom{[n]}{\leq d}}$, $\alpha_{I}\geq 0$, (resp.
$\alpha_{I}\leq 0$), then the inequalities in (• ‣ 3.2) hold.

###### Proof.

The result follows from the following simple observation: Let
$I_{1},I_{2},I_{3},I_{4}\subset[n]$ be four sets of indices, not necessarily
distinct, and let $\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{n})$. Then,

$\mathbb{E}\left[\mathcal{N}^{I_{1}}\mathcal{N}^{I_{2}}\mathcal{N}^{I_{3}}\mathcal{N}^{I_{4}}\right]\geq
0.$

In other words, any monomial with Gaussian variables has a non-negative
expectation. It is now enough to note that each of the expectations in (• ‣
3.2) can be written as a sum of monomials in Gaussian variables. These
monomials have positive coefficients since all coefficients in $F$ have equal
signs and the claim follows. ∎

######  Lemma 3.4.

Let $F:\mathbb{R}^{n}\to\mathbb{R}$ be a quadratic multi-linear polynomial,
$F(x)=F_{1}(x)+F_{2}(x)$. Then, the inequalities in (• ‣ 3.2) hold.

###### Proof.

It is enough to show that
$\mathbb{E}\left[F_{1}(\mathcal{N})F^{3}_{2}(\mathcal{N})\right]=\mathbb{E}\left[F^{3}_{1}(\mathcal{N})F_{2}(\mathcal{N})\right]=0$.
Indeed, this holds since both $F_{1}(\mathcal{N})F^{3}_{2}(\mathcal{N})$ and
$F^{3}_{1}(\mathcal{N})F_{2}(\mathcal{N})$ have odd degrees and so are anti-
symmetric. ∎

###  3.2. Graph Polynomials

Let us now show that the fourth-moment theorem holds for monochromatic counts
in graphs with no influential vertices. For graphs $G$ and $H$, recall the
polynomials $\mathbb{I}_{H}$ and $F_{H,G}$ defined in Section 2.2. To apply
3.2, we first need to estimate the Gaussian variance of the $m$ homogeneous
component $F_{H,G,m}$, for even $m$.

######  Lemma 3.5.

Let $G$ and $H$ be graphs with $v(H)=r$. Then, if
$\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{v(G)})$, for any $0<m\leq r$ even,

$\displaystyle\frac{1}{4^{r-1}}\binom{r}{m}N(H,G)\leq\mathbb{E}\left[F_{H,G,m}(\mathcal{N})^{2}\right]\leq\frac{1}{4^{r-1}}\binom{r}{m}N(H,G)\max\limits_{v\in
V(G)}D_{v}(H,G),$

where $N(H,G)$ is the number of copies of $H$ in $G$, as in (1.3). Moreover,
for triangles, when $H=\triangle$,
$\mathbb{E}\left[F_{\triangle,G,2}(\mathcal{N})^{2}\right]=\mathrm{Var}(F_{\triangle,G}(\mathcal{N}))$.

###### Proof.

The representation in (2.9) along with a simple calculation shows that for
even $m$

$\mathbb{E}\left[F_{H,G,m}(\mathcal{N})^{2}\right]=\frac{1}{4^{r-1}}\sum\limits_{\mathbf{w}\in{\binom{V(G)}{m}}}D^{2}_{\mathbf{w}}(H,G).$

Since every copy of $H$ contains $\binom{r}{m}$ subsets of size $m$, we also
have,

$\sum\limits_{\begin{subarray}{c}\mathbf{w}\in\binom{V(G)}{m}\end{subarray}}D_{\mathbf{w}}(H,G)=\binom{r}{m}N(H,G).$

For any $\mathbf{w}$ and $v\in\mathbf{w}$, $D_{\mathbf{w}}(H,G)\leq
D_{v}(H,G)$, which establishes

$\displaystyle\mathbb{E}\left[F_{H,G,m}(\mathcal{N})^{2}\right]\leq\frac{1}{4^{r-1}}\max\limits_{v\in
V(G)}D_{v}(H,G)\sum\limits_{{\mathbf{w}\in\binom{V(G)}{m}}}D_{\mathbf{w}}(H,G)=\frac{1}{4^{r-1}}\binom{r}{m}N(H,G)\max\limits_{v\in
V(G)}D_{v}(H,G).$

Similarly, since $D_{v}(H,G)$ is a non-negative integer,

$\displaystyle\frac{1}{4^{r-1}}\binom{r}{m}N(H,G)=\frac{1}{4^{r-1}}\sum\limits_{{\mathbf{w}\in\binom{V(G)}{m}}}D_{\mathbf{w}}(H,G)\leq\mathbb{E}\left[F_{H,G,m}(\mathcal{N})^{2}\right],$

which concludes the proof in the general case.

The result for triangles follows by observing that $F_{\triangle,G}$ is
quadratic, as in (2.7). Thus,

$F_{\triangle,G}=F_{\triangle,G,0}+F_{\triangle,G,2},$

with $F_{\triangle,G,0}=\mathbb{E}\left[F_{\triangle,G}(\mathcal{N})\right].$
∎

We can now prove a central limit theorem-type result for
$F_{H,G}(\mathcal{N})$.

######  Lemma 3.6.

Let $G$ and $H$ be graphs with $v(H)=r$. Then, for
$\mathscr{N}\sim\mathscr{N}(0,\mathrm{I}_{|V(G)|})$,
$\mathcal{Z}\sim\mathscr{N}(0,1)$, and the normalized polynomial
$\widetilde{F}_{H,G}(\mathcal{N}):=\frac{F_{H,G}(\mathcal{N})-\mathbb{E}\left[F_{H,G}(\mathcal{N})\right]}{\sqrt{\mathrm{Var}(F_{H,G}(\mathcal{N}))}}$,

$\displaystyle W_{1}(\widetilde{F}_{H,G}(\mathcal{N}),\mathcal{Z})$
$\displaystyle\lesssim\max\limits_{v\in
V(G)}D_{v}(H,G)\left(\sqrt{\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right),$
$\displaystyle d_{2}(\widetilde{F}_{H,G}(\mathcal{N}),\mathcal{Z})$
$\displaystyle\lesssim\left(\sqrt{\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right).$

Moreover, for triangles, when $H=\triangle$,

$W_{1}(\widetilde{F_{\triangle,G}}(\mathcal{N}),\mathcal{Z})\lesssim\sqrt{\mathbb{E}\left[\widetilde{F_{\triangle,G}}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F_{\triangle,G}}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}.$

###### Proof.

As observed from (2.9), $F_{H,G}$ is a multi-linear polynomial of degree at
most $r$, and all of its coefficients are positive. Thus, Lemma 3.3 and 3.2
imply,

$\displaystyle W_{1}(\widetilde{F}_{H,G}(\mathcal{N}),\mathcal{Z})$
$\displaystyle\lesssim\max\limits_{m\leq
r}\mathbb{E}\left[\widetilde{F}_{H,G,m}(\mathcal{N})^{2}\right]^{-1}\left(\sqrt{\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right),$
$\displaystyle d_{2}(\widetilde{F}_{H,G}(\mathcal{N}),\mathcal{Z})$
$\displaystyle\lesssim\left(\sqrt{\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right)$

For triangles, by Lemma 3.5,
$\mathbb{E}\left[\widetilde{F_{\triangle,G,2}}(\mathcal{N})\right]=1$, which
resolves this case. For general $H$, it will suffice to show that

(3.3) $\max\limits_{m\leq
r}\mathbb{E}\left[\widetilde{F}_{H,G,m}(\mathcal{N})^{2}\right]^{-1}\leq
2^{r}\max\limits_{v\in V(G)}D_{v}(H,G).$

By Lemma 3.5, for any $0<m\leq r$ even,
$\mathbb{E}\left[F_{H,G,m}(\mathcal{N})^{2}\right]\geq\frac{1}{4^{r-1}}\binom{r}{m}N(H,G)$.
Similarly, since
$\mathrm{Var}(F_{H,G}(\mathcal{N}))=\sum\limits_{m=1}^{r}\mathbb{E}\left[F_{H,G,m}(\mathcal{N})^{2}\right],$

$\mathrm{Var}(F_{H,G}(\mathcal{N}))\leq\frac{1}{4^{r-1}}\max\limits_{v\in
V(G)}D_{v}(H,G)\sum\limits_{m^{\prime}=1}^{r}\binom{r}{m^{\prime}}N(H,G)\leq\frac{1}{2^{r-2}}\max\limits_{v\in
V(G)}D_{v}(H,G)N(H,G).$

So,

$\mathbb{E}\left[\widetilde{F}_{H,G,m}(\mathcal{N})^{2}\right]^{-1}=\frac{\mathrm{Var}(F_{H,G}(\mathcal{N}))}{\mathbb{E}\left[F_{H,G,m}(\mathcal{N})^{2}\right]}\leq\max\limits_{v\in
V(G)}D_{v}(H,G)\frac{4^{r-1}N(H,G)}{2^{r-2}\binom{r}{m}N(H,G)},$

which is (3.3). ∎

###  3.3. A Fourth-Moment Theorem for Monochromatic Subgraph Counts

We can now combine Lemma 3.6 with the Invariance Principle in 2.2 to prove a
Fourth Moment Theorem for $2$-colorings.

###### Proof of 3.1.

Let $X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes v(G)}$. Since (c.f. (2.8))
$T(H,G)=F_{H,G}(X)$, we have

$Z(H,G)=\widetilde{F}_{H,G}(X)=\frac{F_{H,G}(X)-\mathbb{E}\left[F_{H,G}(X)\right]}{\sqrt{\mathrm{Var}(F_{H,G}(X))}}.$

Thus, we have the following

(triangle ineq.) $\displaystyle W_{1}(Z(H,G),\mathcal{Z})$ $\displaystyle\leq
W_{1}(\widetilde{F}_{H,G}(X),\widetilde{F}_{H,G}(\mathcal{N}))+W_{1}(\widetilde{F}_{H,G}(\mathcal{N}),\mathcal{Z})$
(2.2) $\displaystyle
W_{1}(\widetilde{F}_{H,G}(X),\widetilde{F}_{H,G}(\mathcal{N}))$
$\displaystyle\lesssim\left(\max\limits_{v\in
V(G)}\mathrm{inf}_{v}(\widetilde{F}_{H,G})\right)^{\frac{1}{4}}$ (Lemma 3.6)
$\displaystyle W_{1}(\widetilde{F}_{H,G}(\mathcal{N}),\mathcal{Z})$
$\displaystyle\lesssim\max\limits_{v\in
V(G)}D_{v}(H,G)\left(\sqrt{\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right).$

We now observe that by Lemma 2.3,

$\max\limits_{v\in
V(G)}\mathrm{inf}_{v}(\widetilde{F}_{H,G})=\frac{\max\limits_{v\in
V(G)}\mathrm{inf}_{v}(F_{H,G})}{\mathrm{Var}(F_{H,G}(X))}\lesssim\frac{\max\limits_{v\in
V(G)}D_{v}^{2}(H,G)}{{\mathrm{Var}(F_{H,G}(X))}}.$

Combining these bounds gives the desired result

$W_{1}(Z(H,G),\mathcal{Z})\lesssim\max_{v\in
V(G)}\left[\left(\frac{D_{v}^{2}(H,G)}{{\mathrm{Var}(F_{H,G}(X))}}\right)^{\frac{1}{4}}+D_{v}(H,G)\left(\sqrt{\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3}+\left(\mathbb{E}\left[\widetilde{F}_{H,G}(\mathcal{N})^{4}\right]-3\right)^{\frac{1}{4}}\right)\right].$

The proof for $d_{2}$ is essentially the same, by applying the $d_{2}$ bound
in Lemma 3.6. We only need to note that by (2.3),

$d_{2}(\widetilde{F}_{H,G}(X),\widetilde{F}_{H,G}(\mathcal{N}))\leq
W_{1}(\widetilde{F}_{H,G}(X),\widetilde{F}_{H,G}(\mathcal{N})).$

∎

We can also use 3.1 to obtain bounds on the Kolmogorov distance. By [13,
Theorem 3.3],
$d_{\mathrm{kol}}(Z(H,G),\mathcal{Z})\leq\sqrt{2W_{1}(Z(H,G),\mathcal{Z})}$
and in Lemma A.1 of the Appendix we prove
$d_{\mathrm{kol}}(Z(H,G),\mathcal{Z})\lesssim
d_{2}(Z(H,G),\mathcal{Z})^{\frac{1}{3}}$. Thus 3.1 and these bounds
immediately imply the following quantitative version of 1.2.

######  Corollary 3.7.

In the same setting of 3.1,

$\displaystyle d_{\mathrm{kol}}$ $\displaystyle(Z(H,G),\mathcal{Z})\lesssim$
$\displaystyle\max\limits_{v\in
V(G)}\min\left(\left(\left(\frac{D_{v}^{2}(H,G)}{{\mathrm{Var}(F_{H,G}(X))}}\right)^{\frac{1}{4}}+D_{v}(H,G)m_{4}(H,G)\right)^{\frac{1}{2}},\left(\left(\frac{D_{v}^{2}(H,G)}{{\mathrm{Var}(F_{H,G}(X))}}\right)^{\frac{1}{4}}+m_{4}(H,G)\right)^{\frac{1}{3}}\right).$

Similarly, by applying the Wasserstein bound to the triangle bound of Lemma
3.6 we obtain an improved convergence rate for triangles.

######  Corollary 3.8.

In the same setting of 3.1, if $H=\triangle$ is a triangle,

$\displaystyle d_{\mathrm{kol}}$
$\displaystyle(Z(\triangle,G),\mathcal{Z})\lesssim\max\limits_{v\in
V(G)}\left(\left(\frac{D_{v}^{2}(H,G)}{{\mathrm{Var}(F_{H,G}(X))}}\right)^{\frac{1}{4}}+m_{4}(H,G)\right)^{\frac{1}{2}}.$

##  4\. A Closer Look at Monochromatic Triangles

In this section, we focus on monochromatic triangle counts, taking
$H=\triangle$, and prove 1.3. We recall the polynomial expression in (2.7):

$\mathbb{I}_{\triangle}(x_{u},x_{v},x_{w})=2(x_{v}x_{u}+x_{v}x_{w}+x_{u}x_{w}+1).$

For graph $G$, let $\mathcal{T}(G)$ be the set of unlabeled triangles in $G$.
Given a two-coloring $x\in\\{\pm 1\\}^{v(G)}$ define the centered, normalized
count

$Z_{\triangle}(x):=\widetilde{F}_{\triangle,G}(x)=\frac{1}{4\sigma_{\triangle}}\sum\limits_{T\in\mathcal{T}(G)}(\mathbb{I}_{\triangle}(x|_{T})-2)=\frac{1}{\sigma_{\triangle}}\sum\limits_{uv\in
E(G)}D_{uv}(\triangle,G)x_{u}x_{v},$

where for $T=\\{u,v,w\\}$, $x|_{T}=\\{x_{v},x_{u},x_{w}\\}$, and

(4.1)
$\sigma^{2}_{\triangle}:=\mathrm{Var}(T(\triangle,G))=\frac{1}{16}\sum\limits_{e\in
E(G)}D^{2}_{e}(\triangle,G).$

The expression on the right-hand side follows from (2.9), noting that the only
pairs of vertices $u,v\in V(G)$ where $D_{uv}(\triangle,G)>0$ are those that
form an edge $uv\in E(G).$

We study the distribution of $Z_{\triangle}(X)$ when
$X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes v(G)}$, so that
$Z_{\triangle}(X)=Z(\triangle,G)$. It will be convenient to start by replacing
$X$ with a Gaussian vector, and in light of 2.2, we begin by handling
influential variables. If $\\{G_{n}\\}$ is a sequence of graphs let us denote
by $\mathcal{I}_{n}$ the set of influential variables. Formally,
$\mathcal{I}_{n}=(v_{i}^{(n)})_{i=1}^{k}\subset V(G_{n})$ is an ordered tuple
of vertices, such for any $i=[k]$

$\liminf\limits_{n\to\infty}\frac{D_{v_{i}^{(n)}}(\triangle,G_{n})}{\sigma_{\triangle}}>0,$

and for any other vertices $w^{(n)}\in V(G_{n})$, where there exists $N$ such
that for all $n>N,$ $w^{(n)}\not\in\mathcal{I}_{n},$ we have

$\limsup\limits_{n\to\infty}\frac{D_{w^{(n)}}(\triangle,G_{n})}{\sigma_{\triangle}}=0.$

Note that for simplicity, we are implicitly assuming that the number of
influential vertices is uniformly bounded in $n$.

###  4.1. Influential Edges Forbid CLTs

Our first goal will be to show that when $G_{n}$ contains an influential edge,
then the CLT cannot hold, and thus having no influential edge is a necessary
condition for the asymptotic normality of
$Z(\triangle,G_{n})=Z_{\triangle}(X)$ when
$X\sim\operatorname{Rad}(\frac{1}{2})^{\otimes v(G_{n})}$. This is precisely
the first item of 1.3.

######  Proposition 4.1.

Let $\\{G_{n}\\}_{n\geq 0}$ be a sequence of graphs with $\mathcal{I}_{n}$ the
sets of their influential vertices. Suppose that
$\sup\limits_{n}|\mathcal{I}_{n}|=m<\infty$ and that there exists a sequence
of influential edge $e_{n}\in E(G_{n})$, such that

$\lim\sup\limits_{n\to\infty}\frac{D_{e_{n}}(\triangle,G_{n})}{\sigma_{\triangle}}>0.$

Then, if $\mathcal{Z}\sim\mathscr{N}(0,1)$,

$\limsup\limits_{n\to\infty}d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})>0.$

Our strategy for dealing with influential variables in $Z_{\triangle}(x)$ will
be to fix their values. For a partial coloring
$\rho:{\mathcal{I}_{n}}\to\\{\pm 1\\}$ we write
$Z_{\triangle}^{(\rho)}:V(G_{n})\setminus\mathcal{I}_{n}\to\mathbb{R}$ for the
function $Z_{\triangle}$ where every $v\in\mathcal{I}_{n}$ is assigned the
color $\rho(v)$. We can express $Z_{\triangle}^{(\rho)}$ in the following way

$\displaystyle Z_{\triangle}^{(\rho)}(x)$
$\displaystyle=\frac{1}{3\sigma_{\triangle}}\left[\sum\limits_{u,v\in\mathcal{I}_{n}}D_{uv}(\triangle,G_{n})\rho(u)\rho(v)+\sum\limits_{u\in\mathcal{I}_{n},v\notin\mathcal{I}_{n}}D_{uv}(\triangle,G_{n})\rho(u)x_{v}+\sum\limits_{u,v\notin\mathcal{I}_{n}}D_{uv}(\triangle,G)x_{u}x_{v}\right]$
$\displaystyle=Z_{\triangle}^{(0,\rho)}+Z_{\triangle}^{(1,\rho)}(x)+Z_{\triangle}^{(2)}(x).$

For $i=0,1,2$, $Z_{\triangle}^{(i,\rho)}$ stands for the $i^{\mathrm{th}}$
homogeneous part of $Z_{\triangle}^{(\rho)}$. It is also clear from the
expression that $Z_{\triangle}^{(2)}$ does not depend on $\rho$. Let us
collect some facts about this decomposition when the variables $x_{v}$ is
taken to be Gaussian.

######  Lemma 4.2.

Let
$\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{|V(G_{n})\setminus\mathcal{I}_{n}|})$,
then the following conditions hold:

  1. (1)

There exists a sequence $\\{\lambda_{i,n}\\}_{i=1}^{\infty}\in\mathbb{R}$ with
$|\lambda_{1,n}|\geq|\lambda_{2,n}|\geq\cdots$ and independent standard
Gaussians $\\{M_{i}\\}_{i=1}^{\infty}$ such that,

$Z_{\triangle}^{(2)}(\mathcal{N})\stackrel{{\scriptstyle\mathrm{law}}}{{=}}\sum\limits_{i=1}^{\infty}\lambda_{i,n}(M_{i}^{2}-1).$

  2. (2)

For every partial coloring $\rho$, there exists $\sigma_{\rho}^{2}\in[0,1]$,
such that
$Z_{\triangle}^{(1,\rho)}(\mathcal{N})\sim\mathscr{N}(0,\sigma^{2}_{\rho}).$

  3. (3)

$Z_{\triangle}^{(0,\rho)}\xrightarrow{n\to\infty}0$ for every $\rho$ if and
only if there does not exist an influential edge.

###### Proof.

For the first assertion, we note that $Z_{\triangle}^{(2)}(\mathcal{N})$ is a
quadratic form in Gaussian variables. The result is obtained by diagonalizing
the form and using the fact that the Gaussian is rotationally invariant, see
[26, Proposition 2.7.13] for more details.

The second assertion follows since $Z_{\triangle}^{(1,\rho)}(\mathcal{N})$ is
a centered linear functional of Gaussian variables and hence Gaussian. The
fact that $\sigma_{\rho}^{2}\leq 1$ follows by calculating the variance and
comparing to (4.1).

For the last item, let
$R\sim\operatorname{Rad}(\frac{1}{2})^{\otimes|\mathcal{I}_{n}|}$ be a random
coloring of the influential vertices. Since $R$ is centered, the condition
$Z_{\triangle}^{(0,R)}\xrightarrow{n\to\infty}0$ is equivalent to
$\mathrm{Var}_{R}(Z_{\triangle}^{(0,R)})\xrightarrow{n\to\infty}0.$ Since
$R(u)R(u^{\prime})$ is uncorrelated with $R(v)R(v^{\prime})$ whenever
$\\{u,u^{\prime}\\}\neq\\{v,v^{\prime}\\}$ we get that

$\mathrm{Var}_{R}(Z_{\triangle}^{(0,R)})=\frac{1}{16\sigma^{2}_{\triangle}}\sum\limits_{uv\in\mathcal{I}_{n}}D^{2}_{uv}(\triangle,G_{n}).$

Suppose that we have an influential edge i.e. $u_{n},v_{n}\in\mathcal{I}_{n}$
such that

$\liminf\limits_{n\to\infty}\frac{D_{u_{n}v_{n}}(\triangle,G_{n})}{\sigma_{\triangle}}>0.$

In this case it is clear that
$\liminf\limits_{n\to\infty}\mathrm{Var}_{R}(Z_{\triangle}^{(0,R)})>0$ as
well. On the other hand, if there are no influential edges then,

$\displaystyle\mathrm{Var}_{R}(Z_{\triangle}^{(0,R)})$
$\displaystyle\leq\left(\max\limits_{u,v\in
V(G)}\frac{D_{uv}(\triangle,G_{n})}{\sigma_{\triangle}}\right)\frac{1}{16\sigma_{\triangle}}\sum\limits_{u,v\in\mathcal{I}_{n}}D_{uv}(\triangle,G_{n})=o(1),$

where we have used the variance representation (4.1), and that
$\sup\limits_{n}|\mathcal{I}_{n}|=m<\infty$. ∎

We can now establish one particular case where $Z_{\triangle}(\mathcal{N})$
does not converge to a Gaussian. If there is at least one large coefficient in
the quadratic decomposition of $Z_{\triangle}^{(2)}$, then $Z_{\triangle}(X)$
will have a sub-exponential behavior and so cannot converge to a Gaussian.

######  Lemma 4.3.

Let $\\{G_{n}\\}_{n\geq 0}$ be a sequence of graphs with
$\\{\mathcal{I}_{n}\\}$ the sets of their influential vertices. Suppose that
$\sup\limits_{n}|\mathcal{I}_{n}|=m<\infty$. Further let $\lambda_{1,n}$ be as
in Lemma 4.2, and assume

$\lim\limits_{n\to\infty}{|\lambda_{1,n}|}=c>0.$

Then, there exists some constant $c^{\prime}>0$, such that for every partial
coloring $\rho:\mathcal{I}_{n}\to\\{\pm 1\\}$, and all $t>0$ large enough,

$\mathbb{P}\left(|Z_{\triangle}^{(\rho)}(\mathcal{N})|>t\right)\geq
e^{-c^{\prime}t},$

where
$\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{|V(G_{n})\setminus\mathcal{I}_{n}|})$.

###### Proof.

We fix some large $t>10$, and bound
$\mathbb{P}\left(|Z_{\triangle}^{(2)}(\mathcal{N})|\geq t\right)$ from below.
Towards that, recall the expression $Z_{\triangle}^{(2)}(\mathcal{N})$ from
Lemma 4.2, since we may assume $\lambda_{1,n}\geq\frac{c}{2}$, we obtain

$\displaystyle\mathbb{P}\left(|Z_{\triangle}^{(2)}(\mathcal{N})|\geq t\right)$
$\displaystyle\geq\mathbb{P}\left(\lambda_{1,n}(M_{1}^{2}-1)\geq
t+4\right)\mathbb{P}\left(|Z_{\triangle}^{(2)}(\mathcal{N})-\lambda_{1,n}(M_{1}^{2}-1)|\leq
4\right)$
$\displaystyle\geq\frac{1}{2}\mathbb{P}\left(M_{1}^{2}\geq\frac{t+4+\lambda_{1,n}}{\lambda_{1,n}}\right)\geq\frac{1}{2}\mathbb{P}\left(M_{1}^{2}\geq\frac{t+4+\frac{c}{2}}{\frac{c}{2}}\right)\geq\frac{1}{2}e^{-\beta
t},$

where $\beta>0$ is some constant, which depends on $c$. The first inequality
uses the independence between $\\{M_{i}\\}$, the second inequality uses
Chebyschev’s inequality for
$Z_{\triangle}^{(2)}(\mathcal{N})-\lambda_{1,n}(M_{1}^{2}-1)$, which has
$\mathrm{Var}(|Z_{\triangle}^{(2)}(\mathcal{N})-M_{1}^{2}|)=\sum\limits_{i=2}^{\infty}\lambda_{i,n}^{2}\leq
1$, and the fourth inequality is a tail bound for the chi-squared random
variable $M_{1}^{2}$. But now, by Lemma 4.2, for any $\rho$,
$Z_{\triangle}^{(0,\rho)}+Z_{\triangle}^{(1,\rho)}(\mathcal{N})\sim\mathscr{N}(Z_{\triangle}^{(0,\rho)},\sigma^{2}_{\rho})$
with $\sigma^{2}_{\rho}\leq 1$, and $Z_{\triangle}^{(0,\rho)}\leq m^{2}$.
Thus, we have for some constant $\alpha>0$, independent of $\rho$, and for all
large $t>10$,

$\mathbb{P}\left(|Z_{\triangle}^{(0,\rho)}+Z_{\triangle}^{(1,\rho)}(\mathcal{N})|\geq
t\right)\leq e^{-\alpha t^{2}}.$

So,

$\displaystyle\mathbb{P}\left(|Z_{\triangle}^{(\rho)}(\mathcal{N})|>t\right)$
$\displaystyle\geq\mathbb{P}\left(|Z_{\triangle}^{(2)}(\mathcal{N})|\geq
2t,|Z_{\triangle}^{(0,\rho)}+Z_{\triangle}^{(1,\rho)}(\mathcal{N})|\leq
t\right)$
$\displaystyle\geq\mathbb{P}\left(|Z_{\triangle}^{(2)}(\mathcal{N})|\geq
2t\right)+\mathbb{P}\left(|Z_{\triangle}^{(0,\rho)}+Z_{\triangle}^{(1,\rho)}(\mathcal{N})|\leq
t\right)-1$ $\displaystyle\geq\frac{1}{2}e^{-\beta t}+1-e^{-\alpha
t^{2}}-1=\frac{1}{2}e^{-\beta t}-e^{-\alpha t^{2}}\geq e^{-c^{\prime}t},$

for some $c^{\prime}>0$. ∎

We also need to handle the case where $Z_{\triangle}^{(2)}(\mathcal{N})$ is
not sub-exponential. In that case, as we shall show that
$Z_{\triangle}^{(2)}(\mathcal{N})$, and hence
$Z_{\triangle}^{(\rho)}(\mathcal{N})$, is approximately Gaussian, which makes
$Z_{\triangle}(X)$ approximately a Gaussian mixture. When there is an
influential edge this mixture will be non-trivial, thus not a Gaussian.

######  Lemma 4.4.

Let $\\{G_{n}\\}_{n\geq 0}$ be a sequence of graphs with $\mathcal{I}_{n}$ the
set of their influential vertices. Further let $\lambda_{1,n}$ be as in Lemma
4.2, and assume

$\lim\limits_{n\to\infty}|{\lambda_{1,n}}|=0.$

Then, there exists a subsequence $n_{k}$, such that for every partial coloring
$\rho:\mathcal{I}_{n}\to\\{-1,1\\}$,
$Z_{\triangle}^{(\rho)}(\mathcal{N})\xrightarrow[\mathrm{in\
law}]{n_{k}\to\infty}\mathscr{N}(Z_{\triangle}^{(0,\rho)},\sigma^{\prime
2}_{\rho}),$ for some $\sigma^{\prime 2}_{\rho},$ and
$\mathcal{N}\sim\mathscr{N}(0,\mathrm{I}_{|V(G_{n})\setminus\mathcal{I}_{n}|})$.

###### Proof.

If $\mathrm{Var}(Z_{\triangle}^{(2)}(\mathcal{N}))\xrightarrow{n\to 0}0$,
then, by Lemma 4.2

$Z_{\triangle}^{(\rho)}(\mathcal{N})\xrightarrow[\mathrm{in\
law}]{n\to\infty}Z_{\triangle}^{(0,\rho)}+Z_{\triangle}^{(1,\rho)}(\mathcal{N})\sim\mathscr{N}(0,\sigma_{\rho}^{2}).$

Thus, we suppose that
$\limsup\limits_{n\to\infty}\mathrm{Var}(Z_{\triangle}^{(2)}(\mathcal{N}))=\eta^{2}>0$.
By Lemma 4.2, we can write $Z_{\triangle}^{(2)}(\mathcal{N})$ as
$\sum\limits_{i=1}^{\infty}\lambda_{i,n}(M_{i}^{2}-1),$ and observe that by
the Berry-Eseen inequality [3]

$d_{\mathrm{kol}}(Z_{\triangle}^{(2)}(\mathcal{N}),\widetilde{\mathcal{Z}})\leq\max\limits_{i}\frac{\mathbb{E}\left[(\lambda_{i,n}(M_{i}^{2}-1))^{3}\right]}{\mathbb{E}\left[(\lambda_{i,n}(M_{i}^{2}-1))^{2}\right]}\frac{1}{\sqrt{\mathrm{Var}(Z_{\triangle}^{(2)}(\mathcal{N}))}}\leq\frac{\lambda_{1,n}}{\sqrt{\mathrm{Var}(Z_{\triangle}^{(2)}(\mathcal{N}))}},$

where we have passed to a subsequence and where
$\widetilde{\mathcal{Z}}\sim\mathscr{N}(0,\eta^{2})$. This implies that

$Z_{\triangle}^{(2)}(\mathcal{N})\xrightarrow[\mathrm{in\
law}]{n_{k}\to\infty}\mathscr{N}(0,\eta^{2}).$

Moreover, since $Z_{\triangle}^{(2)}$ is a homogeneous quadratic polynomial,
$Z_{\triangle}^{(2)}(\mathcal{N})$ belongs to the second Wiener chaos and its
limit is independent of $\mathcal{N}$, see [28, Theorem 3.1]. Thus, by Lemma
4.2

$Z_{\triangle}^{(\rho)}(\mathcal{N})\xrightarrow[\mathrm{in\
law}]{n_{k}\to\infty}\mathscr{N}(0,\sigma_{\rho}^{2}+\eta^{2}).$

∎

Having covered the two cases above we can now prove 4.1.

###### Proof of 4.1.

We separate the proof into two cases, depending on the behavior of
$Z_{\triangle}^{(2)}(\mathcal{N})$, as in Lemma 4.2. Recall that
$|\mathcal{I}_{n}|\leq m$ for some choice of $m$ uniformly bounded in $n$.

Case I:  Suppose that $\limsup_{n\to\infty}|\lambda_{i,n}|>0$. By passing to a
subsequence, and applying Lemma 4.3, we obtain a constant $c^{\prime}>0$, such
that for large enough $t>0$,

$\mathbb{P}\left(|Z_{\triangle}^{(\rho)}(\mathcal{N})|>t\right)\geq
e^{-c^{\prime}t},$

uniformly in $\rho.$ Thus, let $X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes
v(G_{n})}$, so that $Z(\triangle,G_{n})=Z_{\triangle}(X)$. By the law of total
probability,

$\mathbb{P}\left(|Z_{\triangle}(X)|>t\right)\geq\frac{1}{2^{m}}\sum\limits_{\rho:\mathcal{I}_{n}\to\\{\pm
1\\}}\mathbb{P}\left(|Z_{\triangle}^{(\rho)}(X)|>t\right)\xrightarrow{n\to\infty}\frac{1}{2^{m}}\sum\limits_{\rho:\mathcal{I}_{n}\to\\{\pm
1\\}}\mathbb{P}\left(|Z_{\triangle}^{(\rho)}(\mathcal{N})|>t\right)\gtrsim
e^{-c^{\prime}t}.$

The final limit follows by observing that for a given partial assignment
$\rho$ of all influential vertices, per Lemma 2.3, $Z_{\triangle}^{(\rho)}$
has no influential variables and thus 2.2 implies convergence. Since
$\mathbb{P}\left(|\mathcal{Z}|\geq t\right)\leq 2e^{-t^{2}/2}$ for
$\mathcal{Z}\sim\mathscr{N}(0,1)$, we conclude the proof by choosing an
appropriately large $t$.

Case II:  Suppose that $\lim_{n\to\infty}|\lambda_{i,n}|=0$, and let
$X\sim\mathrm{Rad}(\frac{1}{2})^{\otimes V(G_{n})}$ be as above. Let $Y$ be a
Gaussian mixture with law

$Y\overset{\text{law}}{=}\frac{1}{2^{|\mathcal{I}_{n}|}}\sum\limits_{\rho:\mathcal{I}_{n}\to\\{\pm
1\\}}\mathscr{N}(Z_{\triangle}^{(0,\rho)},\sigma^{\prime 2}_{\rho}),$

where the variances $\sigma^{\prime 2}_{\rho}$ are as in Lemma 4.4. We claim
that $Z_{\triangle}(X)$ and $Y$ are asymptotically the same. Indeed, by the
law of total probability,

$\displaystyle d_{\mathrm{kol}}(Z_{\triangle}(X),Y)$ $\displaystyle\leq
d_{\mathrm{kol}}(Z_{\triangle}(X),Z_{\triangle}(\mathcal{N}))+d_{\mathrm{kol}}(Z_{\triangle}(\mathcal{N}),Y)$
$\displaystyle\leq\frac{1}{2^{|\mathcal{I}_{n}|}}\sum\limits_{\rho}d_{\mathrm{kol}}(Z_{\triangle}^{(\rho)}(X),Z_{\triangle}^{(\rho)}(\mathcal{N}))+d_{\mathrm{kol}}(Z_{\triangle}(\mathcal{N}),Y).$

Since $Z_{\triangle}^{(\rho)}$ has no influential variables, 2.2 implies

$\frac{1}{2^{|\mathcal{I}_{n}|}}\sum\limits_{\rho}d_{\mathrm{kol}}(Z_{\triangle}^{(\rho)}(X),Z_{\triangle}^{(\rho)}(\mathcal{N}))\xrightarrow{n\to\infty}0,$

while the condition on $\lambda_{1,n}$ and Lemma 4.4 ensure that

$d_{\mathrm{kol}}(Z_{\triangle}(\mathcal{N}),Y)\xrightarrow{n\to\infty}0.$

Thus, $d_{\mathrm{kol}}(Z_{\triangle}(X),Y)\xrightarrow{n\to\infty}0.$ and it
will be enough to show, that when $G_{n}$ contains an influential edge, then
$d_{\mathrm{kol}}(Y,\mathcal{Z})$ is bounded away from $0$ (where
$\mathcal{Z}\sim\mathscr{N}(0,1)$). Since $Y$ is a finite Gaussian mixture,
and since the family of finite Gaussian mixtures is identifiable, [31], for
$Y\xrightarrow[\text{in law}]{n\to\infty}\mathcal{Z}$ it is necessary and
sufficient that, for every $\rho$,

$Z_{\triangle}^{(0,\rho)}\xrightarrow{n\to\infty}0\text{ and
}\sigma_{\rho}^{\prime}\xrightarrow{n\to\infty}1.$

The third item in Lemma 4.2 along with the existence of an influential edge
rules out the possibility of
$Z_{\triangle}^{(0,\rho)}\xrightarrow{n\to\infty}0$ for every $\rho$. Hence
$d_{\mathrm{kol}}(Y,\mathcal{Z})$ must remain bounded away from $0$. ∎

###  4.2. Revisiting the Fourth-Moment Phenomenon for $Z(\triangle,G_{n})$

We now prove the second item of 1.3 and show that when $G_{n}$ does not
contain an influential edge, then the fourth-moment phenomenon persists.

######  Proposition 4.5.

Let ${G_{n}}$ be a sequence of graphs and set $M_{n}:=\max\limits_{e\in
E(G)}\frac{D_{e}(\triangle,H)}{\sigma_{\triangle}}$. Then, for
$\mathcal{Z}\sim\mathscr{N}(0,1)$,

$d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})\lesssim\left(M_{n}^{2}+\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]-3\right)^{1/5}.$

###### Proof.

We shall require several results from [6] concerning the fourth moment of
$Z(\triangle,G_{n})$, and its distance to a Gaussian. First, [6, Theorem 1.1,
Lemma 4.1] established that

(4.2)
$d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})\lesssim\left(\left(\frac{1+N(\triangle_{4},G_{n})}{\sigma_{\triangle}^{4}}\right)^{\frac{1}{4}}+\frac{\sum\limits_{s=1}^{4}N(\triangle_{s},G_{n})+\sum\limits_{s=1}^{28}N(H_{s},G_{n})}{\sigma^{4}_{\triangle}}\right)^{1/5}.$

Here $\triangle_{s}$ stands for an $s$-pyramid ($s$ triangles glued at a
common edge) and $\\{H_{s}\\}_{s=1}^{28}$ is a list of $28$ graphs given in
[6, Lemma 4.1]. In this lemma, the authors also show that there is a list of
positive constants $\\{\delta_{s}\\}_{s=1}^{4}$ and $\\{c_{s}\\}_{s=1}^{28}$,
such that

(4.3)
$\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]-3=\frac{1}{\sigma_{\triangle}^{4}}\left[-\sum\limits_{s=1}^{4}\delta_{s}N(\triangle_{s},G_{n})+\sum\limits_{s=1}^{28}c_{s}N(H_{s},G_{n})\right].$

Our key observation is that we can enumerate the $s$-pyramids by enumerating
over edges $e\in E(G_{n})$, and choosing $s$ different triangles which contain
$e$. Recall that for $e\in E(G_{n})$, there are precisely
$D_{e}(\triangle,G_{n})$ triangles which include $e$, and so

$N(\triangle_{s},G_{n})\leq\sum\limits_{e\in
E(G_{n})}D_{e}(\triangle,G_{n})^{s}.$

We thus have, for every $1\leq s\leq 4$,

$\displaystyle\frac{N(\triangle_{s},G_{n})}{\sigma^{4}_{\triangle}}$
$\displaystyle\leq\frac{\sum\limits_{e\in
E(G_{n})}D_{e}(\triangle,G_{n})^{4}}{\sigma_{\triangle}^{4}}\leq
M_{n}^{2}\cdot\frac{\sum\limits_{e\in
E(G_{n})}D_{e}(\triangle,G_{n})^{2}}{\sigma_{\triangle}^{2}}\leq 10M_{n}^{2},$

where in the final inequality, we used the expression for
$\sigma_{\triangle}^{2}$ given in Eq. 4.1. Plugging this into Eq. 4.3 we get,
for some constant $C>0$,

$-CM_{n}^{2}+\frac{\sum\limits_{s=1}^{28}N(H_{s},G_{n})}{C\sigma_{\triangle}^{4}}\leq\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]-3.$

Applying the same bound to Eq. 4.2 yields that,

$d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})\lesssim\left(M_{n}^{\frac{1}{2}}+\frac{\sum\limits_{s=1}^{28}N(H_{s},G_{n})}{\sigma^{4}_{\triangle}}\right)^{1/5}.$

With the above two inequalities, we can now conclude with

$\displaystyle
d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})\lesssim\left(M_{n}^{\frac{1}{2}}+\left(\mathbb{E}\left[Z(\triangle,G_{n})^{4}\right]-3\right)\right)^{1/5}.$

∎

##  5\. Towards Characterizing Asymptotic Normality of General Monochromatic
Subgraph Counts

In this section, we generalize some of the ideas presented in Section 4 to
more general monochromatic subgraph counts and give evidence towards 1.5.

###  5.1. Graph Sequences Without Influential Pairs Exhibit Fourth-Moment
Phenomena

We begin by generalizing 4.5 to the general case. We shall prove 1.4 and show
that the fourth-moment phenomenon holds whenever the sequence $G_{n}$ does not
contain an influential pair. For convenience, we recall the statement of the
theorem.

######  Theorem 5.1.

Consider a sequence of graphs $\\{G_{n}\\}$, a graph $H$, and let
$\sigma_{H}=\sqrt{\mathrm{Var}(T(H,G_{n}))}.$ If $M_{n}:=\max\limits_{e\in
E(G_{n})}\frac{D_{e}(\triangle,G_{n})}{\sigma_{H}},$ then, for
$\mathcal{Z}\sim\mathscr{N}(0,1)$,

$d_{\mathrm{kol}}(Z(H,G_{n}),\mathcal{Z})\lesssim\left(M_{n}^{2}+(\mathbb{E}\left[Z(H,G_{n})^{4}\right]-3)\right)^{\frac{1}{20}}.$

In 4.5, we showed that the distance of $Z(\triangle,G_{n})$ to a standard
Gaussian $\mathcal{Z}$ was controlled by the maximum influence of a pair of
vertices and the divergence of the fourth moment from
$3=\mathbb{E}[\mathcal{Z}^{4}]$. The key idea in the argument was observing
that the upper bound of [6, Theorem 1.1, Lemma 4.1] on
$d_{\mathrm{kol}}(Z(\triangle,G_{n}),\mathcal{Z})$ was given by a sum over
various connected $4$-joins of triangles (ways to glue $4$ triangles together
into a connected graph). These $4$-joins were observed to be a subset of those
which appeared with some coefficients in the fourth-moment difference
$\mathbb{E}[Z(\triangle,G_{n})^{4}]-3$, and the only $4$-joins with negative
coefficients in this fourth-moment difference had counts controlled by the
influence of edges.

The work of [6] was extended to general $H$ in [14], enabling us to
analogously extend 4.5 to general $H$. Before stating the needed result from
[14], we begin first define the set of $4$-joins appearing in the error term.

######  Definition 5.2 (Good join).

Given a simple connected graph $H$, a _good join_ of $H$ is a graph formed by
joining $4$ copies of $H$, say $H_{1},H_{2},H_{3},H_{4}$, such that for all
$i=1,2,3,4$

(5.1) $\displaystyle\bigg{|}V(H_{1}\cup H_{2}\cup H_{3}\cup
H_{4})\bigg{|}-\bigg{|}V\big{(}\bigcup_{j\neq
i}H_{j}\big{)}\bigg{|}\leq|V(H)|-2.$

and

(5.2) $\displaystyle|V(H_{1}\cup H_{2}\cup H_{3}\cup
H_{4})|\leq\min_{\pi\in\mathbb{S}_{4}}\bigg{\\{}|V(H_{\pi_{1}}\cup
H_{\pi_{2}})|+|V(H_{\pi_{3}}\cup H_{\pi_{4}})|-2\bigg{\\}}.$

In the expression above, we take the minimum over $\pi\in\mathbb{S}_{4}$, the
set of permutations of $(1,2,3,4)$. We denote the collection of all good joins
of $H$ by $\mathcal{G}_{H}$, and by $N(\mathcal{G}_{H},G_{n})$ the number of
different good joins in $G_{n}$.

######  Theorem 5.3.

([14, Theorem 1.4]) Fix a connected graph $H$ with $v(H)=r\geq 3$ and consider
$Z(H,G_{n})$ defined in (1.2). Then, we have that

$d_{\mathrm{kol}}(Z(H,G_{n}),\mathcal{Z})\lesssim\left(\frac{N(\mathcal{G}_{H},G_{n})}{\sigma_{H}(G_{n})^{4}}\right)^{1/20}$

We will also use the following result (contained in the $c=2$ case of [14,
Proposition 4.3]).

######  Proposition 5.4 ([14]).

Fix connected graph $H$ with $v(H)=r$ and consider a graph sequence
$\\{G_{n}\\}$. For $\mathbf{s}\in V(G_{n})_{r}$, let

$W_{\mathbf{s}}:=\frac{1}{|\operatorname{Aut}(H)|}a_{H,\mathbf{s}}(\mathbf{1}\\{1_{X_{=\mathbf{s}}}\\}-{2}^{1-r})=\frac{1}{|\operatorname{Aut}(H)|}a_{H,\mathbf{s}}Z_{\mathbf{s}},$

where $Z_{\mathbf{s}}:=\mathbf{1}_{X_{=\mathbf{s}}}-2^{1-r},$ and observe that
$Z(H,G_{n})=\frac{1}{\sigma_{H}(G_{n})}\sum_{\mathbf{s}}W_{s}.$ Then,

$\displaystyle\mathbb{E}[Z(H,G_{n})^{4}]-3$
$\displaystyle=\frac{1}{\sigma_{H}(G_{n})^{4}}\sum_{\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}\in\mathcal{G}_{H}}\mathbb{E}[W_{\mathbf{s}_{1}}W_{\mathbf{s}_{2}}W_{\mathbf{s}_{3}}W_{\mathbf{s}_{4}}]$
$\displaystyle-\frac{3}{\sigma_{H}(G_{n})^{4}}\underbrace{\sum_{|\mathbf{s}_{1}\cap\mathbf{s}_{2}|\geq
2}\sum_{|\mathbf{s}_{3}\cap\mathbf{s}_{4}|\geq
2}}_{\\{\mathbf{s}_{1}\bigcup\mathbf{s}_{2}\\}\bigcap\\{|\mathbf{s}_{3}\bigcup\mathbf{s}_{4}\\}|\geq
2}\mathbb{E}[W_{\mathbf{s}_{1}}W_{\mathbf{s}_{2}}]\mathbb{E}[W_{\mathbf{s}_{3}}W_{\mathbf{s}_{4}}].$

In order to prove 5.1, we will need to understand more delicately which joins
make positive and negative contributions to the fourth moment error above.

######  Lemma 5.5.

For
$\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}\in\mathcal{G}_{H}$,
we have that

$\mathbb{E}[Z_{\mathbf{s}_{1}}Z_{\mathbf{s}_{2}}Z_{\mathbf{s}_{3}}Z_{\mathbf{s}_{4}}]=-2^{5-4r}+2^{3-2r}\sum_{i<j}2^{-|\mathbf{s}_{i}\cup\mathbf{s}_{j}|}-2^{2-r}\sum_{i=1}^{4}2^{-|\cup_{j\neq
i}\mathbf{s}_{j}|}+2^{1-|\cup_{i}\mathbf{s}_{i}|}$

###### Proof.

This follows by the principle of inclusion-exclusion:

$\displaystyle\mathbb{E}[Z_{\mathbf{s}_{1}}Z_{\mathbf{s}_{2}}Z_{\mathbf{s}_{3}}Z_{\mathbf{s}_{4}}]$
$\displaystyle=\sum_{A\subset[4]}(-1)^{4-|A|}\mathbb{E}\left[2^{(1-r)(4-|A|)}\prod_{j\in
A}\mathbf{1}\\{X_{=\mathbf{s}_{j}}\\}\right]$
$\displaystyle=\sum_{A\subset[4]}(-1)^{4-|A|}2^{(1-r)(4-|A|)+1-|\bigcup_{j\in
A}{\mathbf{s}}_{j}|}.$ $\displaystyle=2^{4(1-r)+1}-4\cdot
2^{3(1-r)+1-r}+\sum_{i<j}2^{2(1-r)+1-|\mathbf{s}_{i}\cup\mathbf{s}_{j}|}-\sum_{i=1}^{4}2^{(1-r)+1-|\cup_{j\neq
i}\mathbf{s}_{j}|}+2^{1-|\cup_{i}\mathbf{s}_{i}|}$
$\displaystyle=-2^{5-4r}+2^{3-2r}\sum_{i<j}2^{-|\mathbf{s}_{i}\cup\mathbf{s}_{j}|}-2^{2-r}\sum_{i=1}^{4}2^{-|\cup_{j\neq
i}\mathbf{s}_{j}|}+2^{1-|\cup_{i}\mathbf{s}_{i}|}.$

∎

Similarly to Eq. 4.1, we can more generally express
$\operatorname{Var}(T(H,G_{n}))$ in terms of total influences of subsets of
vertices, as computed explicitly in [14], and is the analog of (4.1) for more
general shapes.

######  Observation 5.6.

For connected graph $H$ with $v(H)=r,$ we have that

(5.3)
$\sigma_{H}(G_{n})^{2}=\operatorname{Var}(T(H,G_{n}))=\Theta\left(\sum_{k=2}^{r}\sum_{\mathbf{w}\in
V(G_{n})_{k}}D_{\mathbf{w}}(H,G_{n})^{2}\right)=\Theta\left(\sum_{\mathbf{w}\in
V(G_{n})_{2}}D_{\mathbf{w}}(H,G_{n})^{2}\right)$

With these pieces, we can show that if $G_{n}$ lacks influential pairs and the
fourth moment of $Z(H,G_{n})$ is asymptotically $3$, then $T(H,G_{n})$ is
asymptotically Gaussian.

###### Proof of 5.1.

We consider two cases on
$\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}\in\mathcal{G}_{H}$,
letting the corresponding $4$-join by this $4$-tuple be the graph
$H^{\prime}$.

  1. (1)

Suppose that for some $i\neq j$ $|\mathbf{s}_{i}\cap\mathbf{s}_{j}|\geq 2$
(without loss of generality take $i=1,j=2$). Then, by summing over pairs of
vertices $\mathbf{w}_{12}\subset\mathbf{s}_{1}\cap\mathbf{s}_{2}$, we get

$\frac{N(H^{\prime},G_{n})}{\sigma_{H}(G_{n})^{4}}\leq\frac{1}{\sigma_{H}(G_{n})^{4}}\sum\limits_{\begin{subarray}{c}\mathbf{w}_{12},\mathbf{w}_{3},\mathbf{w}_{4}\in
V(G_{n})_{2}\end{subarray}}D_{\mathbf{w}_{12}}(H,G_{n})^{2}D_{\mathbf{w}_{3}}(H,G_{n})D_{\mathbf{w}_{4}}(H,G_{n})\lesssim
M_{n}^{2}\frac{\sum\limits_{\mathbf{w}}D_{\mathbf{w}}(H,G_{n})^{2}}{\sigma_{H}(G_{n})^{2}}\lesssim
M_{n}^{2},$

where the final inequality follows by 5.6.

  2. (2)

Else
$\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}\in\mathcal{G}_{H}$
forms a good join $H^{\prime}$, where for every $i\neq j\in[4]$,
$|\mathbf{s}_{i}\cap\mathbf{s}_{j}|\leq 1$. The only contribution of such
joins to $\mathbb{E}[Z(H,G_{n})^{4}]-3$ is given by
$\frac{1}{\sigma_{H}^{4}}\mathbb{E}[W_{\mathbf{s}_{1}}W_{\mathbf{s}_{2}}W_{\mathbf{s}_{3}}W_{\mathbf{s}_{4}}]$.
Since every good join is connected, we must have $v(H^{\prime})\leq
r+3(r-1)=4r-3$. Further since this good join has no pair of copies of $H$ that
share more than $1$ vertex, we additionally have $v(H^{\prime})\geq 4r-6$. In
order for $\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}$
to be a good join, for at least $4$ of the $6$ pairs
$\\{\mathbf{s}_{i},\mathbf{s}_{j}\\}_{i\neq j}$, we must have
$|\mathbf{s}_{i}\cap\mathbf{s}_{j}|=1$. By Lemma 5.5, we have that

$\displaystyle\mathbb{E}[Z_{\mathbf{s}_{1}}Z_{\mathbf{s}_{2}}Z_{\mathbf{s}_{3}}Z_{\mathbf{s}_{4}}]$
$\displaystyle=-2^{5-4r}+2^{3-2r}\sum_{i<j}2^{-|\mathbf{s}_{i}\cup\mathbf{s}_{j}|}-2^{2-r}\sum_{i=1}^{4}2^{-|\cup_{j\neq
i}\mathbf{s}_{j}|}+2^{1-|\cup_{i}\mathbf{s}_{i}|}$
$\displaystyle\overset{(*)}{\geq}2^{5-4r}+2^{3-2r}\cdot(4\cdot
2^{-(2r-1)}+2\cdot 2^{-2r})-2^{2-r}\cdot(4\cdot
2^{-(v(H^{\prime})-(r-2))})+2^{1-v(H^{\prime})}$ $\displaystyle=7\cdot
2^{4-4r}-2^{1-v(H^{\prime})},$

where in (*), we used that $|\mathbf{s}_{i}\cap\mathbf{s}_{j}|=1$ for at least
$4$ pairs $\\{\mathbf{s}_{i},\mathbf{s}_{j}\\}_{i\neq j}$, and that since
$\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}$ forms a
good join, for any $i\in[4],$ $|\cup_{j\neq i}\mathbf{s}_{j}|\geq
v(H^{\prime})-(r-2)$. Since $7\cdot 2^{4-4r}-2^{1-v(H^{\prime})}>0$ for
$v(H^{\prime})\geq 4r-5$, we turn our attention to the case where
$v(H^{\prime})=4r-6$. In this case, we necessarily have
$|\mathbf{s}_{i}\cap\mathbf{s}_{j}|=1$ for all $6$ pairs, and the above bound
tightens to

$\displaystyle\mathbb{E}[Z_{\mathbf{s}_{1}}Z_{\mathbf{s}_{2}}Z_{\mathbf{s}_{3}}Z_{\mathbf{s}_{4}}]$
$\displaystyle=-2^{5-4r}+2^{3-2r}\sum_{i<j}2^{-|\mathbf{s}_{i}\cup\mathbf{s}_{j}|}-2^{2-r}\sum_{i=1}^{4}2^{-|\cup_{j\neq
i}\mathbf{s}_{j}|}+2^{1-|\cup_{i}\mathbf{s}_{i}|}$ $\displaystyle\geq
2^{5-4r}+2^{3-2r}\cdot(6\cdot 2^{-(2r-1)})-2^{2-r}\cdot(4\cdot
2^{-(v(H^{\prime})-(r-2))})+2^{1-v(H^{\prime})}$ $\displaystyle=0.$

The above estimates imply that for whenever
$\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}\in\mathcal{G}_{H}$
forms a good join $H^{\prime}$, where for every $i\neq j\in[4]$,
$|\mathbf{s}_{i}\cap\mathbf{s}_{j}|\leq 1$, we have
$\mathbb{E}[Z_{\mathbf{s}_{1}}Z_{\mathbf{s}_{2}}Z_{\mathbf{s}_{3}}Z_{\mathbf{s}_{4}}]\geq
0$.

Let $\widetilde{\mathcal{G}}_{H}\subset\mathcal{G}_{H}$ be the tuples
$\\{\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{s}_{3},\mathbf{s}_{4}\\}\in\mathcal{G}_{H}$
that form a good join $H^{\prime}$, where for every $i\neq j\in[4]$,
$|\mathbf{s}_{i}\cap\mathbf{s}_{j}|\leq 1$. Putting the pieces together from
the above two cases, we can conclude that

$\mathbb{E}[Z(H,G_{n})^{4}]-3\gtrsim-
M_{n}^{2}+\frac{1}{\sigma_{H}(G_{n})^{4}}\sum_{H^{\prime}\in\widetilde{\mathcal{G}}_{H}}N(H^{\prime},G_{n}).$

Combining the above inequality with 5.3 gives the desired result:

$\displaystyle d_{\mathrm{kol}}(Z(H,G_{n}),\mathcal{Z})$
$\displaystyle\lesssim\left(\frac{N(\mathcal{G}_{H},G_{n})}{\sigma_{H}(G_{n})^{4}}\right)^{1/20}$
$\displaystyle\lesssim\left(M_{n}^{2}+\left(\mathbb{E}[Z(H,G_{n})^{4}]-3\right)\right)^{1/20}.$

∎

###  5.2. Strongly Influential Pairs Forbid CLTs

We now give some evidence towards 1.5, by showing the conjecture holds for a
stronger notion of influence. Namely, we show that if $\\{G_{n}\\}$ has
strongly influential pairs, those forbid a CLT.

######  Definition 5.7 (Strongly influential vertices).

A $k$-tuple of vertices $\mathbf{w}\in V(G_{n})_{k}$ is $\varepsilon$-strongly
influential, if $D_{\mathbf{w}}(H,G_{n})\geq\varepsilon N(H,G_{n}).$

It is readily seen that $N(H,G_{n})\gtrsim\sigma_{H}(G_{n})$, which justifies
calling the tuple in the above definition _strongly_ influential. Below we
observe that when $G_{n}$ contains an influential pair, then $Z(H,G_{n})$ will
be bounded almost surely, _uniformly in $n$_. Clearly, $Z(H,G_{n})$ is not a
Gaussian in this case.

######  Proposition 5.8.

Consider a fixed $H$ and graph sequence $\\{G_{n}\\}$. If for all $N$, there
exists some $n>N$ such that $G_{n}$ has a strongly influential pair of
vertices $\mathbf{w}=(v,w)\in V(G_{n})_{2}$, then
$Z(H,G_{n})\centernot{\xrightarrow{\text{in law}}}\mathscr{N}(0,1)$.

###### Proof.

Fix connected simple graph $H$ on $r$ vertices. Consider graph $G_{n}$ with
strongly influential vertex pair $\mathbf{z}\in V(G_{n})_{2},$ so that
$D_{\mathbf{z}}(H,G_{n})\gtrsim T(H,G_{n}).$ Per 5.6, we can lower bound the
variance as

$\sigma_{H}(G_{n})^{2}\gtrsim D_{\mathbf{z}}(H,G_{n})^{2}\gtrsim
N(H,G_{n})^{2}$

However, since $N(H,G_{n})\geq T(H,G_{n})$, this implies that

$Z(H,G_{n})=\frac{T(H,G_{n})-\mathbb{E}T(H,G_{n})}{\sigma_{H}(G_{n})}\leq\frac{T(H,G_{n})}{\sigma_{H}(G_{n})}=O(1)$

is bounded almost surely. Therefore,
$Z(H,G_{n})\centernot{\xrightarrow{\text{in law}}}\mathscr{N}(0,1)$. ∎

######  Remark.

There are some other more specific cases where influential pairs can forbid a
CLT. For example, suppose that $H=K_{4}$, so that as in Eq. 2.9,
$F_{H,G}=F_{H,G,0}+F_{H,G,2}+F_{H,G,4}$. The calculations in Lemma 3.5 show
that

$\mathbb{E}\left[F_{H,G,4}^{2}\right]\leq N(H,G)\text{ and
}\mathbb{E}\left[F^{2}_{H,G,2}\right]\gtrsim\max\limits_{v\in
V(G)}D_{v}^{2}(H,G).$

Thus, let $\\{G_{n}\\}$ be a sequence of graphs satisfying
$D_{v}(H,G_{n})\gg\sqrt{N(H,G_{n})}$, and set $\widetilde{F_{H,G}}$ as in
Lemma 3.6. Then, $\widetilde{F_{H,G_{n}}}=\widetilde{F_{H,G_{n},2}}+o(1)$ is
asymptotically a quadratic function, and the assertions of Section 4 hold in
this case as well. Note that the requirement
$D_{v}(H,G_{n})\gg\sqrt{N(H,G_{n})}$ is much weaker than having a strongly
influential pair, yet still stronger than
$D_{v}(H,G_{n})=\Omega\left(\sigma_{H}(G_{n})\right)$.

###  5.3. Aligning Higher Moments with Influential Edges

In 4.1, we showed that the existence of an influential edge precludes
convergence of $Z(\triangle,G_{n})$ to a standard Gaussian $\mathcal{Z}$. Our
approach was to study the tail behavior of an associated quadratic form in
Gaussian variables and to apply the identifiability of Gaussian mixtures. For
more general $H$, per 1.5, we expect influential pairs of vertices to
similarly preclude a central limit theorem. One very natural strategy to try
to exclude a CLT is to study higher moments of $Z(H,G_{n})$ and demonstrate
that e.g. if $\mathbb{E}[Z(H,G_{n})^{4}]\simeq 3$, then the $6$th (or higher)
moment must disagree with that of a standard Gaussian. Below, we give an
example that illustrates a limitation of this type of plan by exhibiting a
sequence of graphs where the first $6$ moments of $Z(\triangle,G_{n})$ all
line up with a standard Gaussian, but per 4.1 we can see that a CLT fails to
hold.

We give a sequence of graphs $\\{G_{n}\\}$ where
$\mathbb{E}[Z(\triangle,G_{n})^{4}]\to 3,\mathbb{E}[Z(\triangle,G_{n})^{6}]\to
15$, but $Z(\triangle,G_{n})$ can be shown to not be asymptotically normal. We
let $G_{n}=S_{n}\sqcup P_{n}\sqcup B_{n}$ be the disjoint union of three
graphs that we define below:

$\displaystyle V(S_{n})$
$\displaystyle=\\{v_{k}\\}_{k\in[4]}\cup\left\\{t^{(k)}_{i}\right\\}_{i\in[n],k\in[4]},$
$\displaystyle\qquad
E(S_{n})=\left\\{\left(v_{k},v_{k+1(4)}\right)\\}_{k\in[4]}\cup\\{\left(v_{k},t^{(k)}_{i}\right),\left(t^{(k)}_{i},v_{k+1(4)}\right)\right\\}_{i\in[n],k\in[4]}$
$\displaystyle V(P_{n})$
$\displaystyle=\\{w,x\\}\cup\left\\{p_{i}\right\\}_{i\in[cn]},$
$\displaystyle\qquad
E(P_{n})=\left\\{\left(w,x\right)\\}\cup\\{\left(w,p_{i}\right),\left(p_{i},x\right)\right\\}_{i\in[cn]}$
$\displaystyle V(B_{n})$
$\displaystyle=\\{y_{i}\\}_{i\in[bn^{2}]}\cup\left\\{\ell^{(ij)}_{0},\ell^{(ij)}_{i},\ell^{(ij)}_{j},r^{(ij)}_{0},r^{(ij)}_{i},r^{(ij)}_{j}\right\\}_{i<j\in[bn^{2}]}$
$\displaystyle\qquad
E(B_{n})=\left\\{(y_{i},\ell_{0}^{(ij)}),(y_{i},\ell_{i}^{(ij)}),(\ell_{i}^{(ij)},\ell_{0}^{(ij)}),(y_{j},\ell_{0}^{(ij)}),(y_{j},\ell_{j}^{(ij)}),(\ell_{j}^{(ij)},\ell_{0}^{(ij)})\right\\}_{i<j\in[bn^{2}]}$
$\displaystyle\qquad\qquad\qquad\quad\cup\left\\{(y_{i},r_{0}^{(ij)}),(y_{i},r_{i}^{(ij)}),(r_{i}^{(ij)},r_{0}^{(ij)}),(y_{j},r_{0}^{(ij)}),(y_{j},r_{j}^{(ij)}),(r_{j}^{(ij)},r_{0}^{(ij)})\right\\}_{i<j\in[bn^{2}]}$

$G_{n}$ is pictured in Fig. 1.

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$S_{4}$

$w$$x$$P_{4}\,(c=2)$

$y_{1}$$y_{2}$$y_{3}$$B_{4}\,(b=\frac{3}{16})$$r_{0}^{(12)}$$r_{1}^{(12)}$$r_{2}^{(12)}$$\ell_{0}^{(12)}$$\ell_{1}^{(12)}$$\ell_{2}^{(12)}$$r_{0}^{(13)}$$r_{1}^{(13)}$$r_{3}^{(13)}$$\ell_{0}^{(13)}$$\ell_{1}^{(13)}$$\ell_{3}^{(13)}$$r_{0}^{(23)}$$r_{2}^{(23)}$$r_{3}^{(23)}$$\ell_{0}^{(23)}$$\ell_{2}^{(23)}$$\ell_{3}^{(23)}$

Figure 1. An example of a graph $G_{n}$ with $n=4,b=3/16,c=2$ as a disjoint
union of graphs $S_{4},P_{4},B_{4}$ as pictured

Let
$T^{\prime}(\triangle,G_{n})=4(T(\triangle,G_{n})-\mathbb{E}[T(\triangle,G_{n})])$
(centered but not normalized). Per Eq. 4.1,

$\mathbb{E}[T^{\prime}(\triangle,G_{n})^{2}]=\sum_{e\in
E(G)}D_{e}^{2}(\triangle,G).$

We then compute the fourth moment by expanding the representation of
$T(\triangle,G_{n})$ of Eq. 1.1, noticing that some terms vanish. Simplifying
yields the following:

$\displaystyle\mathbb{E}[T^{\prime}(\triangle,G_{n})^{4}]$
$\displaystyle=3\left(\sum_{e\in
E(G_{n})}D_{e}^{2}(\triangle,G_{n})\right)^{2}-2\sum_{e\in
E(G_{n})}D_{e}^{4}(\triangle,G_{n})$
$\displaystyle\qquad+24\sum_{C_{4}\in\mathcal{C}_{4}(G_{n})}\prod_{e\in
E(C_{4})}D_{e}(\triangle,G_{n})+o(\sigma_{\triangle}^{4}),$ where the latter
term is a sum over all of the $4$-cycle’s in $G$, requiring that no two
$4$-cycles in the sum have the same edge set. We similarly compute the sixth
moment as follows $\displaystyle\mathbb{E}[T^{\prime}(\triangle,G_{n})^{6}]$
$\displaystyle=720\sum_{C_{6}\in\mathcal{C}_{6}(G_{n})}\prod_{e\in
E(C_{6})}D_{e}(\triangle,G_{n})-240\sum_{C_{4}\in\mathcal{C}_{4}(G_{n})}\left(\prod_{e\in
C_{4}}D_{e}(\triangle G_{n})\right)\left(\sum_{e\in
C_{4}}D_{e}(\triangle,G_{n})^{2}\right)$
$\displaystyle\qquad+15\left(\sum_{e\in
E(G_{n})}D_{e}(\triangle,G_{n})^{2}\right)^{3}+16\sum_{e\in
E(G_{n})}D_{e}(\triangle,G_{n})^{6}+o(\sigma_{\triangle}^{6}).$

When we specialize in the sequence of graphs chosen above, we obtain the
following moments.

$\displaystyle\mathbb{E}[T^{\prime}(\triangle,G_{n})^{4}]$
$\displaystyle=3\mathbb{E}[T^{\prime}(\triangle,G_{n})^{2}]^{2}-2(4n^{4}+(cn)^{4})+24\left(n^{4}+\binom{bn^{2}}{2}\right)+o(n^{4})$
$\displaystyle\mathbb{E}[T^{\prime}(\triangle,G_{n})^{6}]$
$\displaystyle=-240\cdot
4n^{6}+15\mathbb{E}[T^{\prime}(\triangle,G_{n})^{2}]^{3}+16(4n^{6}+(cn)^{6})+o(n^{6})$

Then, if we choose $b=\sqrt{\frac{2}{3}\left(7^{2/3}-2\right)}\approx
1.0518,c=\sqrt{2}\cdot 7^{1/6}\approx 1.956$, we find that as $n\to\infty$,
$\mathbb{E}[T^{\prime}(\triangle,G_{n})^{4}]\longrightarrow
3\mathbb{E}[T^{\prime}(\triangle,G_{n})^{2}]^{2}$ and
$\mathbb{E}[T^{\prime}(\triangle,G_{n})^{6}]\longrightarrow
15\mathbb{E}[T^{\prime}(\triangle,G_{n})^{2}]^{3}$, meaning that the
normalized versions satisfy $\mathbb{E}[Z(\triangle,G_{n})^{4}]\to
3,\mathbb{E}[Z(\triangle,G_{n})^{6}]\to 15$.

However, we can see that $T(\triangle,G_{n})$ is not asymptotically normal, by
noting that
$T(\triangle,G_{n})=T(\triangle,S_{n})+T(\triangle,P_{n})+T(\triangle,B_{n})$
is the sum of three independent (in fact with disjoint vertex support) random
variables. Note that by considering whether or not $w,x\in V(P_{n})$ receive
the same or different colors, we see that the random variable
$T(\triangle,P_{n})$ is equivalent in distribution to

$T(\triangle,P_{n})\equiv\frac{1}{2}\delta_{0}+\frac{1}{2}\operatorname{Bin}(n,1/2).$

By a similar argument to that appearing in Section 4.2 of [6], independence of
the three constituents of $T(\triangle,G_{n})$ and the above characterization
of $T(\triangle,P_{n})$ (which is in the limit a $2$-point discrete
distribution) yields that $T(\triangle,G_{n})$ is not asymptotically Gaussian.

## References

  * [1] Richard Arratia, Skip Garibaldi, and Joe Kilian.  Asymptotic distribution for the birthday problem with multiple coincidences, via an embedding of the collision process.  Random Structures Algorithms, 48(3):480–502, 2016.
  * [2] A. D. Barbour, Lars Holst, and Svante Janson.  Poisson approximation, volume 2 of Oxford Studies in Probability.  The Clarendon Press, Oxford University Press, New York, 1992.  Oxford Science Publications.
  * [3] Andrew C. Berry.  The accuracy of the Gaussian approximation to the sum of independent variates.  Trans. Amer. Math. Soc., 49:122–136, 1941.
  * [4] Bhaswar B. Bhattacharya, Sayan Das, and Sumit Mukherjee.  Motif estimation via subgraph sampling: the fourth-moment phenomenon.  Ann. Statist., 50(2):987–1011, 2022.
  * [5] Bhaswar B. Bhattacharya, Persi Diaconis, and Sumit Mukherjee.  Universal limit theorems in graph coloring problems with connections to extremal combinatorics.  Ann. Appl. Probab., 27(1):337–394, 2017.
  * [6] Bhaswar B. Bhattacharya, Xiao Fang, and Han Yan.  Normal approximation and fourth moment theorems for monochromatic triangles.  Random Structures Algorithms, 60(1):25–53, 2022.
  * [7] Bhaswar B Bhattacharya, Somabha Mukherjee, and Sumit Mukherjee.  The second-moment phenomenon for monochromatic subgraphs.  SIAM Journal on Discrete Mathematics, 34(1):794–824, 2020.
  * [8] Bhaswar B. Bhattacharya and Sumit Mukherjee.  Monochromatic subgraphs in randomly colored graphons.  European J. Combin., 81:328–353, 2019.
  * [9] Bhaswar B Bhattacharya, Sumit Mukherjee, and Jaesung Son.  A fourth moment phenomenon for asymptotic normality.  in preparation.
  * [10] Bhaswar B Bhattacharya, Sumit Mukherjee, and Jaesung Son.  The second-moment phenomenon for monochromatic subgraphs.  in preparation.
  * [11] Ron Blei and Svante Janson.  Rademacher chaos: tail estimates versus limit theorems.  Ark. Mat., 42(1):13–29, 2004.
  * [12] Annalisa Cerquetti and Sandra Fortini.  A Poisson approximation for coloured graphs under exchangeability.  Sankhyā, 68(2):183–197, 2006.
  * [13] Louis H. Y. Chen, Larry Goldstein, and Qi-Man Shao.  Normal approximation by Stein’s method.  Probability and its Applications (New York). Springer, Heidelberg, 2011\.
  * [14] Sayan Das, Zoe Himwich, and Nitya Mani.  A fourth-moment phenomenon for asymptotic normality of monochromatic subgraphs.  Random Structures Algorithms, 63(4):968–996, 2023.
  * [15] Anirban DasGupta.  The matching, birthday and the strong birthday problem: a contemporary review.  J. Statist. Plann. Inference, 130(1-2):377–389, 2005.
  * [16] Persi Diaconis and Frederick Mosteller.  Methods for studying coincidences.  J. Amer. Statist. Assoc., 84(408):853–861, 1989.
  * [17] Christian Döbler and Kai Krokowski.  On the fourth moment condition for Rademacher chaos.  Ann. Inst. Henri Poincaré Probab. Stat., 55(1):61–97, 2019\.
  * [18] Xiao Fang.  A universal error bound in the CLT for counting monochromatic edges in uniformly colored graphs.  Electron. Commun. Probab., 20:no. 21, 6, 2015.
  * [19] Steven D. Galbraith and Mark Holmes.  A non-uniform birthday problem with applications to discrete logarithms.  Discrete Appl. Math., 160(10-11):1547–1560, 2012.
  * [20] Jeong Han Kim, Ravi Montenegro, Yuval Peres, and Prasad Tetali.  A birthday paradox for Markov chains with an optimal bound for collision in the Pollard rho algorithm for discrete logarithm.  Ann. Appl. Probab., 20(2):495–521, 2010.
  * [21] Nathan Linial.  Local-global phenomena in graphs.  Combin. Probab. Comput., 2(4):491–503, 1993.
  * [22] Dominique Malicet, Ivan Nourdin, Giovanni Peccati, and Guillaume Poly.  Squared chaotic random variables: new moment inequalities with applications.  J. Funct. Anal., 270(2):649–670, 2016.
  * [23] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz.  Noise stability of functions with low influences: invariance and optimality.  Ann. of Math. (2), 171(1):295–341, 2010.
  * [24] Salim Noreddine and Ivan Nourdin.  On the Gaussian approximation of vector-valued multiple integrals.  J. Multivariate Anal., 102(6):1008–1017, 2011.
  * [25] Ivan Nourdin and Giovanni Peccati.  Stein’s method on Wiener chaos.  Probab. Theory Related Fields, 145(1-2):75–118, 2009.
  * [26] Ivan Nourdin and Giovanni Peccati.  Normal approximations with Malliavin calculus: from Stein’s method to universality.  Number 192 in Cambridge Tracts in Mathematics. Cambridge University Press, 2012.
  * [27] Ivan Nourdin, Giovanni Peccati, and Gesine Reinert.  Invariance principles for homogeneous sums: universality of Gaussian Wiener chaos.  Ann. Probab., 38(5):1947–1985, 2010.
  * [28] Ivan Nourdin and Guillaume Poly.  Convergence in law in the second Wiener/Wigner chaos.  Electron. Commun. Probab., 17:no. 36, 12, 2012.
  * [29] David Nualart and Giovanni Peccati.  Central limit theorems for sequences of multiple stochastic integrals.  Ann. Probab., 33(1):177–193, 2005.
  * [30] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, New York, 2014.
  * [31] Henry Teicher.  Identifiability of finite mixtures.  Ann. Math. Statist., 34:1265–1269, 1963.
  * [32] Cédric Villani.  Optimal transport, volume 338 of Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, 2009.  Old and new.
  * [33] Guangqu Zheng.  A Peccati-Tudor type theorem for Rademacher chaoses.  ESAIM Probab. Stat., 23:874–892, 2019.

##  Appendix A Bounding the Kolmogorov Distance by the $d_{2}$istance

######  Lemma A.1.

Let $\mathcal{Z}\sim\mathscr{N}(0,1)$ and $Y$ be any random variable, then,

$\sup\limits_{t\in\mathbb{R}}\left|\mathbb{P}\left(Y\leq
t\right)-\mathbb{P}\left(\mathcal{Z}\leq t\right)\right|\lesssim
d_{2}(Y,\mathcal{Z})^{\frac{1}{3}}.$

###### Proof.

The proof is rather standard and follows, as in [13, Theorem 3.3], by
regularizing the step function. Thus, for a positive small $\delta>0$, and
$t\in\mathbb{R}$, set

$h_{t,\delta}(x)=\begin{cases}1&x\leq t\\\
\frac{((t+\delta-x)^{3}(6t^{2}+\delta^{2}+3\delta
x+6x^{2}-3t(\delta+4x)))}{\delta^{5}}&t<x<t+\delta\\\ 0&x\geq
t+\delta\end{cases}.$

The values of $h_{t,\delta}$ in $[t,t+\delta]$ were chosen as the unique
minimal degree interpolating polynomial to ensure that $h_{t,\delta}$ is twice
continuously differentiable in $\mathbb{R}$. In particular, a straightforward,
but tedious, calculation shows

$\|h_{t,\delta}^{\prime}\|_{\infty}\leq\frac{15}{8\delta}\text{ and
}\|h_{t,\delta}^{\prime\prime}\|_{\infty}\leq\frac{10}{\sqrt{3}\delta^{2}}.$

Thus, for small $\delta$,
$\|h_{t,\delta}\|_{C_{2}}\leq\frac{10}{\sqrt{3}\delta^{2}}$, and

$\left|\mathbb{E}\left[h_{t,\delta}(Y)\right]-\mathbb{E}\left[h_{t,\delta}(\mathcal{Z})\right]\right|\leq\frac{10}{\sqrt{3}\delta^{2}}d_{2}(Y,\mathcal{Z}).$

Since $0<h_{t,\delta}(x)<1$ for $x\in(t,t+\delta)$ we may conclude,

$\displaystyle\mathbb{P}\left(Y\leq t\right)-\mathbb{P}\left(\mathcal{Z}\leq
t\right)$
$\displaystyle\leq\mathbb{E}\left[h_{t,\delta}(Y)\right]-\mathbb{P}\left(\mathcal{Z}\leq
t\right)$
$\displaystyle=|\mathbb{E}\left[h_{t,\delta}(Y)\right]-\mathbb{E}\left[h_{t,\delta}(\mathcal{Z})\right]|+|\mathbb{E}\left[h_{t,\delta}(\mathcal{Z})\right]-\mathbb{P}\left(\mathcal{Z}\leq
t\right)|$
$\displaystyle\leq\frac{10}{\sqrt{3}\delta^{2}}d_{2}(Y,\mathcal{Z})+\mathbb{P}\left(t<\mathcal{Z}<t+\delta\right)$
$\displaystyle\leq\frac{10}{\sqrt{3}\delta^{2}}d_{2}(Y,\mathcal{Z})+\frac{\delta}{\sqrt{2\pi}}.$

Optimizing over $\delta$, we get $\mathbb{P}\left(Y\leq
t\right)-\mathbb{P}\left(\mathcal{Z}\leq t\right)\leq
2d_{2}(X,\mathcal{Z})^{\frac{1}{3}},$ and a similar argument bounds
$\mathbb{P}\left(\mathcal{Z}\leq t\right)-\mathbb{P}\left(Y\leq t\right)$. ∎