2. A general invariance principle

For each $v \in [n]$ and $a\in [c]$ , let

(18) \begin{align} \tilde{X}_{v ,a} = \sqrt{c}\bigg( \textbf{1}\{X_v=a\}-\frac{1}{c}\bigg).\end{align}

Let $\{Z_{v, a}\}_{v\in [n],a\in [c]}$ be a collection of i.i.d. N(0,1) and define

(19) \begin{align} \tilde{Z}_{v,a}\;:\!=\; Z_{v,a} - \frac{1}{c}\sum_{a=1}^c Z_{v,a} .\end{align}

We collect some easy facts about the random variables $\{\tilde{X}_{v, a}\}_{v\in [n],a\in [c]}$ and $\{\tilde{Z}_{v, a}\}_{v\in [n],a\in [c]}$ in the following observation.

Hereafter, denote

\begin{align*} \mathbf{X}&=(X_{v,a})_{v\in [n],a\in [c]},\\[5pt] \tilde{\mathbf{X}}&=(\tilde{X}_{v,a})_{v\in [n],a\in [c]},\\[5pt] \mathbf{Z}&=(Z_{v,a})_{v\in [n],a\in [c]},\\[5pt] \tilde{\mathbf{Z}}&=(\tilde{Z}_{v,a})_{v\in [n],a\in [c]}.\end{align*}

Fix an integer $r\geq 0$ . Then for a function $f\;:\;[n]_r \rightarrow \mathbb{R}$ , define

(20) \begin{align} \mathcal{T}(f;\; \tilde{\mathbf{X}}) \;:\!=\; \frac{1}{n^{\frac{r}{2}}\sqrt{c}\,}\sum_{a=1}^{c}\sum_{\mathbf{s}\in [n]_{r}}f(\mathbf{s})\prod_{j=1}^{r} \tilde{X}_{s_j, a} .\end{align}

Define $\mathcal{T}(f;\; \mathbf{X})$ and $\mathcal{T}(f;\; \tilde{\mathbf{Z}})$ similarly. Let $\mathcal{S}_r$ denote the set of all permutations of the set [r]. Then define the symmetrization of f as follows:

\begin{align*} \tilde{f} (s_1,\ldots s_r)=\frac{1}{r!}\sum_{\sigma \in \mathcal{S}_r} f(s_{\sigma(1)},\ldots, s_{\sigma(r)}) .\end{align*}

For functions $f,f'\;:\;[n]_{r}\rightarrow \mathbb{R}$ , their inner product is defined as

\begin{align*} \langle f,f'\rangle \;:\!=\; \frac{1}{n^r}\sum_{\mathbf{s}\in [n]_{r}}f(\mathbf{s})f'(\mathbf{s}) .\end{align*}

and let $\|f\|\;:\!=\;\sqrt{\langle f,f\rangle}$ be the associated norm. For $\mathbf{s} \in [n]_{r}$ , let $\underline{\mathbf{s}}$ denote the (unordered) set formed by the entries of $\mathbf{s}$ . (For example, if $\mathbf{s} = (4, 2, 5)$ then $\underline{\mathbf{s}} = \{2, 4, 5\}$ .) Note that

(21) \begin{align} \langle\tilde{f},\tilde{f}'\rangle = & \langle\tilde{f},f'\rangle = \langle f,\tilde{f}'\rangle = \frac{1}{n^r}\frac{1}{r!}\sum_{\substack{\mathbf{s}, \mathbf{s}' \in [n]_{r} \\ \underline{\mathbf{s}}=\underline{\mathbf{s}}'}} f(\mathbf{s})f'(\mathbf{s}') .\end{align}

We can then define the following bilinear operation:

\begin{align*} \langle f,f'\rangle_{\bullet} \;:\!=\; \langle f,\tilde{f}'\rangle .\end{align*}

Proof. Note that for any $\mathbf{s} \in [n]_{r}$ and $a \in [c]$ , $\mathrm{E}(\prod_{j = 1}^r \tilde{X}_{s_j, a}) = 0$ . This implies $\mathrm{E}(\mathcal{T}(f,\tilde{\mathbf{X}})) = 0$ (recall (20)). Hence,

(23) \begin{align} \mathrm{Cov}( \mathcal{T}(f,\tilde{\mathbf{X}}),\mathcal{T}(f',\tilde{\mathbf{X}}) ) & = \mathrm{E} ( \mathcal{T}(f,\tilde{\mathbf{X}}) \mathcal{T}(f',\tilde{\mathbf{X}}) ) \nonumber \\[5pt] & =\frac{1}{n^{\frac{r+r'}{2}}c}\sum_{a,a'\in [c]} \sum_{\substack{\mathbf{s} \in [n]_{r} \mathbf{s}'\in [n]_{r'}}}f(\mathbf{s})f'(\mathbf{s}')\mathrm{E}\left(\prod_{j\in \underline{\mathbf{s}}}\tilde{X}_{s_j,a}\prod_{j\in \underline{\mathbf{s}}'}\tilde{X}_{s_j' ,a'} \right)\!, \end{align}

where $\mathbf{s} = (s_1, s_2, \ldots, s_r)$ and $\mathbf{s}' = (s_1', s_2', \ldots, s_{r'}')$ , for $\mathbf{s} \in [n]_{r}$ and $\mathbf{s}'\in [n]_{r'}$ . Observe that if $\mathbf{s} \ne \mathbf{s'}$ (that is, either $\underline{\mathbf{s}} \backslash \underline{\mathbf{s}}'$ or $\underline{\mathbf{s}}' \backslash \underline{\mathbf{s}}$ is nonempty), then

\begin{equation*} \mathrm{E}\left(\prod_{j\in \underline{\mathbf{s}}}\tilde{X}_{s_j,a}\prod_{j\in \underline{\mathbf{s}}'}\tilde{X}_{s_j' ,a'} \right) = 0. \end{equation*}

To begin with, suppose $r\neq r'$ . Then $\mathbf{s} \ne \mathbf{s}$ ′, for any $\mathbf{s} \in [n]_{r}$ and $\mathbf{s}'\in [n]_{r'}$ . Hence, in this case all the terms in (23) are zero, and the result in (22) follows.

Now suppose $r=r'$ and $\mathbf{s}, \mathbf{s}' \in [n]_{r}$ is such that $\underline{\mathbf{s}}=\underline{\mathbf{s}}'$ . Then

\begin{align*} \frac{1}{c}\sum_{a,a'\in [c]}\mathrm{E}\left(\prod_{j\in \underline{\mathbf{s}}}\tilde{X}_{s_j, a}\prod_{j\in \underline{\mathbf{s}}'}\tilde{X}_{s_j, a'}\right) & =\frac{1}{c}\sum_{a,a'\in [c]}\mathrm{E}\left(\prod_{j\in \underline{\mathbf{s}}}\tilde{X}_{s_j, a}\tilde{X}_{s_j, a'}\right) \\[5pt] & =\frac{1}{c}\sum_{a\in [c]}\mathrm{E}\left(\prod_{j\in \underline{\mathbf{s}}}\tilde{X}_{s_j, a}^2\right) + \frac{1}{c}\sum_{ a \ne a'\in [c] }\mathrm{E}\left(\prod_{j\in \underline{\mathbf{s}}}\tilde{X}_{s_j, a}\tilde{X}_{s_j, a'}\right) \\[5pt] & =\bigg( 1-\frac{1}{c}\bigg)^r +(c-1)\bigg( -\frac{1}{c}\bigg)^r = \eta . \end{align*}

Hence, from (23),

\begin{align*} \mathrm{Cov}( \mathcal{T}(f,\tilde{\mathbf{X}}),\mathcal{T}(f',\tilde{\mathbf{X}}) ) & =\frac{1}{n^r c}\sum_{a,a'\in [c]} \sum_{\substack{ \mathbf{s} \in [n]_{r}, \mathbf{s}'\in [n]_{r} \\ \underline{\mathbf{s}}=\underline{\mathbf{s}}'}}f(\mathbf{s})f'(\mathbf{s}')\mathrm{E}\left(\prod_{j\in \underline{\mathbf{s}}}\tilde{X}_{s_j, a}\prod_{j\in \underline{\mathbf{s}}'}\tilde{X}_{s_j, a'} \right)\\[5pt] & =\eta \cdot \frac{1}{n^r}\sum_{\substack{ \mathbf{s} \in [n]_{r}, \mathbf{s}' \in [n]_{r'} \\ \underline{\mathbf{s}}=\underline{\mathbf{s}}'}}f( \mathbf{s} ) f'( \mathbf{s}') \\[5pt] & =\eta \cdot r!\,\langle f,f'\rangle_{\bullet} , \end{align*}

where the last step uses (21).

Next, we show that $\mathcal{T}(\cdot;\; \tilde{\mathbf{X}}) $ satisfies an invariance principle. Specifically, we show that the moments of $\mathcal{T}(\cdot;\; \tilde{\mathbf{X}}) $ and $\mathcal{T}(\cdot;\; \tilde{\mathbf{Z}}) $ are asymptotically close, for any finite collection of bounded functions. This result falls within the purview of universality/invariance principles for random multilinear forms (see, for example, [Reference Chatterjee26, Reference Mossel, O’Donnell and Oleszkiewicz63, Reference Nourdin, Peccati and Reinert68, Reference Rotar80]).

Proposition 1. Fix $K \geq 1$ and $r \geq 0$ . Let $\{f_{n}\}_{n \geq 1}$ be sequence of functions such that $f_{n}\;:\;[n]_{r}\rightarrow [\!-M, M]$ , for some $M > 0$ . Then

(24) \begin{align} \lim_{n\rightarrow\infty}\big| \mathrm{E} \big( \mathcal{T} ( f_{n} ;\; \tilde{\mathbf{X}} )^K \big)- \mathrm{E} \big(\mathcal{T} ( f_{n};\; \tilde{\mathbf{Z}} )^K \big) \big| = 0 . \end{align}

Proof. For notational convenience, denote

$$\Delta_{n, K}\;:\!=\; \big| \mathrm{E} \big( \mathcal{T} ( f_{n} ;\; \tilde{\mathbf{X}} )^K \big)- \mathrm{E} \big(\mathcal{T} ( f_{n};\; \tilde{\mathbf{Z}} )^K \big) \big|.$$

Note that

\begin{align*} \Delta_{n, K} & =\frac{1}{n^{\frac{K r}{2}} c^{\frac{K}{2}}}\left| \sum_{\mathbf{a}\in [c]^K}\sum_{\substack{ \mathbf{s}^{(1)}, \ldots, \mathbf{s}^{(K)} \\ \mathbf{s}^{(k)}\in [n]_{r} }} \prod_{k = 1}^{K}f_{n}(\mathbf{s}^{(k)}) \left\{ \mathrm{E} \left(\prod_{k = 1}^{K}\prod_{j\in [n]_{r}}\tilde{X}_{s^{(k)}_j,a_k}\right) - \mathrm{E}\left( \prod_{k = 1}^{K}\prod_{j\in [n]_{r}}\tilde{Z}_{s^{(k)}_j,a_k}\right) \right\} \right| , \end{align*}

where $\mathbf{a} = (a_1, a_2, \ldots, a_K) \in [c]^K$ and $\mathbf{s}^{(k)} = (s_1^{(k)}, s_2^{(k)}, \ldots, s_{r}^{(k)}) \in [n]_{r}$ , for $1 \leq k \leq K$ . Using the fact that $|f_n| \leq M$ gives

(25) \begin{align} \Delta_{n, K} & \leq \frac{M^K}{n^{\frac{K r}{2}}c^{\frac{K}{2}}} \sum_{\mathbf{a}\in [c]^K} \sum_{\substack{ \mathbf{s}^{(1)}, \ldots, \mathbf{s}^{(K)} \\ \mathbf{s}^{(k)}\in [n]_{r} }} \left|\mathrm{E} \left(\prod_{k = 1}^{K}\prod_{j\in [n]_{r}}\tilde{X}_{s^{(k)}_j,a_k}\right) - \mathrm{E}\left( \prod_{k = 1}^{K}\prod_{j\in [n]_{r}}\tilde{Z}_{s^{(k)}_j,a_k}\right) \right| . \end{align}

Given $\mathbf{a} \in [c]^K$ and $\mathbf{S} \;:\!=\; (\mathbf{s}^{(1)},\ldots, \mathbf{s}^{(K)})$ , such that $\mathbf{s}^{(k)} \in [n]_{r}$ , for $1 \leq k \leq K$ , define the edge-colored multihypergraph $F_{\mathbf{S}, \mathbf{a}} = (V(F_{\mathbf{S}, \mathbf{a}}), E(F_{\mathbf{S}, \mathbf{a}}))$ as follows:

\begin{equation*} V(F_{\mathbf{S}, \mathbf{a}}) \;:\!=\; \bigcup_{k=1}^K \underline{\mathbf{s}}^{(k)} \quad \text{and} \quad E(F_{\mathbf{S}, \mathbf{a}} ) \;:\!=\; \big\{\underline{\mathbf{s}}^{(1)}, \ldots, \underline{\mathbf{s}}^{(K)}\big\}, \end{equation*}

and the color of the hyperedge $\underline{\mathbf{s}}^{(k)}$ is $a_k$ , for $1 \leq k \leq K$ . Note that the hyperedges in $\mathbf{s}^{(1)},\ldots, \mathbf{s}^{(K)}$ can be repeated, so $E(F_{\mathbf{S}_K, \mathbf{a}} )$ is a multiset and $F_{\mathbf{S}, \mathbf{a}}$ is a multihypergraph. In addition, define

\begin{equation*} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}} \;:\!=\; \prod_{k = 1}^{K}\prod_{j\in [n]_{r}}\tilde{X}_{s^{(k)}_j,a_k} \quad \text{and} \quad \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}} \;:\!=\; \prod_{k = 1}^{K}\prod_{j\in [n]_{r}}\tilde{Z}_{s^{(k)}_j,a_k} . \end{equation*}

The following lemma records two crucial properties of $\mathrm{E} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}}$ and $\mathrm{E} \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}}$ .

Proof. Note that

(26) \begin{align} \mathrm{E} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}} = \mathrm{E}\left( \prod_{j\in V(F_{\mathbf{S}, \mathbf{a}})}\prod_{a=1}^c \tilde{X}_{j,a}^{\ell_{j,a}} \right)= \prod_{j\in V(F_{\mathbf{S}, \mathbf{a}})} \mathrm{E}\left( \prod_{a=1}^c \tilde{X}_{j,a}^{\ell_{j,a}} \right)\!, \end{align}

where $\ell_{j,a}$ be the number of hyperedges with color $a \in [c]$ containing the vertex $j \in V(F_{\mathbf{S}, \mathbf{a}})$ .

Now, if $j \in V(F_{\mathbf{S}, \mathbf{a}})$ is such that $d_j = 1$ then there exists $b \in [c]$ such that $\ell_{j,b} =1$ and $\ell_{j,a} =0 $ , for all $a \in [c]\backslash{b}$ . This means that

\begin{equation*} \mathrm{E}\left(\prod_{a=1}^c \tilde{X}_{j,a}^{\ell_{j,a}} \right) = \mathrm{E} \tilde{X}_{j,b} = 0 \end{equation*}

and, consequently, $\mathrm{E} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}} = 0$ . By the same argument, we also have $\mathrm{E} \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}} = 0$ .

Next, suppose $d_j = 2$ for all $j \in V(F_{\mathbf{S}, \mathbf{a}})$ . Then there are two possibilities.

• • There exists $b \in [c]$ such that $\ell_{j,b} =2$ and $\ell_{j,a} =0 $ , for all $a \in [c]\backslash\{b\}$ . This means that

  \begin{equation*} \mathrm{E}\left(\prod_{a=1}^c \tilde{X}_{j,a}^{\ell_{j,a}} \right) = \mathrm{E} \tilde{X}_{j,b}^2 = 1-\frac{1}{c} , \end{equation*}
  by Observation 1. By the same argument,
  \begin{equation*} \mathrm{E}\left(\prod_{a=1}^c \tilde{Z}_{j,a}^{\ell_{j,a}} \right) = \mathrm{E} \tilde{Z}_{j,b}^2 = 1-\frac{1}{c}. \end{equation*}

• • There exists $b \ne b' \in [c]$ such that $\ell_{j,b} = \ell_{j,b'} = 1$ and $\ell_{j,a} =0 $ , for all $a \in [c]\backslash\{ b, b' \}$ . This means that

  \begin{equation*} \mathrm{E}\left(\prod_{a=1}^c \tilde{X}_{j,a}^{\ell_{j,a}} \right) = \mathrm{E} \tilde{X}_{j,b} \tilde{X}_{j,b'} = -\frac{1}{c}, \end{equation*}
  by Observation 1. By the same argument,
  \begin{equation*} \mathrm{E}\left(\prod_{a=1}^c \tilde{Z}_{j,a}^{\ell_{j,a}} \right) = \mathrm{E} \tilde{Z}_{j,b} \tilde{Z}_{j,b'} = -\frac{1}{c}. \end{equation*}

Hence, if $d_j = 2$ then

\begin{align*} \mathrm{E}\left(\prod_{a=1}^c \tilde{X}_{j,a}^{\ell_{j,a}} \right) = \mathrm{E}\left(\prod_{a=1}^c \tilde{Z}_{j,a}^{\ell_{j,a}} \right)\!. \end{align*}

Hence, taking product over $j \in V(F_{\mathbf{S}, \mathbf{a}})$ (recall (26)) gives $\mathrm{E} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}} = \mathrm{E} \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}} $ .

The next lemma gives bounds on $\mathrm{E} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}}$ and $\mathrm{E} \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}}$ .

Lemma 3. For any $\mathbf{a} = (a_1, a_2, \ldots, a_K) \in [c]^K$ and $\mathbf{S} = (\mathbf{s}^{(1)},\ldots, \mathbf{s}^{(K)})$ , with $\mathbf{s}^{(k)} \in [n]_{r}$ , for $1 \leq k \leq K$ , we have

(27) \begin{align} \mathrm{E} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}} & \lesssim_{K, c, r} 1 . \end{align}

Moreover, $ \mathrm{E} \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}} \lesssim_{K, c, r} 1$ .

Proof. Note that for each $j \in V(F_{\mathbf{S}, \mathbf{a}})$ ,

(28) \begin{align} \left|\mathrm{E}\left( \prod_{a=1}^c \tilde{X}_{j,a}^{\ell_{j,a}} \right)\right| & = c^{\frac{1}{2} \sum_{a =1}^{c} \ell_{j, a}} \left| \mathrm{E} \prod_{a =1}^c \left( \textbf{1} \{X_{j}=a\}-\frac{1}{c}\right)^{\ell_{j, a}} \right| \lesssim_{K, c, r} 1 . \end{align}

Hence, from (26), $|\mathrm{E} \tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}} | \lesssim_{K, c, r} 1$ . This proves (27).

Next, we bound $\mathrm{E} \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}}$ . First, observe that for each $j \in V(F_{\mathbf{S}, \mathbf{a}})$ ,

(29) \begin{align} \left|\mathrm{E}\left( \prod_{a=1}^c \tilde{Z}_{j,a}^{\ell_{j,a}} \right)\right| & \leq \mathrm{E} \prod_{a =1}^{c} \left| Z_{j, a} - \frac{1}{c} \sum_{b=1}^c Z_{j, b} \right| ^{\ell_{j, a}} \lesssim_{K, c, r} 1. \end{align}

This implies that

\begin{align*} | \mathrm{E} \tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}} | = \left| \mathrm{E}\left( \prod_{j\in V(F_{\mathbf{S}, \mathbf{a}})}\prod_{a=1}^c \tilde{Z}_{j,a}^{\ell_{j,a}} \right) \right| = \prod_{j\in V(F_{\mathbf{S}, \mathbf{a}})} \left| \mathrm{E}\left( \prod_{a=1}^c \tilde{Z}_{j,a}^{\ell_{j,a}} \right) \right| \lesssim_{K, c, r} 1 , \end{align*}

since $|V(F_{\mathbf{S}, \mathbf{a}})| \leq K r$ . This completes the proof of Lemma 3.

Now let $\mathcal{F}$ be the set of colored hypergraphs with the following properties:

• • $F \in \mathcal{F}$ is a hypergraph with vertex set contained in [Kr] and K hyperedges, and every hyperedge of F is assigned a color from [K];

• • all vertices of F have degree at least 2; and

• • some vertex of F has degree at least 3.

Note that for $F \in \mathcal{F}$ there are $O(n^{|V(F)|})$ terms in the joint sum (25) such that $F_{\mathbf{S}, \mathbf{a}}$ is isomorphic (as a colored hypergraph) to F. In such case, $\mathrm{E}\tilde{\mathbf{X}}_{F}=\mathrm{E}\tilde{\mathbf{X}}_{F_{\mathbf{S}, \mathbf{a}}}$ and $\mathrm{E}\tilde{\mathbf{Z}}_{F}=\mathrm{E}\tilde{\mathbf{Z}}_{F_{\mathbf{S}, \mathbf{a}}}$ . This implies, from (25) and Lemma 2, that

(30) \begin{align} \Delta_{n, K} & \lesssim_{M, K, c} \frac{1}{n^{\frac{Kr}{2}}} \sum_{F \in \mathcal{F}} n^{|V(F)|} | \mathrm{E} \tilde{\mathbf{X}}_{F} - \mathrm{E} \tilde{\mathbf{Z}}_{F} |\nonumber \\[5pt] & \lesssim_{M, K, c} \sum_{F \in \mathcal{F}}n^{ |V(F)| -\frac{Kr}{2}} . \end{align}

Note that $Kr=\sum_{e\in E(F)}|e|$ . In addition, for $F \in \mathcal{F}$ , we have that $d_j \geq 2$ for all $j\in V(F)$ with strict inequality for some j. Therefore,

\begin{align*} \frac{Kr }{2} = \frac{1}{2}\sum_{e\in E(F)}|e|=\frac{1}{2}\sum_{j\in V(F)} d_j > |V(F)|. \end{align*}

Hence, each term in (30) is o(1). Since $|\mathcal{F}| \lesssim_{K, c, r} 1$ , the result in Proposition 1 now follows.

3. Proof of Theorem 1

Recall the definition of $T(H,G_n)$ from (2), which is the number of monochromatic copies of H in $G_n$ :

(31) \begin{align} T(H,G_n)= \frac{1}{|{\textrm{Aut}}(H)|}\sum_{\mathbf{s}\in [n]_{|V(H)|}}\prod_{(a,b)\in E(H)}a_{s_as_b}(G_n)\textbf{1}\{X_{=\mathbf{s}}\} .\end{align}

We begin by rewriting $T(H,G_n)$ in terms of $\mathcal{T}(\cdot,\tilde{\mathbf{X}})$ . To this end, we set $V(H) = [|V(H)|]\;:\!=\; \{1, 2, \ldots, |V(H)|\}$ . In addition, for $J=\{i_1<\cdots < i_{|J|}\}\subseteq [|V(H)|]$ and $\mathbf{s} \in [n]_{|V(H)|}$ , denote $\mathbf{s}_J = (s_{i_1},\ldots, s_{i_{|J|}})$ .

Lemma 4. For $J=\{i_1<\cdots < i_{|J|}\}\subseteq [|V(H)|]$ , define $f_{H, J}^{G_n}\;:\;[n]_{|J|}\rightarrow [0,1]$ as follows:

(32) \begin{align} f_{H, J}^{G_n}(\mathbf{t})\;:\!=\;\frac{1}{n^{|V(H)|-|J|}}\sum_{\substack{\mathbf{s}\in [n]_{|V(H)|} \\ \mathbf{s}_J=\mathbf{t}}}\prod_{(a,b)\in E(H)}a_{\mathbf{s}_a \mathbf{s}_b}(G_n) . \end{align}

Then

(33) \begin{align} T(H,G_n)-\mathrm{E}(T(H,G_n))= \frac{1}{|{\mathrm{Aut}}(H)|}\sum_{\substack{J\subseteq V(H)\\ |J|\geq 2}}\mathcal{T}\Big( f_{H, J}^{G_n};\; \tilde{\mathbf{X}} \Big) \frac{n^{|V(H)|-\frac{|J|}{2}}}{c^{|V(H)|-\frac{|J|}{2}-\frac{1}{2}}} . \end{align}

Proof. Note that

(34) \begin{align} \textbf{1}\{X_{=\mathbf{s}}\} & = \sum_{a=1}^c \prod_{j=1}^{|V(H)|} \textbf{1}\{X_{s_j}=a\} \nonumber \\[3pt] & = \sum_{a=1}^c \prod_{j=1}^{|V(H)|}\bigg( \textbf{1}\{X_{s_j}=a\} -\frac{1}{c}+\frac{1}{c}\bigg) \nonumber \\[3pt] & = \sum_{a=1}^c \sum_{J\subseteq V(H)}\prod_{j\in J}\bigg( \textbf{1}\{X_{s_j}=a\} -\frac{1}{c}\bigg) \frac{1}{c^{|V(H)|-|J|}} \nonumber \\[3pt] & = \sum_{a=1}^c \sum_{J\subseteq V(H)}\prod_{j\in J} \tilde{X}_{s_j, a}\frac{1}{c^{|V(H)|-\frac{|J|}{2}}} . \end{align}

Then, recalling (20), we have

(35) \begin{align} \mathcal{T}\Big(f_{H, J}^{G_n};\; \tilde{\mathbf{X}}\Big) & = \frac{1}{n^{|V(H)| - \frac{|J|}{2}}\sqrt{c}\,}\sum_{a=1}^{c}\sum_{\mathbf{t}\in [n]_{|J|}} \sum_{\substack{\mathbf{s}\in [n]_{|V(H)|} \\ \mathbf{s}_J=\mathbf{t}}}\prod_{(a,b)\in E(H)}a_{\mathbf{s}_a \mathbf{s}_b}(G_n) \prod_{j \in J} \tilde{X}_{t_j, a} \nonumber \\[3pt] & = \frac{1}{n^{|V(H)| - \frac{|J|}{2}}\sqrt{c}\,}\sum_{a=1}^{c} \sum_{\mathbf{s}\in [n]_{|V(H)|} } \prod_{(a,b)\in E(H)}a_{\mathbf{s}_a \mathbf{s}_b}(G_n) \prod_{j \in J} \tilde{X}_{s_j, a} . \end{align}

Hence,

(36) \begin{align} & \frac{1}{|{\textrm{Aut}}(H)|}\sum_{J\subseteq V(H)} \mathcal{T}\left( f_{H, J}^{G_n};\; \tilde{\mathbf{X}} \right) \frac{n^{|V(H)|-\frac{|J|}{2}}}{c^{|V(H)|-\frac{|J|}{2}-\frac{1}{2}}} \nonumber \\[3pt] & = \frac{1}{|{\textrm{Aut}}(H)|}\sum_{J\subseteq V(H)} \sum_{a=1}^{c} \sum_{\mathbf{s}\in [n]_{|V(H)|} } \prod_{(a,b)\in E(H)}a_{\mathbf{s}_a \mathbf{s}_b}(G_n) \prod_{j \in J} \tilde{X}_{s_j, a} \frac{1}{c^{|V(H)|-\frac{|J|}{2}}} \nonumber \\[3pt] & = \frac{1}{|{\textrm{Aut}}(H)|} \sum_{\mathbf{s}\in [n]_{|V(H)|} } \prod_{(a,b)\in E(H)}a_{\mathbf{s}_a \mathbf{s}_b}(G_n) \textbf{1}\{X_{=\mathbf{s}}\} , \end{align}

where the last step uses (34).

Now observe that, if $J=\{j_0\}$ , for some $j_0 \in V(H)$ ,

\begin{align*} \sum_{a=1}^c\prod_{j\in J}\left( \textbf{1}\{X_{s_j}=a\} -\frac{1}{c}\right)=\sum_{a=1}^c\left( \textbf{1}\{X_{s_{j_0}}=a\} -\frac{1}{c}\right)=0. \end{align*}

This means (recall (35)) that

(37) \begin{equation} \sum_{\substack{J\subseteq V(H)\\ |J|= 1}}\mathcal{T}\left( f_{H, J}^{G_n};\; \tilde{\mathbf{X}} \right) = 0. \end{equation}

In addition, note that when $J = \emptyset$ ,

(38) \begin{equation} \frac{1}{|{\textrm{Aut}}(H)|} \mathcal{T}\left( f_{H,\emptyset}^{G_n};\; \tilde{\mathbf{X}} \right) \frac{n^{|V(H)|}}{c^{|V(H)|-\frac{1}{2}}} = \mathrm{E}(T(H,G_n)) . \end{equation}

Combining (36), (37), and (38) and rearranging the sums, the result in Lemma 4 follows.

Now let $\{U_r\}_{r\in V(H)}$ be a collection of i.i.d. uniform random variables on [0,Reference Abraham, Delmas and Weibel1]. Define the counterpart of $W_H$ for finite n as follows:

(39) \begin{equation} \tilde{W}^{G_n}_{H}(x,y) \;:\!=\; \sum_{1\leq u\neq v\leq |V(H)|} \mathrm{E}\left(\textbf{1}\{A_n\}\prod_{(i, j)\in E(H)}W^{G_n}(U_i, U_j)\, \middle|\, U_u = x, U_v = y\right)\!,\end{equation}

where $A_n$ is the event that the variables $\{U_r\}_{r\in V(H)}$ fall in distinct intervals when [0, 1] is partitioned in a grid of size $\frac{1}{n}$ , that is, $A_n=\{(\lceil nU_r \rceil)_{r\in V(H)}\in [n]_{|V(H)|}\}$ . (We show in Lemma 5 that $\tilde{W}^{G_n}_{H}$ is directly related to $f_{H,J}^{G_n}$ , which is a sum over distinct indices; see (32). This set of distinct indices gets translated to the event $A_n$ in (39).) Then we define

(40) \begin{align} Q(H, G_n) & \;:\!=\; \frac{1}{ 2 n\sqrt{c}\,}\sum_{a=1}^c \sum_{1 \leq u \ne v \leq n} \tilde{W}^{G_n}_{H}\left(\frac{u}{n},\frac{v}{n}\right) \tilde{Z}_{u, a} \tilde{Z}_{v, a} , \end{align}

where $\{\tilde{Z}_{v, a}\}_{v \in [n], a \in [c]}$ is defined in (19).

Lemma 5. Let $\Gamma(H,G_n)$ and $Q(H, G_n)$ be as defined in (11) and (40), respectively. Then

(41) \begin{align} Q(H, G_n) = \mathcal{T}\left( \sum_{\substack{J\subseteq V(H) \\ |J|= 2}} f_{H, J}^{G_n};\; \tilde{\mathbf{Z}} \right)\!. \end{align}

In addition, as $n \rightarrow \infty$ ,

(42) \begin{align} \Gamma(H,G_n) & = \mathcal{T}\left( \sum_{\substack{J\subseteq V(H) \\ |J|= 2}} f_{H, J}^{G_n};\; \tilde{\mathbf{X}} \right) + o_{L_2}(1) . \end{align}

Proof. Recalling (32) and (39), we obtain, for $1 \leq i \ne j \leq n$ ,

\begin{align*} \sum_{\substack{J\subseteq V(H) \\ |J|= 2}} f_{H, J}^{G_n}(i, j) =\frac{1}{n^{|V(H)|-2}}\sum_{1 \leq u < v\leq |V(H)|}\sum_{\substack{\mathbf{s}\in [n]_{|V(H)|}\\ s_u=i,\ s_v=j } }\prod_{(a,b)\in E(H)}a_{\mathbf{s}_a \mathbf{s}_b}(G_n) & = \frac{1}{2}\tilde{W}^{G_n}_{H}\left( x,y \right)\!, \end{align*}

for $x\in [\frac{i}{n},\frac{i+1}{n}]$ and $y\in [\frac{j}{n},\frac{j+1}{n}]$ . Therefore,

\begin{align*} \mathcal{T}\left( \sum_{\substack{J\subseteq V(H) \\[5pt] |J|= 2}} f_{H, J}^{G_n} ; \tilde{\mathbf{Z}} \right) & = \frac{1}{ 2 n\sqrt{c}\,}\sum_{a=1}^c \sum_{1 \leq u \ne v \leq n} \tilde{W}^{G_n}_{H}\left(\frac{u}{n},\frac{v}{n}\right) \tilde{Z}_{u, a} \tilde{Z}_{v, a} = Q(H, G_n) . \end{align*}

This proves (41).

Next, recalling (11) and from (33), we have

(43) \begin{align} \Gamma(H, G_n) & = \frac{c^{|V(H)|-\frac{3}{2}}}{n^{|V(H)|-1}} \left\{ T(H,G_n)-\mathrm{E}(T(H,G_n)) \right\} \nonumber \\[5pt] & = \frac{1}{|{\textrm{Aut}}(H)|}\sum_{\substack{J\subseteq V(H) \\ |J|\geq 2}}\mathcal{T}\left( f_{H, J}^{G_n};\; \tilde{\mathbf{X}} \right) \frac{c^{\frac{|J|}{2}-\frac{1}{2}} }{n^{\frac{|J|}{2}-1}} . \end{align}

Note that, for any $J \subseteq V(H)$ , with $|J| \geq 3$ , $\mathrm{E} \mathcal{T}(f_{H, J}^{G_n};\; \tilde{\mathbf{X}}) = 0$ and, from Lemma 1,

\begin{align*} \frac{1}{n^{|J| -2}} \mathrm{Var} \left(\mathcal{T}\left(f_{H, J}^{G_n};\; \tilde{\mathbf{X}}\right)\right ) & = \frac{\eta |J|!}{n^{|J| -2}} \|\tilde{f}_{H, J}^{G_n} \|_2^2 = o(1) , \end{align*}

since $0\leq \tilde{f}_{H, J}^{G_n} \leq 1$ . Hence, $\mathcal{T}(f_{H, J}^{G_n}) = o_{L_2}(1)$ , for all $J \subseteq V(H)$ such that $|J| \geq 3$ . This implies, from (43), that

\begin{align*} \Gamma(H,G_n) & = \frac{c^{|V(H)|-\frac{3}{2}}}{n^{|V(H)|-1}} \sum_{\substack{J\subseteq V(H) \\ |J|= 2}}\mathcal{T}\left( f_{H, J}^{G_n};\; \tilde{\mathbf{X}} \right) \frac{n^{|V(H)|-\frac{|J|}{2}}}{c^{|V(H)|-\frac{|J|}{2}-\frac{1}{2}}} + o_{L_2}(1)\\[5pt] & = \mathcal{T}\left( \sum_{\substack{J\subseteq V(H) \\ |J|= 2}} f_{H, J}^{G_n};\; \tilde{\mathbf{X}} \right) + o_{L_2}(1). \end{align*}

This proves (42) and completes the proof of Lemma 5.

The following lemma represents $Q(H,G_n)$ as a sum of independent bivariate stochastic integrals.

Lemma 6. Let $\big\{B^{(1)}(t), B^{(2)}(t), \ldots, B^{(c-1)}(t)\big\}_{t \in [0, 1]}$ be a collection of independent Brownian motions on [0, 1] and $Q(H,G_n)$ be as defined in (40). Then

\begin{align*} Q(H,G_n) \stackrel{D} = \frac{1}{2\sqrt{c}\,}\sum_{a=1}^{c-1}\int_{[0, 1]^2} \tilde{W}^{G_n}_{H}(x,y)\,\mathrm{d}B^{(a)}_x\,\mathrm{d}B^{(a)}_y . \end{align*}

Proof. Let $\{Z_{v, a}\}_{v\in [n],a\in [c]}$ be a collection of i.i.d. N(0,1) random variables. For $1 \leq v \leq n$ , let $\mathbf{Z}_v = (Z_{v, 1}, Z_{v, 2}, \ldots, Z_{v, c})^\top$ . Then, for $1 \leq v \leq n$ , $\mathbf{M} \mathbf{Z}_v = \tilde{\mathbf{Z}}_v$ , where $\tilde{\mathbf{Z}}_v = (\tilde{Z}_{v, 1}, \tilde{Z}_{v, 2}, \ldots, \tilde{Z}_{v, c})^\top$ , $\mathbf{M}= \mathbf{I}-\frac{1}{c}\textbf{1}^{\top}\textbf{1}$ , and $\textbf{1}$ is the vector of ones of length c. Note that $\mathbf{M}^\top \mathbf{M} = \mathbf{M}$ and $\mathbf{M}$ has $c-1$ nonzero eigenvalues all of which are 1. Hence, we can write

\begin{align*} Q(H,G_n) & =\frac{1}{ 2 n\sqrt{c}\,}\sum_{a=1}^c\sum_{1\leq u \neq v \leq n}\tilde{W}^{G_n}_{H}\left( \frac{u}{n},\frac{v}{n}\right)\tilde{Z}_{u,a}\tilde{Z}_{v,a} \\[5pt] & = \frac{1}{ 2 n\sqrt{c}\,}\sum_{1\leq u \neq v \leq n}\tilde{W}^{G_n}_{H}\left(\frac{u}{n},\frac{v}{n}\right) \mathbf{Z}_u^\top \mathbf{M}^\top \mathbf{M} \mathbf{Z}_v \end{align*}

\begin{align*} & = \frac{1}{ 2 n\sqrt{c}\,}\sum_{1\leq u \neq v \leq n}\tilde{W}^{G_n}_{H}\left(\frac{u}{n},\frac{v}{n}\right) \mathbf{Z}_u^\top \mathbf{M} \mathbf{Z}_v \nonumber \\[5pt] & \stackrel{D}= \frac{1}{ 2 n\sqrt{c}\,}\sum_{1\leq u \neq v \leq n}\tilde{W}^{G_n}_{H}\left( \frac{u}{n},\frac{v}{n}\right)\sum_{a=1}^{c-1} Y_{u,a} Y_{v,a}\\& \qquad\qquad\qquad \textrm{(where $\{Y_{v, a}\}_{v\in [n],a\in [c-1]}$ are i.i.d.}\,{N}(0, 1)) \nonumber \\[5pt] & \stackrel{D}{=} \frac{1}{ 2 \sqrt{c}\,}\sum_{a=1}^{c-1}\int_{[0, 1]^2} \tilde{W}^{G_n}_{H}(x,y)\,\mathrm{d}B^{(a)}_x\,\mathrm{d}B^{(a)}_y, \end{align*}

where the last inequality follows after noting that

$$\frac{1}{n}Y_{u,a}Y_{v,a}\stackrel{D}{=}\int_{[0,1]^2}\textbf{1}\bigg\{\bigg[\frac{u-1}{n},\frac{u}{n}\bigg)\times \bigg[\frac{v-1}{n},\frac{v}{n}\bigg)\bigg\} \mathrm{d}B_x \mathrm{d}B_y$$

and that $\tilde{W}^{G_n}_{H}$ is a constant on $\big[\frac{u-1}{n},\frac{u}{n}\big)\times \big[\frac{v-1}{n},\frac{v}{n}\big)$ , for all $1\leq u\neq v\leq n$ .

With the above preparations, we proceed with the proof of Theorem 1. For this, suppose $\mathcal{H}= (H_1, H_2, \ldots, H_d)$ is a finite collection of graphs and $\mathbf{G}_n = (G_n^{(1)}, G_n^{(2)}, \ldots, G_n^{(d)})$ is a sequence of d-multiplexes converging in multiplex cut-norm to $\mathbf{W} = (W_1, W_2, \ldots, W_d)$ . Recall the definition of $\boldsymbol{\Gamma}(\mathcal{H}, \mathbf{G}_n)$ from (10) and define

\begin{equation*} \mathbf{Q}(\mathcal{H}, \mathbf{G}_n) = \big(Q\big(H_1, G_n^{(1)}\big), Q\big(H_2,G_n^{(2)}\big), \ldots, Q\big(H_d, G_n^{(d)}\big)\big)^\top.\end{equation*}

Then, for any vector $\boldsymbol \alpha = (\alpha_1, \alpha_2, \ldots, \alpha_d) \in \mathbb{R}^d$ , recalling (41), we have

\begin{align*} \boldsymbol \alpha^\top Q(\mathcal{H}, \mathbf{G}_n) = \mathcal{T}\left( \sum_{i=1}^d \sum_{\substack{J\subseteq V(H_i) \\ |J|= 2}} \alpha_i\, f_{H_i, J}^{G_n^{(i)}};\; \tilde{\mathbf{Z}} \right)\!.\end{align*}

In addition, from (42) we have, as $n \rightarrow \infty$ ,

\begin{align*} \boldsymbol \alpha^\top \boldsymbol \Gamma(\mathcal{H}, \mathbf{G}_n) & = \mathcal{T}\left( \sum_{i=1}^d \sum_{\substack{J\subseteq V(H_i) \\ |J|= 2}} \alpha_i\, f_{H_i, J}^{G_n^{(i)}};\; \tilde{\mathbf{X}} \right) + o_{L_2}(1) .\end{align*}

From Proposition 1 and the above we have, for all integers $K \geq 1$ ,

\begin{align*} \lim_{n \rightarrow \infty} \left| \mathrm{E} \left(\big(\boldsymbol \alpha^ \top \boldsymbol{\Gamma}(\mathcal{H}, \mathbf{G}_n)\big)^K\right) - \mathrm{E} \left(\big(\boldsymbol \alpha^ \top \mathbf{Q}(\mathcal{H}, \mathbf{G}_n)\big)^K \right) \right| = 0.\end{align*}

Therefore, by the Cramér–Wold device, to prove Theorem 1 it suffices to derive the limiting distribution of $\boldsymbol \alpha^ \top \mathbf{Q}(\mathcal{H}, \mathbf{G}_n)$ . For this, note that

(44) \begin{align} \boldsymbol{\alpha}^{\top} \mathbf{Q}(\mathcal{H}, \mathbf{G}_n) = \sum_{i=1}^d \alpha_i Q\big(H_i, G_n^{(i)}\big) = \frac{1}{ 2 \sqrt{c}\,}\sum_{a=1}^{c-1}I^{(a)}_2\left( \sum_{i=1}^d \alpha_i \tilde{W}^{G_n^{(i)}}_{H_i} \right)\!,\end{align}

where $I^{(a)}_2(F)\;:\!=\;\int_{[0,1]^2}F(x,y)\,\mathrm{d}B^{(a)}_x\,\mathrm{d}B^{(a)}_y$ , for any bounded symmetric kernel $F \in \mathscr{W}_1$ . Observe that for any $1 \leq i \leq d$ ,

$$\Big\|\tilde{W}^{G_n^{(i)}}_{H_i}-W^{G_n^{(i)}}_{H_i}\Big\|_2^2 \leq |V(H_i)|^2\mathrm{P}\big(A_n^c\big) . $$

Since $(\lceil nU_i \rceil)_{i \in V(H)}$ is a uniform random vector over $[n]^{V(H)}$ ,

$$\mathrm{P}(A_n)=\frac{n(n-1)\cdots (n-|V(H)| +1 )}{n^{|V(H)|}}\rightarrow 1.$$

Hence, (44) has the same limiting distribution as

(45) \begin{align} \frac{1}{ 2 \sqrt{c}\,} \sum_{a=1}^{c-1} I^{(a)}_2\left( \sum_{i=1}^d \alpha_i W^{G_n^{(i)}}_{H_i} \right)\!.\end{align}

Now let

(46) \begin{align} W_{\boldsymbol{\alpha}, n} \;:\!=\; \sum_{i=1}^d \alpha_i W^{G_n^{(i)}}_{H_i} \quad\text{and}\quad W_{\boldsymbol \alpha} \;:\!=\; \sum_{i=1}^d \alpha_i (W_i)_{H_i} .\end{align}

Since $\mathbf{G}_n$ converges to $\mathbf{W}$ in the multiplex cut-metric, there is a sequence of invertible measure-preserving maps $\phi_n\;:\;[0,1]\rightarrow [0,1]$ such that

\begin{equation*} \sum_{i=1}^d \Big\|\Big(W^{G_n^{(i)}}\Big)^{\phi_n}-W_i \Big\|_{\square} \rightarrow 0.\end{equation*}

Let $\mathscr{W}_1$ be the space of bounded, symmetric, measurable functions from $[0, 1]^2$ to $[0, \infty)$ . Define the map $\eta_{H_i} \;:\; \mathscr{W}_1 \rightarrow \mathscr{W}_1$ , for $1 \leq i \leq d$ , given by $\eta_{H_i}(W) = W_{H_i}$ . Note that $\eta_{H_i}((W^{G_n^{(i)}})^{\phi_n}) = \eta_{H_i}(W^{G_n^{(i)}})^{\phi_n}$ . Then by Lemma 9, as $n \rightarrow \infty$ ,

(47) \begin{align} \| W_{\boldsymbol{\alpha}, n}^{\phi_n} - W_{\boldsymbol{\alpha}}\|_\square \rightarrow 0 .\end{align}

Using (46), we can rewrite (45) as

(48) \begin{align} \frac{1}{ 2 \sqrt{c}\,} \sum_{a=1}^{c-1} I^{(a)}_2\left( \sum_{i=1}^d \alpha_i W^{G_n^{(i)}}_{H_i} \right) & = \frac{1}{ 2 \sqrt{c}\,} \sum_{a=1}^{c-1} I^{(a)}_2\big( W_{\boldsymbol{\alpha}, n} \big) \nonumber\\[5pt] & \stackrel{D} = \frac{1}{ 2 \sqrt{c}\,} \sum_{a=1}^{c-1} I^{(a)}_2( W_{\boldsymbol{\alpha}, n}^{\phi_n} ) \nonumber\\[5pt] & = \frac{1}{ 2 \sqrt{c}\,}\sum_{a=1}^{c-1}I_2^{(a)}\big(W_{\boldsymbol \alpha, n}^{\phi_n}-W_{\boldsymbol{\alpha}}\big)+\frac{1}{ 2 \sqrt{c}\,}\sum_{a=1}^{c-1}I_2^{(a)}(W_{\boldsymbol{\alpha}}) .\end{align}

By Lemma 10 the two terms in the right-hand side above are asymptotically independent, hence it suffices to derive the limiting distribution of the first term.

Lemma 7. As $n \rightarrow \infty$ ,

(49) \begin{align} \frac{1}{2 \sqrt{c}\,}\sum_{a=1}^{c-1}I_2^{(a)}\big(W_{\boldsymbol \alpha, n}^{\phi_n}-W_{\boldsymbol{\alpha}}\big) \stackrel{D}{\to} \sqrt{\frac{c-1}{2c}} N(0, \boldsymbol \alpha^\top \Sigma \boldsymbol \alpha ) , \end{align}

where $\Sigma$ is defined in Theorem 1.

Proof. By the spectral theorem for bounded symmetric kernels (see [Reference Lovász52, Section 7.5]),

$$\Delta_{\alpha, n}(x, y)\;:\!=\; W_{\boldsymbol \alpha,n}^{\phi_n}(x,y)-W_{\boldsymbol{\alpha}}(x,y)=\sum_{s=1}^\infty \lambda^{(n)}_s \phi_s^{(n)}(x) \phi_s^{(n)}(y), $$

where $\{\lambda^{(n)}_s\}_{s \geq 1}$ are the eigenvalues and $\{ \phi_s^{(n)}\}_{s \geq 1}$ are a set of orthonormal eigenvectors for the operator

$$T_{\Delta_{\boldsymbol{\alpha}, n}} f (x) = \int_0^1 \Delta_{\boldsymbol{\alpha}, n}(x, y) f(y) \mathrm{d}y.$$

Define, for $s \geq 1$ ,

\begin{align*} \xi_s=\sum_{a=1}^{c-1} \left(\int_0^1 \phi_s^{(n)}(x)\mathrm{d}B^{(a)}_x \right)^2-(c-1). \end{align*}

By orthonormality, the variables $\{\xi_s\}_{s \geq 1}$ have independent $\chi^2_{c-1}-(c-1)$ distributions. Hence,

\begin{align*} \frac{1}{2\sqrt{c}\,}\sum_{a=1}^{c-1}I_2^{(a)}\big(W_{\boldsymbol \alpha,n}^{\phi_n}-W_{\boldsymbol{\alpha}}\big) \stackrel{D} = \frac{1}{2 \sqrt{c}\,}\sum_{s=1}^{\infty}\lambda^{(n)}_s \xi_s. \end{align*}

The result in (49) then follows from Lemma 11 if we show the following:

(50) \begin{align} \lim_{n \rightarrow \infty} \max_{s \geq 1}\big|\lambda_s^{(n)}\big| = 0 \quad\text{and}\quad\lim_{n \rightarrow \infty} \sum_{s \geq 1}|\lambda_s^{(n)}|_2^2 = \boldsymbol{\alpha}^\top \Sigma \boldsymbol{\alpha}. \end{align}

To show the first condition in (50), we will use the identity $\sum_{s \geq 1}(\lambda^{(n)}_s )^4=t(C_4, \Delta_{n, \boldsymbol{\alpha}})$ (see [Reference Lovász52, Section 7.5]), where $C_4$ denotes the cycle of size 4. This implies that

\begin{align*} \max_{s \geq 1}|\lambda_s^{(n)}|^4 \leq \sum_{s=1}^\infty \big(\lambda^{(n)}_s \big)^4=t(C_4, \Delta_{n, \boldsymbol{\alpha}}) & = \|\Delta_{n, \boldsymbol{\alpha}}\|_{\infty}^4t\left( C_4, \frac{\Delta_{n, \boldsymbol{\alpha}}}{\|\Delta_{n, \boldsymbol{\alpha}}\|_{\infty}}\right) \nonumber \\[5pt] & \leq 16\|\Delta_{n, \boldsymbol{\alpha}}\|_{\infty}^3\|\Delta_{n, \boldsymbol{\alpha}} \|_\square \rightarrow 0, \end{align*}

by (47), the counting lemma [Reference Lovász52, Lemma 10.24], and the fact that

\begin{equation*} \|\Delta_{n, \boldsymbol{\alpha}}\|_{\infty}\leq \sum_{i=1}^d|\alpha_i|\Big\|W^{G_n^{(i)}}_{H_i}\Big\|_{\infty} \leq \sum_{i=1}^d|\alpha_i|(|V(H_i)|-1)|V(H_i)|. \end{equation*}

We now prove the second condition in (50). For this, observe that

\begin{align*} \lim_{n\rightarrow\infty}\|\Delta_{n, \boldsymbol{\alpha}}\|_2^2 & = \lim_{n\rightarrow\infty}\big\|W_{\boldsymbol \alpha,n}^{\phi_n}-W_{\boldsymbol{\alpha}}\big\|_2^2 \\[5pt] & = \lim_{n\rightarrow\infty}\big\|W_{\boldsymbol \alpha, n}^{\phi_n} \big\|_2^2 - 2 \lim_{n\rightarrow\infty} \big\langle W_{\boldsymbol \alpha,n}^{\phi_n}, W_{\boldsymbol{\alpha}} \big\rangle +\|W_{\boldsymbol{\alpha}}\|_2^2 \\[5pt] & = \lim_{n\rightarrow\infty}\|W_{\boldsymbol \alpha, n} \|_2^2-\|W_{\boldsymbol{\alpha}}\|_2^2, \end{align*}

using the fact that $\lim_{n\rightarrow\infty} \langle W_{\boldsymbol \alpha,n}^{\phi_n}, W_{\boldsymbol{\alpha}} \rangle = \|W_{\boldsymbol{\alpha}}\|_2^2$ , which follows from (47) and by invoking [Reference Lovász52, Lemma 8.22]. In addition,

\begin{align*} \lim_{n\rightarrow\infty}\|W_{\boldsymbol \alpha, n} \|_2^2 & = \lim_{n\rightarrow\infty}\left\| \sum_{i=1}^d \alpha_i W^{G_n^{(i)}}_{H_i} \right\|_2^2 \\[5pt] & = \lim_{n\rightarrow\infty} \left\{ \sum_{i=1}^d \alpha_i^2 \| W^{G_n^{(i)}}_{H_i} \|_2^2 + \sum_{1 \leq i \ne j \leq d} \alpha_i \alpha_j \Big\langle W^{G_n^{(i)}}_{H_i} , W^{G_n^{(j)}}_{H^{(j)}} \Big\rangle \right\} \\[5pt] & = \sum_{i=1}^d \alpha_i^2 \tau(H_i, W_i) + \sum_{1 \leq i \ne j \leq d} \alpha_i \alpha_j \rho_{ij} , \end{align*}

where $\tau(H_i, W_i)$ is as defined in Lemma 8 and $\rho_{ij}$ is as in (13). Combining the above and observing that

\begin{equation*} \|W_{\boldsymbol{\alpha}}\|_2^2 = \sum_{i=1}^d \alpha_i^2 \|(W_i)_{H_i}\|_2^2 + \sum_{1 \leq i \ne j \leq d} \alpha_i \alpha_j \big\langle (W_i)_{H_i}, (W_j)_{H_j} \big\rangle, \end{equation*}

the second condition in (50) follows. This completes the proof of Lemma 7.

The proof of Lemma 7 uses the following result about the limiting value of $\|W^{G_n}_{H}\|_2^2$ .

Lemma 8. For any fixed graph $H = (V(H), E(H))$ and a sequence of graphs $G_n$ converging to a graphon W,

$$\lim_{n \rightarrow \infty} \big\|W^{G_n}_{H}\big\|_2^2 = \sum_{\substack{1\leq u\neq v\leq |V(H)|\\ 1\leq u'\neq v'\leq |V(H)|}} t\left( H\bigotimes_{(a, b),(a', b')} H, W \right) \;:\!=\; \tau(H, W).$$

Moreover, for any two fixed graphs $H_1 = (V(H_1), E(H_1))$ and $H_2 = (V(H_2), E(H_2))$ and a sequence of graphs $G_n$ converging to a graphon W,

(51) \begin{align} \lim_{n \rightarrow \infty} \Big\langle W^{G_n}_{H_1}, W^{G_n}_{H_2} \Big\rangle = \sum_{\substack{1\leq u\neq v\leq |V(H_1)| \\ 1\leq u'\neq v'\leq |V(H_2)|}} t\left( H_1 \bigotimes_{(a, b),(a', b')} H_2, W \right)\!. \end{align}

Proof. Let H′ be an isomorphic copy of H. Then

\begin{align*} \Big\|W^{G_n}_{H}\Big\|_2^2 & = \int_{[0,1]^2}\left[ \sum_{1\leq a \neq b \leq |V(H)|} \mathrm{E}\left( \prod_{(i, j)\in E(H)} W^{G_n}(U_i,U_j) \;\middle|\; U_a=x,U_b=y \right) \right]^2\,\mathrm{d}x \,\mathrm{d}y \\[5pt] & = \int_{[0,1]^2}\sum_{\substack{(a, b)\in V(H)_2 \\ (a',b')\in V(H')_2}}\mathrm{E}\left( \prod_{(i, j) \in E(H)\cup E(H')} W^{G_n}(U_i,U_j) \;\middle|\; \begin{pmatrix} U_a \\[5pt] U_b\end{pmatrix} = \begin{pmatrix} U_{a'} \\[5pt] U_{b'}\end{pmatrix} = \begin{pmatrix} x \\[5pt] y\end{pmatrix} \right) \,\mathrm{d}x \,\mathrm{d}y\\[5pt] & = \sum_{\substack{1\leq a \neq b \leq |V(H)| \\ 1\leq a' \neq b' \leq |V(H)|}} t\left( H\bigotimes_{(a,b),(a',b')} H, W^{G_n} \right) \rightarrow \tau(H, W) , \end{align*}

since $G_n$ converges to W. The result in (51) can be proved similarly.

To complete the proof of Theorem 1, recall the representation in (48). Then applying Lemmas 7 and 10 shows that

\begin{align*} \frac{1}{2 \sqrt{c}\,} \sum_{a=1}^{c-1} I^{(a)}_2\left( \sum_{i=1}^d \alpha_i W^{G_n^{(i)}}_{H_i} \right) \stackrel{D} \rightarrow \sqrt{\frac{c-1}{2c}} \boldsymbol{\alpha}^\top \mathbf{Z} + \frac{1}{2 \sqrt{c}\,}\sum_{a=1}^{c-1}I_2^{(a)}(W_{\boldsymbol{\alpha}}) ,\end{align*}

where $\mathbf{Z}$ is as defined Theorem 1 and the two terms in the right-hand side above are independent. Finally, recall (from (44) and (45)) that the left-hand side above has the same limiting distribution as $\boldsymbol{\alpha}^\top \mathbf{Q}(\mathcal{H}, \mathbf{G}_n)$ . Hence, by the Cramér–Wold device the result in Theorem 1 follows.

4. Examples

In this section we illustrate our results in various examples. A few of the examples will involve random multiplexes. To this end, it is worth noting that Theorem 1 can be easily extended to random multiplexes, when the limits in (9) and (13) hold in probability, under the assumption that the multiplex and its coloring are jointly independent (see, for example, [Reference Bhattacharya, Diaconis and Mukherjee13, Lemma C.1]).

Example 4. A natural example of a random multiplex is the correlated Erdős–Rényi model, which is a 2-multiplex where the edges are dependent across the different layers. This model emerged from the study of network privacy [Reference Pedarsani and Grossglauser75] and is the basic underlying model in graph matching problems (see [Reference Mao, Wu, Xu and Yu59, Reference Mao, Wu, Xu and Yu60] and the references therein). Specifically, the correlated Erdős–Rényi model $\mathbf{G}(n, p, q, \rho) = (G_n^{(1)}, G_n^{(2)})$ is a 2-multiplex with a common vertex set [n], where independently for every $1 \leq i < j \leq n$ , we have

\begin{align*} \mathrm{P}\big( (i, j) \in E\big(G_n^{(1)}\big)\big) = p, \quad \mathrm{P}\big( (i, j) \in E\big(G_n^{(2)}\big)\big) = q, \end{align*}

and

\begin{align*} \mathrm{P}\big( (i, j) \in E\big(G_n^{(1)}\big) \cap E\big(G_n^{(2)}\big)\big) = \rho + p q \;:\!=\; p_{1, 2}, \end{align*}

for $p, q \in (0, 1)$ and $p_{1,2} \in [\max\{p+q-1,0\}, \min\{p,q\}]$ . In this case, $(G_n^{(1)}, G_n^{(2)})$ converges in the multiplex cut-metric to $(W_1, W_2)$ , where $W_1 \equiv p$ and $W_2 \equiv q$ . Therefore, for any two graphs $H_1$ and $H_2$ ,

(52) \begin{align} ((W_1)_{H_1}, (W_2)_{H_2})=\left( |V(H_1)| (|V(H_1)| -1) p^{|E(H_1)|},|V(H_2)| (|V(H_2)| -1 ) q^{|E(H_2)|}\right)\!. \end{align}

To apply Theorem 1, it remains to find the limit

\begin{align*} \lim_{n \rightarrow \infty} \Big\langle W_{H_1}^{G_n^{(1)}}, W_{H_2}^{G_n^{(2)}} \Big\rangle \end{align*}

(recall (14)) and to compute $\Sigma$ .

Note that, given $\mathbf{G}_n = (G_n^{(1)}, G_n^{(2)})$ ,

\begin{align*} \Big\langle W_{H_1}^{G_n^{(1)}}, W_{H_2}^{G_n^{(2)}} \Big\rangle & = \int_{[0, 1]^2} W_{H_1}^{G_n^{(1)}} (x, y) W_{H_2}^{G_n^{(2)}} (x, y) \,\mathrm{d} x \,\mathrm{d} y \nonumber \\[5pt] & = \sum_{\substack{(a, b)\in V(H_1)_2 \\ (a',b')\in V(H_2)_2}} B_{H_1, H_2}^{G_n^{(1)} G_n^{(2)}} ((a, b), (a', b')) , \end{align*}

where

\begin{align*} & B_{H_1, H_2}^{G_n^{(1)} G_n^{(2)}} ((a, b), (a', b')) \nonumber \\[5pt] & \;:\!=\; \int_{[0, 1]^2} \Bigg\{ \mathrm{E}\left( \prod_{(i, j)\in E(H_1)} W^{G_n^{(1)}}(U_i, U_j) \;\middle|\; \begin{pmatrix} U_a \\ U_b\end{pmatrix} = \begin{pmatrix} x \\ y\end{pmatrix} \right) \nonumber \\[5pt] & \hspace{1.5in} \mathrm{E}\left( \prod_{(i, j)\in E(H_2)} W^{G_n^{(2)}}(U_i,U_j) \;\middle|\; \begin{pmatrix} U_{a'} \\ U_{b'}\end{pmatrix} = \begin{pmatrix} x \\ y\end{pmatrix} \right) \Bigg\} \mathrm{d}x \mathrm{d}y \nonumber \\[5pt] & \stackrel{L^2} \rightarrow \begin{cases} p_{1,2} \cdot p^{|E(H_1)|-1}q^{|E(H_2)|-1} & \textit{if } (a,b)\in E(H_1) \textit{ and } (a',b')\in E(H_2) , \\[5pt] p^{|E(H_1)|}q^{|E(H_2)|} & \textit{otherwise}. \end{cases} \end{align*}

Therefore, from (52),

(53) \begin{align} \Big\langle W_{H_1}^{G_n^{(1)}}, W_{H_2}^{G_n^{(2)}} \Big\rangle - \langle(W_1)_{H_1},(W_2)_{H_2}\rangle \stackrel{L^2} \rightarrow |E(H_1)||E(H_2)| \rho \cdot p^{|E(H_1)|-1}q^{|E(H_2)|-1} . \end{align}

This implies that

(54) \begin{align} \hspace{-0.125in} \Sigma = \begin{pmatrix} |E(H_1)||E(H_2)| p^{|E(H_1)|+ E(H_2)|-1}(1-p)\;\;\;\;\; & |E(H_1)||E(H_2)| \rho \cdot p^{|E(H_1)|-1}q^{|E(H_2)|-1} \\[5pt] |E(H_1)||E(H_2)| \rho \cdot p^{|E(H_1)|-1}q^{|E(H_2)|-1}\;\;\;\; & |E(H_1)||E(H_2)| q^{|E(H_1)|+E(H_2)|-1} (1-q)\end{pmatrix} . \end{align}

Combining (53) and (54) and applying Theorem 1 gives

\begin{align*} \begin{pmatrix} \Gamma(H_1,G_n^{(1)}) \\[5pt] \Gamma(H_2,G_n^{(2)}) \end{pmatrix} \xrightarrow{D} \sqrt{\frac{c-1}{2c}} \begin{pmatrix} Z_1 \\[5pt] Z_2 \end{pmatrix} +\frac{1}{ 2 \sqrt{c}\,} \begin{pmatrix} |V(H_1)| (|V(H_1)| -1) p^{|E(H_1)|} \\[5pt] |V(H_2)| (|V(H_2)| -1) q^{|E(H_1)|} \end{pmatrix} \xi , \end{align*}

with $\xi \sim \chi^2_{c-1}-(c-1)$ which is independent of $(Z_1,Z_2) \sim N_2(\mathbf 0, \Sigma)$ .

Next, we construct an example where the Gaussian component of the limiting distribution in (14) has a degenerate covariance matrix.

Example 5. Suppose $G_n^{(1)} \sim G(n, p)$ , where $p \in (0, 1)$ , and consider the multiplex $\mathbf{G}_n = (G_n^{(1)}, G_n^{(2)})$ , where $G_n^{(2)}$ is the complement graph of $G_n^{(1)}$ . Then, by plugging in $H_1=H_2=K_3$ , $c=2$ , $q=1-p$ , and $p_{1,2}=0$ into Example 4 gives

\begin{align*} \begin{pmatrix} \Gamma(K_3,G_n^{(1)}) \\[5pt] \Gamma(K_3, G_n^{(2)}) \end{pmatrix} \xrightarrow{D} 3\sqrt{p(1-p)}\begin{pmatrix} p^2Z \\[5pt] -(1-p)^2Z \end{pmatrix} +3\sqrt{2}\begin{pmatrix} \displaystyle p^3 \\[5pt] \displaystyle (1-p)^3 \end{pmatrix} \xi , \end{align*}

with $\xi\sim \chi^2_1-1$ which is independent of $Z \sim N(0,1)$ .

The next example shows that marginal convergence (in the cut-metric) of the graphs in the different layers of a multiplex $\mathbf{G}_n$ and the convergence of the pairwise overlaps (13) are not enough for the convergence of the joint distribution of $\Gamma(\mathcal{H}, \mathbf{G}_n)$ . This illustrates the need to assume that the graphs in the different layers converge in the multiplex cut-metric (as in (9)) for the limiting distribution of $\Gamma(\mathcal{H}, \mathbf{G}_n)$ to exist. To this end, for two graphs $G_1 = (V(G_1), E(G_1))$ and $G_2 = (V(G_2), E(G_2))$ , denote $G_1 \bigcup G_2 = (V(G_1) \bigcup V(G_2), E(G_1) \bigcup E(G_2))$ .

Figure 2.

The graphs $G_n^{(1)}$ , $G_n^{(2)}$ , and $G_n^{(3)}$ in Example 6.

Example 6. Let $A_1, A_2, A_3, A_4$ be four disjoint sets of size n. Denote by $B_{n}^{(s, s+1)}$ the complete bipartite graph between the sets $A_s$ and $A_{s+1}$ , for $1 \leq s \leq 3$ (see Figure 2). Define

\begin{equation*} G_n^{(1)} = \bigcup_{s=1}^3 B_n^{(s, s+1)}, \quad G_n^{(2)} = B_n^{(1, 2)}, \quad \text{and} \quad G_n^{(3)} = B_n^{(2, 3)}. \end{equation*}

(Note that, in other words, $G_n$ is the n-blow-up of a path with four vertices; see [Reference Lovász52, Section 3.3].) Now consider the following two sequences of multiplexes:

\begin{equation*} \mathbf{G}_n = \big(G_n^{(1)}, G_n^{(2)}\big) \quad \text{and} \quad \tilde{\mathbf{G}}_n = \big(G_n^{(1)}, G_n^{(3)}\big). \end{equation*}

Note that the graph $G_n^{(1)}$ converges to the graphon $W_{1234}$ in Figure 3(a) and the graphs $G_n^{(2)}$ and $G_n^{(3)}$ converge to the graphon $W_{23}$ in Figure 3(b). Hence, marginally the graphs in the two layers of $\mathbf{G}_n$ and the graphs in the two layers of $\tilde{\mathbf{G}}_n$ converge to the same limits. Moreover,

\begin{align*} \lim_{n \rightarrow \infty} \frac{2 |E\big(G_n^{(1)}\big) \cap E\big(G_n^{(2)}\big)|}{n^2} = \lim_{n \rightarrow \infty} \frac{2 |E\big(G_n^{(1)}\big) \cap E\big(G_n^{(3)}\big)|}{n^2} = \frac{1}{8}, \end{align*}

that is, (15) converges to the same limit for both $\mathbf{G}_n$ and $\tilde{\mathbf{G}}_n$ . Hence, the premises of Corollary 1 hold for both $\mathbf{G}_n$ and $\tilde{\mathbf{G}}_n$ . In particular, with $c=2$ , we get

(55) \begin{align} \begin{pmatrix} \Gamma\left(K_2,G_n^{(1)}\right) \\[5pt] \Gamma\left(K_2,G_n^{(2)}\right) \end{pmatrix} \xrightarrow{D} \begin{pmatrix}\displaystyle\int_{[0,1]^2}W_{1234}(x, y)\,\mathrm{d}B_x\,\mathrm{d}B_y \\[5pt] \displaystyle\int_{[0,1]^2}W_{23}(x, y)\,\mathrm{d}B_x\,\mathrm{d}B_y\end{pmatrix} & \stackrel{D}{=} \frac{1}{4}\begin{pmatrix}\displaystyle Z_1Z_2+Z_2Z_3+Z_3Z_4 \\[5pt] Z_1Z_2 \end{pmatrix} \nonumber \\[5pt] & \;=\!:\; \begin{pmatrix} Y \\[5pt] Y'\end{pmatrix} \end{align}

and

(56) \begin{align} \begin{pmatrix} \Gamma\big(K_2,G_n^{(1)}\big) \\[5pt] \Gamma\big(K_2,G_n^{(3)}\big) \end{pmatrix} \xrightarrow{D} \begin{pmatrix}\displaystyle\int_{[0,1]^2}W_{1234}(x, y)\,\mathrm{d}B_x\,\mathrm{d}B_y \\[5pt] \displaystyle\int_{[0,1]^2}W_{23}(x, y)\,\mathrm{d}B_x\,\mathrm{d}B_y\end{pmatrix} & \stackrel{D}{=} \frac{1}{4}\begin{pmatrix}\displaystyle Z_1Z_2+Z_2Z_3+Z_3Z_4 \\[5pt] Z_2Z_3 \end{pmatrix} \nonumber \\[5pt] & \;=\!:\; \begin{pmatrix} Y \\[5pt] Y'' \end{pmatrix} , \end{align}

where $Z_1, Z_2, Z_3, Z_4$ are i.i.d. N(0,1) and $\{B_t\}_{t \in [0, 1]}$ is the standard Brownian motion on [0, 1]. Note that the limiting distributions in (55) and (56) are different. In particular, $\mathrm{E}(Y-Y')^4=\frac{36}{4^4}$ which is different from $\mathrm{E}(Y-Y'')^4=\frac{24}{4^4}$ . The reason for this is that in this case $\lim_{n\rightarrow\infty}\delta_{\square}(\mathbf{W}^{\mathbf{G}_n},\mathbf{W}^{\tilde{\mathbf{G}}_n})\neq 0$ .

Figure 3.

The graphons $W_{1234}$ and $W_{23}$ in Example 6.

Finally, we consider the correlated stochastic block model, which generalizes both Examples 5 and 6.

Example 7. The SBM is one of the most widely studied models in network analysis [Reference Holland, Laskey and Leinhardt41, Reference Kolaczyk and Csárdi48, Reference Olhede and Wolfe71]. This is a random graph $G_n=([n],E(G_n))$ , where the vertex set [n] is partitioned into $K\geq 1$ blocks $C_1, C_2, \ldots, C_K$ (which are referred to as communities) and the edges are obtained as follows: independently for $1 \leq u < v \leq n$ ,

\begin{equation*} \mathrm{P}((u, v)\in E(G_n)) = p_{ab} , \quad \text{if } u \in C_a \text{ and } v \in C_b , \end{equation*}

for $a, b \in [K]$ . Here, $((p_{ab}))_{1\leq a, b \leq K}$ is a $K \times K$ is a matrix of parameters encoding the within/between block connection probabilities. The correlated SBM (on 2 layers) is a random multiplex $(G_n^{(1)},G_n^{(2)})$ where the common vertex set [n] is partitioned into $K\geq 1$ blocks $C_1, C_2, \ldots, C_K$ as before and the edges are obtained as follows: independently for $1 \leq u < v \leq n$ ,

\begin{equation*} \mathrm{P}\big((u, v)\in E\big(G_n^{(1)}\big)\big) = p_{ab}^{(1)} , \quad \mathrm{P}\big((u, v)\in E\big(G_n^{(2)}\big)\big) = p_{ab}^{(2)} , \end{equation*}

and

\begin{equation*} \mathrm{P}\big((u, v)\in E\big(G_n^{(1)}\big) \cap E\big(G_n^{(2)}\big)\big) = p_{ab}^{(12)}, \end{equation*}

if $u \in C_a \text{ and } v \in C_b$ , for $a, b \in [K]$ . Here, $((p_{ab}^{(1)}))_{1\leq a, b \leq K}$ , $((p_{ab}^{(2)}))_{1\leq a, b \leq K}$ , and $((p_{ab}^{(12)}))_{1\leq a, b \leq K}$ are $K \times K$ matrices of parameters encoding the connection probabilities within/between blocks in layer 1, layer 2, and in both the layers, respectively. The correlated SBM has recently emerged as an important prototype for modeling multilayer social network data and in graph matching problems (see [Reference Barbillon, Donnet, Lazega and Bar-Hen3, Reference Chai and Rácz23, Reference Chandna, Janson and Olhede24, Reference Gaudio, Racz and Sridhar36, Reference Lyzinski55, Reference Lyzinski, Sussman, Fishkind, Pao, Chen, Vogelstein, Park and Priebe56, Reference Onaran, Garg and Erkip72, Reference Pamfil, Howison and Porter73, Reference Racz and Sridhar76, Reference Rácz and Sridhar77, Reference Zhang, Wang and Wang87] and references therein). Suppose that $\frac{|V_a|}{n} \rightarrow \lambda_a \in [0, 1]$ , for $a \in [K]$ , and $\{I_1, I_2, \ldots, I_K\}$ is a partition of [0, 1] into intervals of length $\lambda_1, \lambda_2, \ldots, \lambda_K$ , respectively. Then the multiplex $(G_n^{(1)}, G_n^{(2)}, G_n^{(1)}\cap G_n^{(2)})$ converges, in the appropriate multiplex cut-distance, to the 3-graphon $(W_{1},W_{2},W_{12}),$ where

$$W_{1}(x,y)= p_{ab}^{(1)}, \quad W_{2}(x,y)= p_{ab}^{(2)}, \quad W_{12}(x,y)= p_{ab}^{(12)},$$

for all $x\in I_a$ and $y\in I_b$ , and $a, b \in [K]$ . Hence, fixing $c=2$ , Corollary 1 implies that

\begin{equation*} \frac{1}{n}\left[ \begin{pmatrix} T\big(K_2,G_{n}^{(1)}\big) \\[5pt] T\big(K_2,G_{n}^{(2)}\big) \end{pmatrix} - \frac{1}{c}\begin{pmatrix} |E\big(G_{n}^{(1)}\big)| \\[5pt] |E\big(G_{n}^{(2)}\big)| \end{pmatrix} \right] \xrightarrow{D} \frac{1}{2\sqrt{2}\,}\mathbf{L} + \frac{1}{4}\mathbf{Q} , \end{equation*}

where $\mathbf{L}=(L^{(1)},L^{(2)})$ and $\mathbf{Q}=(Q^{(1)},Q^{(2)})$ are independent. Here,

\begin{align*} Q^{(1)} &= \sum_{{a, b \in [K]}}p_{ab}\sqrt{\lambda_a \lambda_b}\big( Z_a^{(1)}Z_b^{(1)} - \mathrm{E} Z_a^{(1)}Z_b^{(1)}\big),\\[5pt] Q^{(2)} &= \sum_{{a, b \in [K]}}p_{ab}\sqrt{\lambda_a \lambda_b}\big( Z_a^{(2)}Z_b^{(2)} - \mathrm{E} Z_a^{(2)}Z_b^{(2)}\big) , \end{align*}

where $\{Z_a^{(1)}\}_{a \in [K]}$ and $\{Z_a^{(2)}\}_{a \in [K]}$ are independent collections of i.i.d. N(0, 1) random variables; and

\begin{align*} L^{(1)} = \sum_{{a, b \in [K]}}\lambda_a \lambda_b\eta_{ab}^{(1)}, \quad L^{(2)} = \sum_{{a, b \in [K]}}\lambda_a \lambda_b\eta_{ab}^{(2)} , \end{align*}

where $\{(\eta_{ab}^{(1)},\eta_{ab}^{(2)})\}_{a, b \in [K]}$ is a collection of independent $N_2(0,\Sigma_{ab})$ variables with

\begin{equation*} \Sigma_{ab} = \begin{pmatrix} p_{ab}^{(1)}\big(1-p_{ab}^{(1)}\big) & p_{ab}^{(12)} - p_{ab}^{(1)}p_{ab}^{(2)} \\[5pt] p_{ab}^{(12)} - p_{ab}^{(1)}p_{ab}^{(2)} & p_{ab}^{(2)}\big(1-p_{ab}^{(2)}\big) \end{pmatrix}, \end{equation*}

for all ${a, b \in [K]}$ .

5. Future directions

In this paper we have derived the joint distribution of monochromatic subgraphs in multiplex networks (converging in the cut-metric) colored uniformly at random with c colors. A possible future direction would be to consider nonuniform colorings. The authors expect the techniques developed in this paper to be still relevant in the nonuniform setting, although the nature of the limiting distribution may differ. Additionally, it may be relevant to study settings in which the coloring in each layer differs, yet exhibits some correlation structure across layers. Another question is to derive convergence rates for the asymptotic results presented in this paper. A key challenge is that the limiting distribution involves both Gaussian and non-Gaussian components. While techniques for Gaussian convergence are well developed, results for non-Gaussian distributions are limited to specific cases. Understanding how convergence rates depend on the structure of the multiplex, particularly inter-layer interactions, is an interesting future direction.