2.1. Preliminaries

A quantity that will play a central role in our analysis the homomorphism density of a fixed multigraph $F=(V(F), E(F))$ (without loops) in a graphon $W$ , which is defined as

(2.1) \begin{align} t(F,W)=\int _{[0,1]^{|V(F)|}}\prod _{(s, t) \in E(F)}W(x_{s},x_{t})\prod _{a=1}^{|V(F)|}\,\textrm{d} x_{a}. \end{align}

Note that this is the natural continuum analogue of the homomorphism density of a fixed graph $F=(V(F), E(F))$ into finite (unweighted) graph $G=(V(G), E(G))$ which is defined as

(2.2) \begin{align} t(F, G) \;:\!=\;\frac{|\hom (F,G)|}{|V (G)|^{|V (F)|}}, \end{align}

where $|\hom (F,G)|$ denotes the number of homomorphisms of $F$ into $G$ . In fact, it is easy to verify that $t(F, G) = t(F, W^{G})$ , where $W^{G}$ is the empirical graphon associated with the graph $G$ which defined as

(2.3) \begin{align} W^G(x, y) =\boldsymbol 1\{(\lceil |V(G)|x \rceil, \lceil |V(G)|y \rceil )\in E(G)\}. \end{align}

(In other words, to obtain the empirical graphon $W^G$ from the graph $G$ , partition $[0, 1]^2$ into $|V(G)|^2$ squares of side length $1/|V(G)|$ , and let $W^G(x, y)=1$ in the $(i, j)$ -th square if $(i, j)\in E(G)$ , and 0 otherwise.)

Let $H=(V(H), E(H))$ be a simple graph. For convenience, we will throughout the paper assume that $V(H)=\{1, 2, \ldots,|V(H)|\}$ . Then, the homomorphism density defined (2.1) can also interpreted as the probability that a $W$ -random graph on $|V(H)|$ vertices contains $H$ , that is,

(2.4) \begin{align} t(H,W)=\mathbb{P}(G(|V(H)|,W)\supseteq H). \end{align}

To see this, recall the construction of a $W$ -random graph and note from (2.1) that,

(2.5) \begin{align} t(H,W)=\mathbb{E}\left [\prod _{(a,b)\in E(H)}W(U_{a},U_{b})\right ] & = \mathbb{E}\left [\prod _{(a,b)\in E(H)} \textbf{1}\{ Y_{ab}\leq W(U_{a},U_{b}) \}\right ] \nonumber \\[5pt] & = \mathbb{E}\left [ \textbf{1}\{G(|V(H)|,W)\supseteq H \}\right ]. \end{align}

Next, recalling (1.1) note that

(2.6) \begin{align} \mathbb{E}X_{n}(H,W) &=\sum _{1\leq i_{1}\lt \cdots \lt i_{|V(H)|}\leq n}\sum _{H'\in \mathscr{G}_H(\{i_{1},\ldots, i_{|V(H)|}\})}t(H,W) \nonumber \\[5pt] &= \big(\begin{array}{c}{n}\\[-8pt] {|V(H)|}\end{array}\big) \left |\mathscr{G}_H( \{ 1,\ldots, |V(H)| \} ) \right | \cdot t(H,W) \end{align}

where the last equality follows since the number of subgraphs of $K_{|V(H)|}$ on $\{i_{1},\ldots, i_{|V(H)|}\}$ isomorphic to $H$ is the same for any collection of distinct indices $1\leq i_{1}\lt \cdots \lt i_{|V(H)|}\leq n$ . Clearly,

(2.7) \begin{align} \left |\mathscr{G}_H( \{ 1,\ldots, |V(H)| \} ) \right | = \frac{|V(H)|!}{|\textrm{Aut}(H)|}, \end{align}

where $\textrm{Aut}(H)$ is the collection of all automorphisms of $H$ , that is, the collection of permutations $\sigma$ of the vertex set $V(H)$ such that $(x, y) \in E(H)$ if and only if $(\sigma (x), \sigma (y)) \in E(H)$ . This implies, from (2.6),

(2.8) \begin{align} \mathbb{E}X_{n}(H,W) = \frac{(n)_{|V(H)|}}{|\textrm{Aut}(H)|}t(H,W), \end{align}

where $(n)_{|V(H)|}\;:\!=\;n(n-1)\cdots (n-|V(H)|+1)$ .

2.2. Conditional homomorphism densities and $H$ -regularity

In this section, we will formalise the notion of $H$ -regularity of a graphon $W$ . To this end, we need to introduce the notion of conditional homomorphism densities. Throughout, we will assume $H=(V(H), E(H))$ is a non-empty simple graph with vertices labelled $V(H)=\{1, 2, \ldots, |V(H)|\}$ .

Definition 2.1. Fix $1 \leq K \leq |V(H)|$ and an ordered set $\boldsymbol{a}= (a_1, a_2, \ldots, a_K)$ of distinct vertices $a_1, a_2, \ldots, a_K \in V(H)$ . Then the $K$ -point conditional homomorphism density function of $H$ in $W$ given $\boldsymbol{a}$ is defined as

(2.9) \begin{align} t_{\boldsymbol{a}}(\boldsymbol{x},H,W) &\;:\!=\;\mathbb{E}\left [\prod _{(a,b)\in E(H)}W(U_{a},U_{b})\Bigm |U_{a_{j}}=x_{j}, \text{ for } 1\leq j \leq K \right ] \notag \\[5pt] &\phantom \;:\!=\; \mathbb{P}\left (G(|V(H)|,W)\supseteq H \bigm | U_{a_{j}}=x_{j}, \text{ for } 1\leq j \leq K \right ), \end{align}

where $\boldsymbol{x}= (x_1, x_2, \ldots, x_K)$ . In other words, $t_{\boldsymbol{a}}(\boldsymbol{x},H,W)$ is the homomorphism density of $H$ in the graphon $W$ when the vertex $a_j \in V(H)$ is marked with the value $x_j \in [0, 1]$ , for $1 \leq j \leq K$ .

The conditional homomorphism densities will play a crucial role in the description of the limiting distribution of $X_n(H, W)$ . In particular, the $H$ -regularity of a graphon $W$ is determined by the 1-point conditional homomorphism densities, which we formalise below:

Definition 2.2. ( $H$ -regularity of a graphon) A graphon $W$ is said to be $H$ -regular if

(2.10) \begin{align} \overline{t}(x,H,W) \;:\!=\; \frac{1}{|V(H)|}\sum _{a=1}^{|V(H)|}t_a(x,H,W)=t(H,W), \end{align}

for almost every $x \in [0, 1]$ .

Note that in (2.10) it is enough to assume that $\overline{t}(x,H,W)$ is a constant for almost every $x \in [0, 1]$ . This is because

(2.11) \begin{align} \int _0^1 t_{a}(x,H,W) \,\textrm{d} x = t(H, W), \end{align}

for all $a \in V(H)$ . Hence, if $\overline{t}(x,H,W)$ is a constant a.e., then the constant must be $t(H, W)$ . Therefore, in other words, a graphon $W$ is $H$ -regular if the homomorphism density of $H$ in $W$ when one of the vertices of $H$ is marked, is a constant independent of the value of the marking.

Remark 2.3. Note that when $H=K_r$ is the $r$ -clique, for some $r \geq 2$ , then $t_{a}(x,H,W)=t_{b}(x,H,W)$ , for all $1 \leq a \ne b \leq r$ . Hence, (2.10) simplifies to

(2.12) \begin{align} t_{1}(x,K_r,W) = \mathbb{E}\left [\prod _{1\leq a \lt b \leq r}W(U_{a},U_{b})\biggm |U_{1}=x\right ] = t(H,W), \text{ for almost every } x \in [0, 1], \end{align}

which is precisely the notion of $K_{r}$ -regularity defined in [Reference Hladký, Pelekis and Šileikis17].

Remark 2.4. Recall that the degree function of a graphon $W$ is defined as

(2.13) \begin{align} d_{W}(x)\;:\!=\;\int _{[0,1]}W(x,y) \,\textrm{d} y. \end{align}

Note that for $H=K_2$ , (2.9) yields

(2.14) \begin{align} t_{1}(x,K_2,W) = \mathbb{E}\left [W(U_{1},U_{2})\bigm |U_{1}=x\right ] = \int _{[0,1]}W(x,y) \,\textrm{d} y = d_{W}(x). \end{align}

Hence, the notion of $K_2$ -regularity coincides with the standard notion of degree regularity, where the degree function $ d_{W}(x)\;:\!=\;\int _{[0,1]}W(x,y) \,\textrm{d} y$ is constant a.e.

2.3. Spectrum of graphons and 2-point conditional densities

Hereafter, we denote by $\mathcal{W}_0$ the space of all graphons, which is the collection of all symmetric, measurable functions $W \;:\;[0, 1]^2\rightarrow [0, 1]$ . We let also $\mathcal{W}_1$ be the space of all bounded, symmetric, measurable functions $W \;:\; [0, 1]^2\rightarrow [0, \infty )$ . Every graphon $W\in \mathcal{W}_0$ , or more generally $W\in \mathcal{W}_1$ , defines an operator $T_{W}\;:\;L^{2}[0,1]\rightarrow L^{2}[0,1]$ as follows:

(2.15) \begin{equation} (T_Wf)(x)=\int _0^1W(x, y)f(y)\,\textrm{d} y, \end{equation}

for each $f\in L^{2}[0,1]$ . $T_W$ is a symmetric Hilbert–Schmidt operator; thus it is compact and has a discrete spectrum, that is, it has a countable multiset of non-zero real eigenvalues, which we denote by ${\textrm{Spec}}(W)$ , with

(2.16) \begin{align} \sum _{\lambda \in{\textrm{Spec}}(W)}\lambda ^2=\iint W(x,y)^2\,\textrm{d} x\,\textrm{d} y\lt \infty . \end{align}

Moreover, a.e.,

(2.17) \begin{align} (T_{W}f)(x)=\sum _{\lambda \in{\textrm{Spec}}(W)}\lambda \langle f,\phi _{\lambda }\rangle \phi _{\lambda }(x) \end{align}

and

(2.18) \begin{align} W(x,y)=\sum _{\lambda \in{\textrm{Spec}}(W)}\lambda \phi _{\lambda }(x)\phi _{\lambda }(y), \end{align}

where $\{\phi _{\lambda }\}_{\lambda \in{\textrm{Spec}}(W)}$ denotes an orthonormal system of eigenfunctions associated with ${\textrm{Spec}}(W)$ . For a more detailed discussion on the spectral properties of graphons and their role in graph limit theory, see [Reference Lovász25, Chapters 7, 11].

To describe the limiting distribution of $X_n(H, W)$ when $W$ is $H$ -regular, we will need to understand the spectral properties of the following graphon obtained from the 2-point conditional densities:

Definition 2.5. Given a graphon $W \in \mathcal{W}_0$ and a simple connected graph $H=(V(H), E(H))$ , the 2-point conditional graphon induced by $H$ is defined as

(2.19) \begin{align} W_{H}(x,y)=\frac{1}{2|\textrm{Aut}(H)|}\sum _{1\leq a\neq b\leq |V(H)|}t_{a, b}((x,y),H,W), \end{align}

where $t_{a, b}((x,y),H,W)$ is the $2$ -point conditional homomorphism density function of $H$ in $W$ given the vertices $(a, b)$ , as in Definition 2.1.Footnote ¹ (The normalisation factor in (2.19) is chosen for later convenience in e.g. (2.25).)

Intuitively, $W_{H}(x,y)$ can be interpreted as the homomorphism density of $H$ in $W$ containing the ‘vertices’ $x, y \in [0, 1]$ .

Note that a graphon $W$ is $H$ -regular (see Definition 2.2) if and only if the 2-point conditional graphon $W_H$ is degree regular (see Remark 2.4). This is because, for all $x \in [0, 1]$ ,

(2.20) \begin{align} \int _0^1 W_{H}(x,y)\,\textrm{d} y & = \frac{|V(H)|-1}{2|\textrm{Aut}(H)|}\sum _{a=1}^{|V(H)|}t_{a}(x,H,W), \end{align}

and the RHS of (2.20) is a constant if and only if $W$ is $H$ -regular. In fact, if $W$ is $H$ -regular, then $\frac{1}{|V(H)|} \sum _{a=1}^{|V(H)|}t_{a}(x,H,W) = t(H, W)$ a.e.; hence, the degree of $W_H$ becomes

(2.21) \begin{align} \int _0^1 W_{H}(x,y)\,\textrm{d} y = \frac{|V(H)|(|V(H)|-1)}{2|\textrm{Aut}(H)|} \cdot t(H, W) & \;:\!=\; d_{W_H}, \end{align}

for almost every $x \in [0, 1]$ . This implies that, if $W$ is $H$ -regular, then $d_{W_H}$ is an eigenvalue of the operator $T_{W_H}$ (recall (2.15)) and $\phi \equiv 1$ is a corresponding eigenvector. In this case, we will use ${\textrm{Spec}}^{-}(W_{H})$ to denote the collection ${\textrm{Spec}}(W_H)$ with the multiplicity of the eigenvalue $d_{W_H}$ decreased by $1$ . (Note that $d_{W_H}\gt 0$ by (2.21) unless $t(H,W)=0$ , or $|V(H)|=1$ ; these cases are both trivial, see Remark 2.10.)

Figure 1.

The $(a, b)$ -vertex join of the graphs $H_1$ and $H_2$ .

2.4. Statement of the main result

To state our results on the asymptotic distribution of $X_{n}(H,W)$ , we need to define a few basic graph operations.

Definition 2.6. For a graph $H=(V(H),E(H))$ on vertex set $\{1,2,\cdots, r\}$ define,

(2.22) \begin{align} E^{+}(H)=\{(a,b)\;:\;1\leq a\neq b\leq r, (a,b) \text{ or } (b,a)\in E(H)\} \end{align}

Figure 2.

The weak and strong edge joins of the graphs $H_1$ and $H_2$ .

Having introduced the framework and the relevant definitions, we are now ready to state our main result regarding the asymptotic distribution of $X_n(H, W)$ , the number of copies of $H$ in the $W$ -random graph $G(n, W)$ .

The sum in (2.25) may be infinite, but it converges in $L^2$ and a.s. by (2.16) (see [Reference Kallenberg23, Lemma 4.16]). The proof of Theorem 2.9 uses the projection method for generalised $U$ -statistics developed in Janson and Nowicki [Reference Janson and Nowicki22], which allows us to decompose $X_{n}(H,W)$ over sums of increasing complexity. (See also [Reference Janson20, Chapter 11.3] and [Reference Kaur and Röllin24].) The terms in the expansion are indexed by the vertices and edges subgraphs of the complete graph of increasing sizes, and the asymptotic behaviour of $X_{n}(H,W)$ is determined by the non-zero terms indexed by the smallest size graphs. Details of the proof are given in Section 5. Various examples are discussed in Section 3.

The main emphasis of the present paper is Theorem 2.9(2), for $H$ -regular graphons, where the more interesting non-Gaussian fluctuation emerges. Moreover, it turns out that there are non-trivial cases where also the limit in Theorem 2.9(2) is degenerate. We discuss this further in Section 4, where we give both an example of such a higher order degeneracy, and examples of graphs $H$ for which this cannot happen for any $W$ . We will also study when one of the two components of the limit (the normal and the non-normal component) vanishes. In particular, in the classical Erdős–Rényi case $W\equiv p$ , Theorem 2.9(2) applies to every $H$ with the non-normal component vanishing, so the limit is normal, which is a classical result; see further Example 3.3.

Finally, it is worth mentioning that limiting distributions very similar to that in Theorem 2.9(2) also appears in the context of counting monochromatic subgraphs in uniform random colourings of sequences of dense graphs [Reference Bhattacharya and Mukherjee4, Reference Bhattacharya, Diaconis and Mukherjee5]. Although this is a fundamentally different problem, the appearance of similar limiting objects in both situations is interesting.

4.1. Degeneracy of the Non-Gaussian Component

The following proposition characterises when the limit in (4.2) is Gaussian. It extends the special case $H=K_r$ which was shown in [Reference Hladký, Pelekis and Šileikis17, Theorem 1.3].

Proof. From (4.2) it is clear that (1), (2) and (3) are equivalent. Next, recalling the discussion following (2.21), ${\textrm{Spec}}^-(W_H)=\emptyset$ if and only if ${\textrm{Spec}}(W_H)=\{d_{W_H}\}$ ; furthermore, since $W$ is $H$ -regular, $W_H$ is degree regular and, hence, $\phi \equiv 1$ is an eigenfunction corresponding to $d_{W_H}$ . Therefore, by (2.18), if ${\textrm{Spec}}(W_H)=\{d_{W_H}\}$ , then

(4.3) \begin{align} W_H(x,y)= d_{W_H}\phi (x)\phi (y) = d_{W_H} \qquad \text{a.e.} \end{align}

Conversely, $W_H(x,y)=d_{W_H}$ a.e. implies that $d_{W_H}$ is the only non-zero eigenvalue of $T_{W_H}$ , and thus ${\textrm{Spec}}^-(W_H)=\emptyset$ . This establishes that (3) and (4) are equivalent.

4.2. Degeneracy of the Gaussian Component

The Gaussian component in the limit (4.2) is degenerate when $\sigma _{H,W}^2 = 0$ . To study the structure of such graphons, we need a few definitions. For a graph $F=(V(F), E(F))$ and $S\subseteq V(F)$ , the neighbourhood of $S$ in $F$ is $N_F(S)=\{v \in V(F) \;:\; \exists u \in S \text{ such that } (u, v) \in E(F)\}$ . Moreover, for $u, v \in V(F)$ , $F\backslash \{u, v\}$ is the graph obtained by removing the vertices $u, v$ and all the edges incident to them. For notational convenience, we introduce the following definition:

Definition 4.2. Let $H$ be a labelled finite simple graph and $W$ a graphon. Then, for $1 \leq u \ne v \leq |V(H)|$ , the function $t_{u, v}^{-}(\cdot, \cdot, H, W) \;:\; [0, 1]^2 \rightarrow [0, 1]$ is defined as

(4.4) \begin{align} & t_{u, v}^{-}(x, y, H, W) \notag \\[5pt] &= \int _{[0,1]^{|V(H)|-2}} \prod _{r \in N_H(u)\backslash \{v\}}W(x, z_r) \prod _{s \in N_H(v) \backslash \{u\}} W(y, z_s) \prod _{(r, s) \in E(H\backslash \{u, v\}) } W(z_r, z_s) \prod _{r \notin \{u, v\}} \,\textrm{d} z_r . \end{align}

Thus, if $(u,v)\in E(H)$ , then

(4.5) \begin{align} t_{u, v}(x, y, H, W) = W(x,y) t_{u, v}^{-}(x, y, H, W) . \end{align}

Note that

(4.6) \begin{align} \sigma _{H,W}^2 & = c_H\sum _{(a,b),(c,d)\in E^{+}(H)} \int t_{a, b}^{-}(x, y, H, W) t_{c, d}^{-}(x, y, H, W) W(x,y)(1-W(x,y)) \,\textrm{d} x \,\textrm{d} y, \end{align}

where $c_H\;:\!=\; \frac{1}{2 |\textrm{Aut} (H)|^2}$ . It is clear from (4.6) that if $W$ is random-free, then $\sigma _{H,W}^2=0$ and hence, if $W$ is $H$ -regular, the asymptotic distribution does not have a normal component. Interestingly, the converse is also true whenever $H$ is bipartite. This is formulated in the following theorem:

The proof of Theorem 4.3 is given in Section 6. It entails showing, using the bipartite structure of $H$ , that for almost every $(x, y)$ such that $W(x, y) \in (0, 1)$ , we have $t_{a, b}^{-}(x, y, H, W) \gt 0$ , for $a\neq b\in V(H)$ such that $(a,b)\in E(H)$ . Consequently, from (4.6), $\sigma _{H,W}^2 \gt 0$ whenever the set $\{(x, y) \in [0, 1]^2 \;:\; W(x, y) \in (0, 1)\}$ has positive Lebesgue measure. An immediate consequence of Theorem 4.3 is that for a bipartite graph $H$ and an $H$ -regular $W$ , the asymptotic distribution of $Z_n(H, W)$ is non-degenerate whenever $W$ is not random-free.

For non-bipartite $H$ , we note only the following, which extends [Reference Hladký, Pelekis and Šileikis17, Proposition 1.5].

4.3. Degeneracy of the Limit in (4.2)

We begin with an example where the limit in (4.2) is degenerate.

Example 4.6. Let $H=K_{1,3}$ be the 3-star on vertex set $\{1,2,3,4\}$ , where the root (non-leaf) vertex is labelled $1$ . Further, suppose that $W$ is the complete balanced bipartite graphon:

(4.7) \begin{align} W(x,y)\;:\!=\; \begin{cases} 0 & \text{ if }(x,y)\in \left [0, \frac{1}{2}\right ]^2 \bigcup \left (\frac{1}{2}, 1\right ]^2, \\[5pt] 1 & \text{ otherwise} . \end{cases} \end{align}

To begin with note that $d_{W}(x)=\int _{0}^{1}W(x,y) \,\textrm{d} y=\frac{1}{2}$ , for all $x\in [0,1]$ . Therefore,

(4.8) \begin{align} \frac{1}{4}\sum _{i=1}^{4}t_{i}\left (x,K_{1,3},W\right ) &=\frac{1}{4}\left [d_W(x)^3+3\int W(x,t)d_W(t)^2 \,\textrm{d} t\right ]= \frac{1}{8} . \end{align}

This establishes that $W$ is $K_{1,3}$ -regular, and that $t(K_{1,3},W)=1/8$ . Next, since $W \in \{0,1\}$ , by Theorem 4.3, $\sigma _{K_{1,3},W_{2}}^{2}=0$ . Hence, to show that the limit distribution of $Z_n(K_{1, 3}, W)$ is degenerate it suffices to check that $\sum _{\lambda \in \text{Spec}^{-}(W_{K_{1,3}})}\lambda ^{2} = 0 .$ By Proposition 4.1, this is equivalent to showing

(4.9) \begin{align} W_{K_{1,3}}(x,y) = \frac{12}{ 2\left |{\textrm{Aut}}(K_{1,3})\right |}t\left (K_{1,3},W\right ) = \frac{1}{8}, \end{align}

for a.e. $(x,y)\in [0,1]^2$ (since $ |{\textrm{Aut}}(K_{1,3}) | = 3! = 6$ ). Towards this recall (2.19), which yields

(4.10) \begin{align} W_{K_{1,3}}(x,y) & =\frac{1}{2|\textrm{Aut}(K_{1,3})|}\sum _{1 \leq a\neq b \leq 4}t_{a,b}\left (x,y,K_{1,3},W\right ) \nonumber \\[5pt] & =\frac{1}{12}\bigg [3W(x,y)\int W(x,z)W(x,t) \,\textrm{d} z \,\textrm{d} t + 3W(x,y)\int W(y,z)W(y,t)\,\textrm{d} z \,\textrm{d} t \nonumber \\[5pt] & \hskip 5em + 6\int W(x,t)W(y,t)W(z,t) \,\textrm{d} z \,\textrm{d} t\bigg ] \nonumber \\[5pt] &=\frac{1}{12}\left [3W(x,y)d_W(x)^2 + 3W(x, y)d_W(y)^2 + 6 \int d_W(t) W(x,t)W(y, t) \,\textrm{d} t\right ] \nonumber \\[5pt] &=\frac{1}{12}\left [\frac{3}{2}W(x,y) + 3\int W(x,t)W(y, t) \,\textrm{d} t\right ]. \end{align}

Now, observe that if $W(x,y) = 0$ then $\int W(x,t)W(y, t) \,\textrm{d} t = \frac{1}{2}$ , which implies, from (4.10), $W_{K_{1,3}}(x,y) = \frac{1}{8}$ . Further, when $W(x,y) = 1$ , then $\int W(x,t)W(y, t) \,\textrm{d} t = 0$ , which implies $W_{K_{1,3}}(x,y) = \frac{1}{8}$ . Thus for all $(x,y)\in [0,1]^2$ , $W_{K_{1,3}}=1/8$ , which establishes (4.9). This shows that limiting distribution of $Z_n(K_{1, 3}, W)$ is degenerate for $W$ as in (4.7).

In fact, in this example, we can easily find the asymptotic distribution of $X_{n}(K_{1,3}, W)$ directly. Let $M\;:\!=\;\bigl |{\{i:U_i\le \frac 12\}}\bigr |\sim \operatorname{Bin}\bigl (n,\frac 12\bigr )$ , and $\hat M\;:\!=\;M-n/2$ . Then

(4.11) \begin{align} X_n(K_{1,3},W)&=M\binom{n-M}3 + (n-M)\binom M3 \notag \\[5pt] & =\frac{1}{6}\Bigl (M(n-M)\bigl ((n-M)^2-3(n-M)+2\bigr )+(n-M)M\bigl (M^2-3M+2\bigr )\Bigr ) \notag \\[5pt] & =\frac{1}{6}M(n-M)\bigl ((n-M)^2+M^2-3n+4\bigr ) \notag \\[5pt] & =\frac{1}{6}\Bigl (\frac{n}2+\hat M\Bigr )\Bigl (\frac{n}2-\hat M\Bigr ) \Bigl (\Bigl (\frac{n}2-\hat M\Bigr )^2+\Bigl (\frac{n}2+\hat M\Bigr )^2-3n+4\Bigr ) \notag \\[5pt] & =\frac{1}{6}\Bigl (\Bigl (\frac{n}2\Bigr )^2-\hat M^2\Bigr ) \Bigl (2\Bigl (\frac{n}2\Bigr )^2+2\hat M^2 -3n+4\Bigr ) \notag \\[5pt] & =\frac{1}{3}\Bigl (\Bigl (\frac{n}2\Bigr )^4-\hat M^4\Bigr ) -\frac{3n-4}{6}\Bigl (\Bigl (\frac{n}2\Bigr )^2-\hat M^2\Bigr ). \end{align}

Hence, subtracting the mean and using (2.8),

(4.12) \begin{align} \frac{X_n(K_{1,3},W)-\frac{(n)_4}{48}}{n^2}& =-\frac{\hat M^4-\mathbb{E} \hat M^4}{3n^2} +\frac{3n-4}{6n}\cdot \frac{\hat M^2-\mathbb{E}\hat M^2}{n}. \end{align}

Since the central limit theorem yields $\hat M/n^{1/2}\overset{D}{\rightarrow } Z/2$ , with all moments, where $Z\sim N(0,1)$ , (4.12) yields

(4.13) \begin{align} \frac{X_n(K_{1,3},W)-\frac{(n)_4}{48}}{n^2}& \overset{D}{\longrightarrow } -\frac{Z^4-3}{48} +\frac{Z^2-1}8 =-\frac{1}{48}\bigl (Z^4-6 Z^2+3\bigr ) =-\frac{1}{48}h_4(Z), \end{align}

where $h_4$ is the 4th Hermite polynomial (using the normalisation in, e.g. [Reference Janson20, Example 3.18]). Consequently, in this example, the correct normalisation is by $n^2=n^{|V(H)|-2}$ , and the limit distribution is given by a fourth-degree polynomial of a Gaussian variable.

The example above raises the question for which graphs $H$ is the limiting distribution of $Z_n(H, W)$ in Theorem 2.9(2) non-degenerate for all graphons $W$ . In the following we will show that the limit is always non-degenerate when $H=C_{4}$ or $H=K_{1, 2}$ (the 4-cycle and the 2-star). Our proofs use the specific structure of the 4-cycle and 2-star, and it remains unclear for what other graphs can one expect the non-degeneracy result to hold.

Non-Degeneracy of the Limit for the 4-Cycle: We begin by deriving explicit conditions for degeneracy of the two components of the limiting distribution of $Z(C_4, W)$ . (For the normal part, we can also use Theorem 4.3, but we find it interesting to first make a direct evaluation of the condition $\sigma ^2_{H,W}=0$ .) Towards this define:

(4.14) \begin{align} U_1(x,y)\;:\!=\;\int _{[0, 1]} W(x,s)W(y,s) \,\textrm{d} s \quad \text{and}\quad U_{2}(x,y)\;:\!=\;\int _{[0, 1]^2} W(x,s)W(s,t)W(y,t) \,\textrm{d} s \,\textrm{d} t. \end{align}

Proof. Since all the vertices of the 4-cycle are symmetric, from Definition 2.2 we have the following: The graphon $W$ is $C_4$ -regular if

(4.17) \begin{align} \int _{[0, 1]^3} W(x,y)W(y,z)W(z,t)W(t,x) \,\textrm{d} y \,\textrm{d} z \,\textrm{d} t=t(C_4, W) \text{ a.e. } x \in [0, 1] . \end{align}

Moreover, since $|\textrm{Aut}(C_4)|=8$ , by Definition 2.5, the 2-point conditional graphon induced by $C_4$ is given by

(4.18) \begin{align} W_{C_4}(x, y)=\frac{ 4 U_1(x, y)^2 + 8 W(x, y) U_2(x, y) }{2 |\textrm{Aut}(C_4)|} = \frac{ U_1(x, y)^2 + 2 W(x, y) U_2(x, y) }{4}, \end{align}

where $U_1, U_2$ are as defined in (4.14). Hence, Proposition 4.1 shows that ${\textrm{Spec}}^-(W_{C_4})=\emptyset$ if and only if (4.15) holds.

Next, since all the edges of $C_4$ are symmetric, the weak edge join of 2 copies of $C_4$ is always isomorphic to graph $F_1$ in Figure 5(a). Similarly, the strong edge join of 2 copies of $C_4$ is always isomorphic to graph $F_2$ in Figure 5(b).

Figure 5.

(a) The weak and (b) the strong edge join of two copies of $C_4$ .

Therefore, using $|E^+(C_4)|=8$ and $|\textrm{Aut}(C_4)|=8$ in (2.26), we find that $ \sigma ^2_{C_4, W}$ simplifies to

(4.19) \begin{align} \sigma ^2_{C_4, W} & = \frac{1}{2} \left ( t(F_1, W) - t(F_2, W) \right ) \nonumber \\[5pt] & = \frac{1}{2} \left (\int _{[0, 1]^2} W(x,y)U_2^{2}(x,y) \,\textrm{d} x \,\textrm{d} y -\int _{[0, 1]^2} W^{2}(x,y)U_2^{2}(x,y) \,\textrm{d} x \,\textrm{d} y \right ). \end{align}

Hence,

(4.20) \begin{align} \sigma ^2_{C_4, W} = 0 \iff \int _{[0,1]^2} U_2^{2}(x,y) \left ( W(x, y) - W^{2}(x,y) \right ) \,\textrm{d} x \,\textrm{d} y, \end{align}

which completes the proof.

The following theorem shows that (if we ignore the trivial cases in Remark 2.10), whenever $W$ is $C_{4}$ -regular, the limiting distribution of $Z_n(C_4, W)$ is always non-degenerate. Hence, for $H=C_4$ , Theorem 2.9(1) or (2) will give a non-degenerate limit. By Lemma 4.7, Theorem 4.8 is equivalent to the claim that whenever $W$ is $C_{4}$ -regular, (4.15) and (4.16) cannot occur simultaneously. The proof of Theorem 4.8 is given in Section 7.

Non-Degeneracy of the Limit for the 2-Star: As in Lemma 4.7, we first derive conditions which are equivalent to degeneracy of the two components of the limiting distribution of $Z_n(K_{1, 2}, W)$ .

Proof. From (3.14) the 2-point conditional graphon induced by $K_{1, 2}$ is given by

(4.23) \begin{align} W_{K_{1, 2}}(x,y) = \frac{1}{2}\left \{W(x,y)\left (d_{W}(x)+d_{W}(y)\right ) + U_1(x, y) \right \} . \end{align}

Furthermore, (2.21) yields $d_{W_{K_{1, 2}}}=\frac{6}{4}t(K_{1,2},W)=\frac{3}{2}\int _0^1 d_W(x)^2\,\,\textrm{d} x.$ Hence, Proposition 4.1 shows that ${\textrm{Spec}}^-(W_{K_{1, 2}})=\emptyset$ if and only if (4.21) holds.

Furthermore, recalling (3.13) we have,

(4.24) \begin{align} \sigma _{K_{1, 2},W}^{2} =2\left [ t\left (K_{1,3},W\right ) + t(P_3,W)-t\bigl (K_{1, 3}^{+},W\bigr )-t\left (P_3^{+},W\right )\right ] \end{align}

where the graphs $K_{1,3},K_{1,3}^{+},P_3$ and $P_3^{+}$ are as shown in Figure 4. By evaluating the densities in (4.24), we obtain

(4.25) \begin{align} \sigma _{K_{1, 2},W}^{2} = 2\int \left \{ d_W(x) d_W(y) + d_W(x)^2 \right \} W(x,y)(1-W(x,y))\,\textrm{d} x \,\textrm{d} y . \end{align}

This shows that $\sigma _{K_{1, 2},W}^{2} =0$ equivalent to (4.22).

The following theorem is the counterpart of Theorem 4.8 for $K_{1,2}$ and shows that for $H=K_{1,2}$ , and Theorem 2.9(1) or (2) will give a non-degenerate limit. By Lemma 4.7, Theorem 4.10 is equivalent to the claim that whenever $W$ is $K_{1,2}$ -regular, (4.21) and (4.22) cannot occur simultaneously. The proof of Theorem 4.10 is given in Section 8.

5.1. Orthogonal Decomposition of Generalized $U$ -Statistics

We recall some notations and definitions from [Reference Janson and Nowicki22]. Suppose $\{U_{i} \;:\; 1 \leq i \leq n\}$ and $\{Y_{ij} \;:\; 1\leq i\lt j \leq n\}$ are i.i.d. sequences of $U[0,1]$ random variables. Denote by $K_n$ the complete graph on the set of vertices $\{1, 2, \ldots, n\}$ and let $G= (V(G), E(G))$ be a subgraph of $K_{n}$ . Let $\mathcal{F}_{G}$ be the $\sigma$ -algebra generated by the collections $\{U_{i}\}_{i\in V(G)}$ and $\{Y_{ij}\}_{ij\in E(G)}$ and let $L^{2}(G)=L^2(\mathcal{F}_G)$ be the space of all square integrable random variables that are functions of $\{U_{i} \;:\; i\in V(G)\}$ and $\{Y_{ij} \;:\; ij\in E(G)\}$ . Now, consider the following subspace of $L^{2}(G)$ :

(5.3) \begin{align} M_{G}\;:\!=\;\{Z\in L^{2}(G) \;:\; \mathbb{E}[ZV]=0\text{ for every }V\in L^{2}(H)\text{ such that }H\subset G\}. \end{align}

(For the empty graph, $M_{\emptyset }$ is the space of all constants.) Equivalently, $Z\in M_{G}$ if and only if $Z\in L^{2}(G)$ and

(5.4) \begin{align} \mathbb{E}\left [Z\mid X_{i},Y_{ij} \;:\; i \in V(H), (i, j) \in E(H)\right ] = 0, \quad \text{for all } H\subset G. \end{align}

Then, we have the orthogonal decomposition [Reference Janson and Nowicki22, Lemma 1]

(5.5) \begin{align} L^{2}(G)=\bigoplus _{H\subseteq G} M_H, \end{align}

that is, $L^{2}(G)$ is the orthogonal direct sum of $M_{H}$ for all subgraphs $H\subseteq G$ . This allows us to decompose any function in $L^{2}(G)$ as the sum of its projections onto $M_{H}$ for $H\subseteq G$ . For any closed subspace $M$ of $L^2(K_n)$ , denote the orthogonal projection onto $M$ by $P_M$ . Then, in particular, for $f$ as in (5.2), we have the decomposition

(5.6) \begin{align} f=\sum _{H\subseteq G} f_{H}, \end{align}

where $f_{H}=P_{M_H}f$ is the orthogonal projection of $f$ onto $M_{H}$ . Further, for $1 \leq s \leq |V(H)|$ , define

(5.7) \begin{align} f_{(s)}\;:\!=\;\sum _{H\subseteq G \;:\; |V(H)|=s} f_{H} . \end{align}

The smallest positive $d$ such that $f_{(d)}\neq 0$ is called the principal degree of $f$ . The asymptotic distribution of $X_n(H, W)$ depends on the principal degree of $f$ and the geometry of the subgraphs which appear in its decomposition.

For any graph $G\subseteq K_n$ , the orthogonal projection onto $L^2(G)=L^2(\mathcal{F}_G)$ equals the conditional expectation $\mathbb{E}(\cdot \mid \mathcal{F}_G)$ , i.e.,

(5.8) \begin{align} P_{L^2(G)}=\mathbb{E}[\cdot \mid \mathcal{F}_G]. \end{align}

Moreover, by (5.5), we have

(5.9) \begin{align} P_{L^{2}(G)}=\sum _{H\subseteq G} P_{M_H}. \end{align}

The equations (5.8)–(5.9) enable us to express any $P_{M_H}$ as a linear combination of conditional expectations. We will do this explicitly for the simplest cases in lemmas below.

5.2. Proof of Theorem 2.9(1)

Recall the definition of the function $f$ from (5.2) and consider its decomposition as in (5.6). Then (5.7) for $s=1$ gives,

(5.10) \begin{align} f_{(1)}=\sum _{a=1}^{|V(H)|}f_{K_{\{a\}}}, \end{align}

where $K_{\{a\}}$ is the graph with the single vertex $a$ and $f_{K_{\{a\}}}$ is the projection of $f$ onto the space $M_{K_{\{a\}}}$ , for $1 \leq a \leq |V(H)|$ . We will calculate $f_{{K_{{\{a\}}}}}$ using the following lemma, which we state for general functions $F$ .

Lemma 5.1. For $1 \leq a \leq |V(H)|$ , and any $F\in L^2$ , the projection of $F$ onto the space $M_{K_{\{a\}}}$ is given by

(5.11) \begin{align} F_{K_{\{a\}}}=\mathbb{E}\left [F\mid U_{a}\right ]-\mathbb{E}[F]. \end{align}

Proof. By (5.9) and (5.8),

(5.12) \begin{align} F_{{K_{{\{a\}}}}}\;:\!=\; P_{ M_{{K_{{\{a\}}}}}} F = P_{L^2({K_{{\{a\}}}})}F-P_{M_\emptyset }F = \mathbb{E}[F\mid U_a]-\mathbb{E}[F]. \end{align}

Applying Lemma 5.1 to $f$ defined in (5.2), we obtain

(5.13) \begin{align} f_{K_{\{a\}}} &=\sum _{H'\in \mathscr{G}_H}\mathbb{E}\left [\prod _{(b, c) \in E(H')} \textbf{1}\left \{Y_{bc}\leq W(U_{b},U_{c})\right \}\,\middle |\, U_{a}\right ]-\mathbb{E}[f] \notag \\[5pt] &=\sum _{H'\in \mathscr{G}_H}\mathbb{E}\left [\prod _{(b, c)\in E(H')}W(U_{b},U_{c})\, \middle |\, U_{a}\right ]-\mathbb{E}[f]\notag \\[5pt] &=\sum _{H'\in \mathscr{G}_H}t_{a}(U_{a},H',W)-\mathbb{E}[f], \end{align}

where the last step follows from the definition of the 1-point conditional homomorphism density function (recall Definition 2.1). Then from (5.10),

(5.14) \begin{align} f_{(1)}=\sum _{a=1}^{|V(H)|}\left (\sum _{H'\in \mathscr{G}_H}t_{a}(U_{a},H',W)-\mathbb{E}[f]\right ). \end{align}

We now proceed to compute $\operatorname{Var} f_{(1)}$ .

For this, we need the following combinatorial identity.

Lemma 5.2. For the vertex join operation $\bigoplus _{a,b}$ as in Definition 2.7 the following holds:

(5.15) \begin{align} |\mathscr{G}_H|^{2}\sum _{1\leq a,b\leq |V(H)|}t\left (H\bigoplus _{a,b} H, W\right ) &=|V(H)|^{2}\sum _{H_{1},H_{2}\in \mathscr{G}_H}t\left (H_{1}\bigoplus _{1,1}H_{2},W\right ). \end{align}

Proof. For any permutation $\phi \;:\; V(H)\rightarrow V(H)$ , we define the permuted graph $\phi (H)\;:\!=\;(\phi (V(H)), \phi (E(H)))$ , where $\phi (V(H))=\{\phi (a) \;:\; 1\leq a \leq |V(H)|\}$ and $\phi (E(H))=\{(\phi (a), \phi (b)) \;:\; (a, b) \in E(H)\}$ .

First, fix $(a,b)\in V(H)^{2}$ and consider two permutations, $\phi _{a} \;:\; V(H)\rightarrow V(H)$ and $\phi _{b} \;:\; V(H)\rightarrow V(H)$ such that $\phi _{a}(a)=\phi _{b}(b)=1$ . Then

(5.16) \begin{align} \sum _{1\leq a,b\leq |V(H)|}\sum _{H_{1},H_{2}\in \mathscr{G}_H}t\left (H_{1}\bigoplus _{a,b}H_{2},W\right ) &=\sum _{1\leq a,b\leq |V(H)|}\sum _{H_{1},H_{2}\in \mathscr{G}_H}t\left (\phi _{a}(H_{1})\bigoplus _{1,1}\phi _{b}(H_{2}),W\right ) \nonumber \\[5pt] &=\sum _{1\leq a,b\leq |V(H)|}\sum _{H_{1},H_{2}\in \mathscr{G}_H}t\left (H_{1}\bigoplus _{1,1}H_{2},W\right ) \nonumber \\[5pt] &=|V(H)|^{2}\sum _{H_{1},H_{2}\in \mathscr{G}_H}t\left (H_{1}\bigoplus _{1,1}H_{2},W\right ), \end{align}

where the second equality follows, since the map $(H_1, H_2) \rightarrow (\phi _{a}(H_{1}),\phi _{b}(H_{2}))$ is a bijection from $\mathscr{G}_H^{2}$ to $\mathscr{G}_H^{2}$ , for all $1 \leq a, b \leq |V(H)|$ .

Next, fix $H_{1},H_{2}\in \mathscr{G}_H$ . Then consider isomorphisms $\phi _{1}, \phi _{2} \;:\; V(H)\rightarrow V(H)$ such that $\phi _{1}(H_{1})=H$ and $\phi _{2}(H_{2})=H$ . Thus,

(5.17) \begin{align} \sum _{H_{1},H_{2}\in \mathscr{G}_H}\sum _{1\leq a, b\leq |V(H)|}t\left (H_{1}\bigoplus _{a,b}H_{2},W\right ) &=\sum _{H_{1},H_{2}\in \mathscr{G}_H}\sum _{1\leq a, b\leq |V(H)|}t\left (H\bigoplus _{\phi _{1}(a),\phi _{2}(b)}H,W\right ) \nonumber \\[5pt] &=\sum _{H_{1},H_{2}\in \mathscr{G}_H}\sum _{1\leq a, b\leq |V(H)|}t\left (H\bigoplus _{a,b}H, W \right ) \nonumber \\[5pt] &=|\mathscr{G}_H|^{2}\sum _{1\leq a, b\leq |V(H)|}t\left (H\bigoplus _{a,b}H, W\right ). \end{align}

Here, the second equality follows since $(a, b) \rightarrow (\phi _{1}(a),\phi _{2}(b))$ is a bijection from $V(H)^2$ to $V(H)^2$ .

Combining (5.16) and (5.17) the identity in (5.15) follows.

Lemma 5.3.

(5.18) \begin{align} \operatorname{Var}[f_{(1)}]& =|V(H)| |\mathscr{G}_H|^{2} \left \{ \frac{1}{|V(H)|^2} \sum _{1\leq a,b\leq |V(H)|}t\left (H\bigoplus _{a,b}H,W\right ) - t(H,W)^{2} \right \} \notag \\[5pt] &= \frac{|V(H)|!\,(|V(H)|-1)!}{|\textrm{Aut}(H)|^2} \left \{ \sum _{1\leq a,b\leq |V(H)|}t\left (H\bigoplus _{a,b}H,W\right ) -{|V(H)|^2} t(H,W)^{2} \right \} . \end{align}

Proof. Recalling (5.14) gives, since the terms in the outer sum there are independent,

(5.19) \begin{align} \text{Var}[f_{(1)}]=\sum _{a=1}^{|V(H)|}\text{Var}\left [\sum _{H'\in \mathscr{G}_H}t_{a}(U_{a},H',W)\right ]. \end{align}

Consider the term corresponding to $a=1$ in the sum above. For any $H_{1},H_{2}\in \mathscr{G}_H$ ,

(5.20) \begin{align} \mathbb{E}\left [t_{1}(U_{1},H_{1},W)t_{1}(U_{1},H_{2},W)\right ] &=t\left (H_{1}\bigoplus _{1,1}H_{2},W\right ) . \end{align}

Hence,

(5.21) \begin{align} \text{Var}\left [\sum _{H'\in \mathscr{G}_H}t_{1}(U_{1},H',W)\right ] &=\sum _{H_{1},H_{2}\in \mathscr{G}_H}\text{Cov}\left [t_{1}(U_{1},H_{1},W),t_{1}(U_{1},H_{2},W)\right ] \nonumber \\[5pt] &=\sum _{H_{1},H_{2}\in \mathscr{G}_H}\left (t\left (H_{1}\bigoplus _{1,1}H_{2},W\right )-t(H,W)^{2}\right ) . \end{align}

Now, an argument similar to Lemma 5.2 shows that

(5.22) \begin{align} \sum _{H'\in \mathscr{G}_H}t_{a}(x,H',W)=\sum _{H'\in \mathscr{G}_H}t_{b}(x,H',W), \end{align}

for all $x\in [0,1]$ and $1\leq a, b\leq |V(H)|$ . Hence, (5.19) and (5.21) imply

(5.23) \begin{align} \text{Var}[f_{(1)}]&= |V(H)| \sum _{H_{1},H_{2}\in \mathscr{G}_H}\left (t\left (H_{1}\bigoplus _{1,1}H_{2},W\right )-t(H,W)^{2}\right ), \end{align}

and the result follows by Lemma 5.2, using (2.7) for the second equality.

Note that $\mathbb{E} f_{(1)}= 0$ by (5.7). Hence, $\operatorname{Var} f_{(1)}=0$ if and only if $f_{(1)}=0$ a.s.

Proof. Lemma 5.3 shows that $\text{Var}[f_{(1)}]$ is zero if and only if

(5.24) \begin{align} \frac{1}{|V(H)|^{2}}\sum _{1\leq a,b\leq |V(H)|}t\left (H\bigoplus _{a,b},W\right )=t(H,W)^{2} . \end{align}

Now observe,

(5.25) \begin{align} \sum _{1\leq a,b\leq |V(H)|}t\left (H\bigoplus _{a,b}H,W\right ) &=\sum _{1\leq a,b\leq |V(H)|}\int t_{a}(x,H,W)t_{b}(x,H,W)\,\textrm{d} x \notag \\[5pt] &=\int \left (\sum _{1\leq a\leq |V(H)|}t_{a}(x,H,W)\right )^{2}\,\textrm{d} x . \end{align}

Thus (5.24) becomes, using also (2.11),

(5.26) \begin{align} \int \left (\sum _{1\leq a\leq |V(H)|}t_{a}(x,H,W)\right )^{2}\,\textrm{d} x-\left ( \int \sum _{1\leq a\leq |V(H)|}t_{a}(x,H,W)\right )^{2} \,\textrm{d} x = 0, \end{align}

which is equivalent to $\text{Var} [\Delta (U) ]=0$ , where we define

(5.27) \begin{align} \Delta (x)\;:\!=\;\sum _{1\leq a\leq |V(H)|}t_{a}(x,H,W) \end{align}

and let $U\sim \operatorname{Uniform}[0,1]$ . Hence, $\text{Var}[f_{(1)}]=0$ if and only if $\Delta (U)$ is constant a.s. Therefore, since $\mathbb{E}\Delta (U)= |V(H)| t(H,W)$ , we see that $\text{Var}[f_{(1)}]=0$ if and only if

(5.28) \begin{align} \frac{1}{|V(H)|}\sum _{1\leq a\leq |V(H)|}t_{a}(x,H,W)=t(H,W) \text{ for almost every } x \in [0, 1]. \end{align}

By Definition 2.2, (5.28) says that $W$ is $H$ -regular.

Proof of Theorem 2.9(1). Lemma 5.4 shows that if $W$ is not $H$ -regular, then the principal degree of $f$ is 1. Thus, [Reference Janson and Nowicki22, Theorem 1] yields

(5.29) \begin{align} \frac{X_{n}(H,W)-\frac{(n)_{|V(H)|}}{|\textrm{Aut}(H)|}t(H,W)}{n^{|V(H)|-\frac{1}{2}}} \overset{D}{\rightarrow }\textsf{N}(0, \tau ^{2}), \end{align}

where using also (5.18) and (2.24),

(5.30) \begin{align} \tau ^{2} & = \frac{1}{|V(H)|!\,(|V(H)|-1)!}\text{Var}[f_{(1)}] = \tau ^2_{H, W}. \end{align}

This completes the proof of Theorem 2.9(1) when $W$ is not $H$ -regular.

In fact, (5.29)–(5.30) hold also when $W$ is $H$ -regular, with $f_{(1)}=0$ and $\tau ^2=0$ . Although this case is not included in the statement of [Reference Janson and Nowicki22, Theorem 1], it follows by its proof, as a consequence of [Reference Janson and Nowicki22, Lemma 2]; see also [Reference Janson20, Corollary 11.36]. Consequently, Theorem 2.9(1) holds for any $W \in \mathcal{W}_0$ .

5.3. Proof of Theorem 2.9(2)

In this case, $W$ is $H$ -regular, hence $f_{(1)}\equiv 0$ by Lemma 5.4. Therefore, we consider $f_{(2)}$ (recall (5.7)), which can be written as

(5.31) \begin{align} f_{(2)}=\sum _{1\leq a\lt b\leq |V(H)|} \left ( f_{{E_{{\{a,b\}}}}} +f_{{K_{\{a,b\}}}} \right ), \end{align}

where ${E_{{\{a,b\}}}} = (\{a, b\}, \emptyset )$ is the graph with two vertices $a$ and $b$ and no edges, and ${K_{\{a,b\}}} = (\{a, b\}, \{ (a, b) \} )$ is the complete graph with vertices $a$ and $b$ . As for $f_{(1)}$ , we have $\mathbb{E}f_{(2)}=0$ , and thus $\operatorname{Var} f_{(2)}=0\iff f_{(2)}=0$ a.s.

If $\operatorname{Var}f_{(2)}\neq 0$ , then $f$ has principal degree 2, and we can apply [Reference Janson and Nowicki22, Theorem 2], which shows that

(5.32) \begin{align} \frac{X_{n}(H,W)-\frac{(n)_{|V(H)|}}{|\textrm{Aut}(H)|}t(H,W)}{n^{|V(H)|-{1}}} \overset{D}{\rightarrow } \sigma Z+\sum _{\lambda \in \Lambda }\lambda (Z_\lambda ^2-1), \end{align}

where $Z$ and ${\{Z_\lambda \}}_{\lambda \in \Lambda }$ are independent standard Gaussians,

(5.33) \begin{align} \sigma ^2=\frac{1}{2(|V(H)-2)!^2}\mathbb{E} \bigl [f_{{K_{\{1,2\}}}}^2\bigr ] \end{align}

and $\Lambda$ is the multiset of (non-zero) eigenvalues of a certain integral operator $T$ .

Moreover, if $\operatorname{Var}f_{(2)}=0$ , so $f_{(2)}=0$ a.s., then the conclusion of [Reference Janson and Nowicki22, Theorem 2] still holds (with a trivial limit 0), again as a consequence of [Reference Janson and Nowicki22, Lemma 2]. (See also the more general [Reference Janson20, Theorem 11.35].) Hence, (5.32) holds in any case.

It remains to show that $\sigma ^2=\sigma ^2_{H,W}$ in (2.26), and that $\Lambda$ equals ${\textrm{Spec}}^-(W_H)$ ; then (5.32) yields (2.25). We begin by finding $f_{E_{{\{a,b\}}}}$ and $f_{K_{\{a,b\}}}$ .

Lemma 5.5. For $1\leq a\lt b\leq |V(H)|$ and any $F\in L^2$ , the projection of $f$ onto the space $M_{{E_{{\{a,b\}}}}}$ is given by

(5.34) \begin{align} F_{{E_{{\{a,b\}}}}}=\mathbb{E}\left [F\mid U_{a},U_{b}\right ]-\mathbb{E}[F\mid U_{a}]-\mathbb{E}[F\mid U_{b}]+\mathbb{E}[F] . \end{align}

Proof. By (5.9),

(5.35) \begin{align} F_{{E_{{\{a,b\}}}}} \;:\!=\; P_{ M_{{E_{{\{a,b\}}}}}} F &= P_{L^2({E_{{\{a,b\}}}})}F - P_{M_{K_{{\{a\}}}}}F - P_{M_{{K_{{\{b\}}}}}}F -P_{M_\emptyset }F \notag \\[5pt] & = P_{L^2({E_{{\{a,b\}}}})}F - P_{L^2({K_{{\{a\}}}})}F - P_{L^2({K_{{\{b\}}}})}F +P_{M_\emptyset }F \end{align}

and the result follows by (5.8).

Lemma 5.6. For $1\leq a\lt b\leq |V(H)|$ and any $F\in L^2$ , the projection of $f$ onto the space $M_{{K_{\{a,b\}}}}$ is given by

(5.36) \begin{align} F_{{K_{\{a,b\}}}}=\mathbb{E}\left [F\mid U_{a},U_{b},Y_{ab}\right ] - \mathbb{E}\left [F\mid U_{a},U_{b}\right ]. \end{align}

Proof. The subgraphs of $K_{\{a,b\}}$ are $E_{{\{a,b\}}}$ , $K_{{\{a\}}}$ , $K_{{\{b\}}}$ and $\emptyset$ , and thus (5.9) yields

(5.37) \begin{align} F_{{K_{\{a,b\}}}} \;:\!=\; P_{ M_{{K_{\{a,b\}}}}} F& = P_{L^2({K_{\{a,b\}}})}F -P_{M_{E_{{\{a,b\}}}}}F- P_{M_{K_{{\{a\}}}}}F - P_{M_{{K_{{\{b\}}}}}}F -P_{M_\emptyset }F \notag \\[5pt] & = P_{L^2({K_{\{a,b\}}})}F - P_{L^2({E_{{\{a,b\}}}})}F, \end{align}

and the result follows by (5.8).

Specialising to $f$ defined in (5.2), we found $f_{K_{{\{a\}}}}=\mathbb{E} [f\mid U_a]-\mathbb{E} f$ in (5.13). Furthermore, the same argument yields, recalling (2.9) and (4.4),

(5.38) \begin{align} \mathbb{E}[f\mid U_a,U_b]= \sum _{H'\in \mathscr{G}_H}t_{a,b}(U_{a},U_b,H',W) \end{align}

and

(5.39) \begin{align} \mathbb{E}[f\mid U_a,U_b,Y_{ab}] &= \sum _{H'\in \mathscr{G}_H}t^-_{a,b}(U_{a},U_b,H',W) Z_{H',{\{a,b\}}}(Y_{ab},U_{a},U_{b}), \end{align}

where

(5.40) \begin{align} Z_{H',{\{a,b\}}}(Y_{ab},U_{a},U_{b}) \;:\!=\; \begin{cases} \textbf{1}\{Y_{ab}\leq W(U_{a},U_{b})\} & \text{ if } (a, b) \in E(H'),\\[5pt] 1 & \text{ otherwise. } \end{cases} \end{align}

Let also

(5.41) \begin{align} \overline W_{H', \{a, b\}}(x, y) \;:\!=\; \begin{cases} W(x, y) & \text{ if } (a, b)\in E(H'),\\[5pt] 1 & \text{ otherwise}, \end{cases} \end{align}

and $\mathscr{G}_{H, \{a, b\}}\;:\!=\;\{H'\in \mathscr{G}_H \;:\; (a, b) \in E(H')\}$ . Then, (5.36), (5.38) and (5.39) yield, using also (4.5),

(5.42) \begin{align} f_{K_{\{a,b\}}} &= \sum _{H'\in \mathscr{G}_H}t^-_{a,b}(U_{a},U_b,H',W) \Bigl ( Z_{H',{\{a,b\}}}(Y_{ab},U_{a},U_{b}) - \overline W_{H', \{a, b\}}(U_a, U_b) \Bigr ) \notag \\[5pt] &= \sum _{H'\in \mathscr{G}_{H,{\{a,b\}}}} t^-_{a,b}(U_{a},U_b,H',W) \Bigl ( \textbf{1}\{Y_{ab}\leq W(U_{a},U_{b})\} -W(U_a,U_b)\Bigr ). \end{align}

To compute the variance of $f_{{K_{\{1,2\}}}}$ , we recall the notions of weak and strong edge joins from Definition 2.7 and introduce a few definitions. Let $(V_H)_2 \;:\!=\;\{(a,b)\in V(H)^{2} \;:\; a\neq b\}$ . For $(a,b),(c,d)\in (V_H)_2$ define

(5.43) \begin{align} \underline{t}\left (H_{1}\mathop{\ominus }\limits _{(a,b),(c,d)} H_{2},W\right ) = t\left (H_{1}\mathop{\ominus }\limits _{(a,b),(c,d)} H_{2},W\right ) \boldsymbol 1\{(a,b) \in E^{+}(H_{1}) \text{ and }(c,d) \in E^{+}(H_{2})\} \end{align}

and similarly,

(5.44) \begin{align} \underline{t}\left (H_{1}\bigoplus _{(a,b),(c,d)} H_{2},W\right ) = t\left (H_{1}\bigoplus _{(a,b),(c,d)} H_{2},W \right ) \boldsymbol 1\{(a,b) \in E^{+}(H_{1}) \text{ and }(c,d) \in E^{+}(H_{2})\} . \end{align}

Then we have the following identities, similar to Lemma 5.2:

Lemma 5.7. Let $(V_H)_2$ be as defined above, and let $K_H\;:\!=\;|(V_H)_2|^2=|V(H)|^{2}(|V(H)|-1)^{2}$ . Then

(5.45) \begin{align} K_H \sum _{H_{1},H_{2}\in \mathscr{G}_H} \underline{t} \left (H_{1}\mathop{\ominus }\limits _{(1,2),(1,2)} H_{2},W\right ) & = |\mathscr{G}_H|^{2}\sum _{(a,b),(c,d)\in (V_H)_2 } \underline{t} \left (H\mathop{\ominus }\limits _{(a,b),(c,d)} H,W\right ). \end{align}

and, similarly,

(5.46) \begin{align} K_H \sum _{H_{1},H_{2}\in \mathscr{G}_H} \underline{t} \left (H_{1}\bigoplus _{(1,2),(1,2)} H_{2},W\right ) & = |\mathscr{G}_H|^{2}\sum _{(a,b),(c,d)\in (V_H)_2 } \underline{t} \left (H\bigoplus _{(a,b),(c,d)} H,W\right ). \end{align}

Proof. We will first show that

(5.47) \begin{align} \sum _{(a,b),(c,d)\in (V_H)_2}\sum _{H_{1},H_{2}\in \mathscr{G}_H} \underline{t} \left (H_{1}\mathop{\ominus }\limits _{(a,b),(c,d)} H_{2},W\right ) &= K_H \sum _{H_{1},H_{2}\in \mathscr{G}_H} \underline{t} \left (H_{1}\mathop{\ominus }\limits _{(1,2),(1,2)} H_{2},W\right ) . \end{align}

For this consider permutations $\phi _{(a,b)}, \phi _{(c,d)} \;:\; V(H) \rightarrow V(H)$ such that $\phi _{(a,b)}(a)=1$ and $\phi _{(a,b)}(b)=2$ and $\phi _{(c,d)}(c)=1$ and $\phi _{(c, d)}(d)=2$ . Then

(5.48) \begin{align} \sum _{(a,b),(c,d)\in (V_H)_2}\sum _{H_{1},H_{2}\in \mathscr{G}_H} \underline{t} \left (H_{1}\mathop{\ominus }\limits _{(a,b),(c,d)} H_{2},W\right ) &=\sum _{(V_H)_2\times V_{H}^2}\sum _{\mathscr{G}_H^{2}} \underline{t} \left (\phi _{(a,b)}(H_{1})\mathop{\ominus }\limits _{(1,2),(1,2)} \phi _{(c,d)}(H_{2}),W\right ) \notag \\[5pt] &= K_H \sum _{\mathscr{G}_H^{2}} \underline{t} \left (H_{1}\mathop{\ominus }\limits _{(1,2),(1,2)} H_{2},W\right ), \end{align}

where the last equality follows from the observation that $(H_{1},H_{2}) \rightarrow (\phi _{(a,b)}(H_{1}),\phi _{(c,d)}(H_{2}))$ is an bijection from $\mathscr{G}_H^2$ to $\mathscr{G}_H^2$ , for all $(a,b),(c,d)\in (V_H)_2$ .

Now by considering isomorphisms $\phi _{1}$ and $\phi _{2}$ such that $\phi _{1}(H_{1})=H$ and $\phi _{2}(H_{2})=H$ , a similar argument as above shows that

(5.49) \begin{align} \sum _{(a,b),(c,d)\in (V_H)_2}\sum _{H_{1},H_{2}\in \mathscr{G}_H} \underline{t}\left (H_{1}\mathop{\ominus }\limits _{(a,b),(c,d)} H_{2},W\right ) &=|\mathscr{G}_H|^{2}\sum _{(a,b),(c,d)\in (V_H)_2 } \underline{t} \left (H\mathop{\ominus }\limits _{(a,b),(c,d)} H,W\right ). \end{align}

Combining (5.47) and (5.49) yields the identity (5.45). The identity (5.46) follows by the same proof with only notational differences.

With the above definitions and identities we now proceed to compute the variance of $f_{{K_{\{1,2\}}}}$ .

Lemma 5.8. We have

(5.50) \begin{align} \operatorname{Var}[f_{{K_{\{1,2\}}}}]=\frac{(|V(H)|-2)!^{2}}{|\textrm{Aut}(H)|^{2}}\sum _{(a,b),(c,d)\in E^{+}(H)}\left (t\left (H\mathop{\ominus }\limits _{(a,b),(c,d)} H,W\right )-t\left (H\bigoplus _{(a,b),(c,d)} H,W\right )\right ) . \end{align}

Proof. We specialise (5.42) to $(a,b)=(1,2)$ and write for convenience

(5.51) \begin{align} h(U_{1},U_{2}, H_{1}, H_{2},W) \;:\!=\;t_{1,2}^-(U_{1},U_{2},H_{1},W)\, t_{1,2}^-(U_{1},U_{2},H_{2},W). \end{align}

This yields,

(5.52) \begin{align} \mathbb{E}[f_{{K_{\{1,2\}}}}^2] & = \sum _{H_{1},H_{2}\in \mathscr{G}_{H, \{1, 2\}}}\mathbb{E} \left [ h(U_{1},U_{2}, H_{1}, H_{2},W) \bigl ( \textbf{1}\{Y_{12}\leq W(U_{1},U_{2})\} - W(U_1, U_2) \bigr )^2 \right ] \nonumber \\[5pt] & = \sum _{H_{1},H_{2}\in \mathscr{G}_{H, \{1, 2\}}}\mathbb{E}\bigl [ h(U_{1},U_{2},H_{1}, H_{2}, W) W(U_{1},U_{2}) (1-W(U_{1},U_{2}))\bigr ] \nonumber \\[5pt] & =\sum _{H_{1},H_{2}\in \mathscr{G}_{H, \{1, 2\}}} \left ( t\left (H_{1}\mathop{\ominus }\limits _{(1,2),(1,2)} H_{2},W\right ) -t\left (H_{1}\bigoplus _{(1,2),(1,2)} H_{2},W\right ) \right ). \end{align}

Now, using the notations introduced in (5.43) and (5.44), the identity (5.52) can be written as

(5.53) \begin{align} \mathbb{E}[f_{{K_{\{1,2\}}}}^2] & = \sum _{H_{1},H_{2} \in \mathscr{G}_H}\left (\underline{t}\left (H_{1}\mathop{\ominus }\limits _{(1,2),(1,2)} H_{2},W\right )-\underline{t}\left (H_{1}\bigoplus _{(1,2),(1,2)} H_{2},W\right )\right ) \notag \\[5pt] & = \frac{(|V(H)|-2)!^2}{|\textrm{Aut}(H)|^2}\sum _{ (a,b),(c,d)\in (V_H)_2 }\left ( \underline{t}\left (H\mathop{\ominus }\limits _{(a,b),(c,d)} H,W\right ) - \underline{t}\left (H\bigoplus _{(a,b),(c,d)} H,W\right ) \right ) \notag \\[5pt] & = \frac{(|V(H)|-2)!^2}{|\textrm{Aut}(H)|^2}\sum _{(a,b),(c,d)\in E^{+}(H)}\left (t\left (H\mathop{\ominus }\limits _{(a,b),(c,d)} H,W\right )-t\left (H\bigoplus _{(a,b),(c,d)} H,W\right )\right ), \end{align}

where the second equality uses the identities from Lemma 5.7 and (2.7), and the third equality follows from the definitions in (5.43) and (5.44). This yields the result (5.50), since $\mathbb{E} f_{K_{\{a,b\}}}=0$ .

Lemma 5.8 and (5.33) show that

(5.54) \begin{align} \sigma ^2=\sigma ^2_{H,W}, \end{align}

as defined in (2.26).

Next, we compute the Hilbert–Schmidt operator $T$ as defined in [Reference Janson and Nowicki22, Theorem 2]. Note first that in our case this operator is defined on the space $M_{K_{\{1\}}}$ . Recall that $M_{K_{{\{1\}}}}\subset L^2({K_{{\{1\}}}})$ , where $L^2({K_{{\{1\}}}})$ is the space of all square integrable random variables of the form $g(U_1)$ . We may identify $L^2({K_{{\{1\}}}})$ and $L^2[0,1]$ , and then (5.5) yields the orthogonal decomposition

(5.55) \begin{align} L^{2}[0,1]=M_{K_{{\{1\}}}} \bigoplus M_{\emptyset }, \end{align}

where $M_{\emptyset }$ is the one-dimensional space of all constants. Hence, $M_{K_{{\{1\}}}}$ is identified with the subspace of $L^2[0,1]$ orthogonal to constants, i.e., $M_{K_{{\{1\}}}}={ \{g\in L^2[0,1]\;:\;\int _0^1 g=0 \}}$ .

Then, taking $g,h\in M_{K_{\{1\}}}\subset L^2[0,1]$ , the definitions given in [Reference Janson and Nowicki22, Theorem 2] yield

(5.56) \begin{align} \langle Tg,h\rangle &= \frac{1}{2(|V(H)|-2)!}\mathbb{E}\left [fg(U_{1})h(U_{2})\right ] . \end{align}

Recall the operator $T_{W_H}$ defined on $L^2[0,1]$ by (2.15) and (2.19).

Proof. We may replace $f$ by $\mathbb{E}[f\mid U_1,U_2]$ in (5.56), which by (5.38) yields

(5.57) \begin{align} \langle Tg,h\rangle & = \frac{1}{2(|V(H)|-2)!}\mathbb{E}\bigl [\mathbb{E}[f\mid U_1,U_2]g(U_{1})h(U_{2})\bigr ] \notag \\[5pt] &=\frac{1}{2(|V(H)|-2)!}\mathbb{E}\left [\sum _{H'\in \mathscr{G}_H}t_{1,2}(U_{1},U_{2},H',W)g(U_{1})h(U_{2})\right ]\nonumber \\[5pt] &=\left \langle \frac{1}{2(|V(H)|-2)!}\int \sum _{H'\in \mathscr{G}_H}t_{1,2}(x,\cdot,H',W)g(x)\textrm{d}x,h(\cdot )\right \rangle . \end{align}

Denote by $S_{|V(H)|}$ the set of all $|V(H)|!$ permutations of $V(H)$ . Then it is easy to observe that

(5.58) \begin{align} \sum _{\phi \in S_{|V(H)|}}t_{1,2}(x,y,\phi (H),W)=|\textrm{Aut}(H)|\sum _{H'\in \mathscr{G}_H}t_{1,2}(x,y,H',W) . \end{align}

Also,

(5.59) \begin{align} \sum _{\phi \in S_{|V(H)|}}t_{1,2}(x,y,\phi (H),W) &=\sum _{1\leq a\neq b\leq |V(H)|}\sum _{\substack{\phi \in S_{|V(H)|}\\ \phi (a)=1,\phi (b)=2}}t_{1,2}(x,y,\phi (H),W)\nonumber \\[5pt] &=\sum _{1\leq a\neq b\leq |V(H)|}\sum _{\substack{\phi \in S_{|V(H)|}\\ \phi (a)=1,\phi (b)=2}}t_{\phi ^{-1}(1)\phi ^{-1}(2)}(x,y,H,W)\nonumber \\[5pt] &=\sum _{1\leq a\neq b\leq |V(H)|}\sum _{\substack{\phi \in S_{|V(H)|}\\ \phi (a)=1,\phi (b)=2}}t_{a, b}(x,y,H,W)\nonumber \\[5pt] &=(|V(H)|-2)!\sum _{1\leq a\neq b\leq |V(H)|}t_{a,b}(x,y,H,W) \end{align}

Combining (5.58) and (5.59), we have, recalling (2.19),

(5.60) \begin{align} \frac{1}{2(|V(H)|-2)!}\sum _{H'\in \mathscr{G}_H}t_{1,2}(x,y,H',W)=\frac{1}{2|\textrm{Aut}(H)|}\sum _{1\leq a\neq b\leq |V(H)|}t_{a, b}(x,y,H,W)=W_{H}(x,y). \end{align}

Consequently, combining (5.57), (5.60) and (2.15), we obtain

(5.61) \begin{align} \langle Tg,h\rangle =\langle T_{W_H} g,h\rangle, \qquad g,h\in M_{K_{{\{1\}}}}. \end{align}

Furthermore, since $W$ is $H$ -regular, $W_H$ is degree regular and (2.21) shows that

(5.62) \begin{align} T_{W_H}1=d_{W_H}=d_{W_H}\cdot 1. \end{align}

Hence, $T_{W_H}$ maps the space $M_\emptyset$ of constant functions into itself. By (5.55), $M_{K_{{\{1\}}}}$ is the orthogonal complement of $M_\emptyset$ , and thus, since $T_{W_H}$ is a symmetric operator, $T_{W_H}$ also maps $M_{K_{{\{1\}}}}$ into itself. Hence, both $T$ and $T_{W_H}$ map $M_{K_{{\{1\}}}}$ into itself, and thus (5.61) shows that $T=T_{W_H}$ on $M_{K_{{\{1\}}}}$ .

Finally, recall that $\Lambda$ in (5.32) is the multiset of non-zero eigenvalues of $T$ , which we just have shown equals the multiset of eigenvalues of $T_{W_H}$ on $M_{K_{{\{1\}}}}$ . Moreover, on $M_\emptyset$ , $T_{W_H}$ has the single eigenvalue $d_{W_H}$ by (5.62). Hence, ${\textrm{Spec}}(W_H)=\Lambda \cup{\{d_H\}}$ , and thus ${\textrm{Spec}}^-(W_H)=\Lambda$ by the definition after (2.21).

5.4. Higher Order Limits

In the case where the limit in Theorem 2.9(2) is degenerate (as in Example 4.6), the function $f$ in (5.2) has principal degree $d \gt 2$ . In this case, [Reference Janson and Nowicki22, Theorem 3] shows that $(X_n(H, W) - \mathbb{E} X_n(H, W))/n^{|V(H)| - d/2}$ has a (non-degenerate) limit distribution, which can be expressed as a polynomial of degree $d$ in (possibly infinitely many) independent standard Gaussian variables. The expression in [Reference Janson and Nowicki22, Theorem 3] uses Wick products of Gaussian variables; these can be expressed using Hermite polynomials, see [Reference Janson20, Theorems 3.19 and 3.21]. One simple illustration (with $d=4$ ) is given in Example 4.6. This leads to the following natural open questions: