2.1 Thresholds for submultiplex containment

Thresholds for the emergence of fixed subgraphs in the random graph $G(n, p)$ were among the first problems studied by Erdős and Rényi in their fundamental paper [Reference Erdős and Rényi13]. Bollobás [Reference Bollobás7] resolved this problem in its full generality a few years later, and this is now a textbook result in random graph theory (see, e.g., [Reference Janson, Łuczak and Ruciński18, Chapter 3]). Our first aim in this article is to derive the analogous result for submultiplexes in the correlated Erdős–Rényi multiplex model. We begin by formalizing the notion of containment in a multiplex network. For two multiplexes $\boldsymbol F= (V(\boldsymbol F), F^{(1)}, F^{(2)}) $ and $\boldsymbol G = (V(\boldsymbol G), G^{(1)}, G^{(2)}) $ , we write $\boldsymbol F\subseteq \boldsymbol G$ and say that $\boldsymbol F$ is a submultiplex of $\boldsymbol G$ if $V(\boldsymbol F)\subseteq V(\boldsymbol G)$ and $E(F^{(i)})\subseteq E(G^{(i)})$ , for $i \in \{1, 2\}$ . Given a fixed multiplex $\boldsymbol H = (V(\boldsymbol {H}), H^{(1)}, H^{(2)})$ and an injective map $\phi : V(\boldsymbol H) \rightarrow [n]$ , denote by $\boldsymbol H_{\phi }$ the image multiplex with vertex set $\phi (V(\boldsymbol {H}))$ and edge sets $\phi (E(H^{(i)})) = \{(\phi (u), \phi (v)): (u, v) \in E(H^{(i)}) \}$ , for $i \in \{1, 2\}$ . Then the number of (unlabeled) copies of $\boldsymbol H$ in $\boldsymbol G_n = ([n], G_n^{(1)}, G_n^{(2)}) \sim G(n, p_1, p_2, p_{12})$ , generated from the correlated Erdős–Rényi model as in Definition 1.1, is defined as

(2.1) $$ \begin{align} X(\boldsymbol H,\boldsymbol G_n) = \sum_{\overline{\boldsymbol H}'\in\mathcal C_n(\boldsymbol H)} \boldsymbol 1 \{\overline{\boldsymbol H}'\subseteq\boldsymbol G_n \} , \end{align} $$

where $\mathcal C_n(\boldsymbol H) := \left \{ \boldsymbol H_{\phi }: \phi : V(\boldsymbol H) \rightarrow [n] \text { is injective} \right \}$ . The following result gives the threshold for the emergence of $\boldsymbol {H}$ in $G(n, p_1, p_2, p_{12})$ . Throughout, we are going to assume $p_1, p_2$ (and as a result, $p_{12}$ ) are bounded away from 1.

Theorem 2.1 Suppose $\boldsymbol H = (V(\boldsymbol {H}), H^{(1)}, H^{(2)})$ is a fixed multiplex with at least one edge (i.e., $|E(\boldsymbol {H})| \geq 1$ ). Then for $X(\boldsymbol {H}, \boldsymbol G_n)$ as defined above, the following holds:

(2.2) $$ \begin{align} X(\boldsymbol{H}, \boldsymbol G_n) \stackrel{P} \rightarrow \begin{cases} 0, & \Phi_{\boldsymbol{H}} \ll 1 , \\ \infty, & \Phi_{\boldsymbol{H}} \gg 1 , \end{cases} \end{align} $$

where

(2.3) $$ \begin{align} \Phi_{\boldsymbol{H}} & = \Phi_{\boldsymbol{H}} (n, p_1, p_2, p_{12}) \nonumber \\ & :=\min_{\substack{\boldsymbol{F} = (V(\boldsymbol{F}), F^{(1)}, F^{(2)}) \subseteq \boldsymbol{H} \\ |E(\boldsymbol{F})| \geq 1 }} n^{|V(\boldsymbol{F})|}p_1^{|E(F^{(1)})\setminus E(F^{(2)})|} p_2^{|E(F^{(2)})\setminus E(F^{(1)}) |} p_{12}^{|E(F^{(1)})\cap E(F^{(2)}) |}. \end{align} $$

The proof of Theorem 2.1 relies on standard applications of the first and second moment methods (see Section 3). From the proof, it will be evident that

$$ \begin{align*}\Phi_{\boldsymbol{H}} \asymp_{\boldsymbol H} \min\{ \mathbb{E} [X(\boldsymbol{F}, \boldsymbol G_n) ] : \boldsymbol{F} \subseteq \boldsymbol{H}, |E(\boldsymbol{F})| \geq 1 \}.\end{align*} $$

In other words, the threshold for the emergence of a fixed submultiplex is determined by the rarest (in terms of expected number of copies) submultiplex of $\boldsymbol {H}$ . The same phenomenon determines the threshold for the appearance of any fixed subgraph in an Erdős–Rényi random graph (see [Reference Janson, Łuczak and Ruciński18, Theorem 3.4]).

Remark 2.2 One can recover the threshold for subgraphs in Erdős–Rényi random graphs by considering one of the layers in $\boldsymbol {H}$ to be empty. Specifically, if $H^{(2)}$ is the empty graph and $H^{(1)}= H = (V(H), E(H))$ is a fixed simple graph, then (2.3) simplifies to

$$ \begin{align*}\Phi_{H} =\min_{\substack{F \subseteq H, |E(F)| \geq 1 }} n^{|V(F)|}p_1^{|E(F)|} .\end{align*} $$

In this case, the condition $\Phi _{H} \gg 1$ is equivalent to $ n p_1^{m_H} \gg 1 $ , where

(2.4) $$ \begin{align} m_H:=\max_{F\subseteq H,\,|V(F)|>0}\frac{|E(F)|}{|V(F)|}. \end{align} $$

This matches the threshold for the emergence of H in the Erdős–Rényi graph $G(n, p_1)$ (see [Reference Janson, Łuczak and Ruciński18, Theorem 3.4]). If the maximum in (2.4) is attained by H itself, that is, $m(H)=\frac {|E(H)|}{|V(H)|}$ , then H is said to be a balanced graph. Otherwise, H is said to be an unbalanced graph. Moreover, if the maximum in (2.4) is uniquely attained at H, then H is called a strictly balanced graph.

To better visualize the phase transition in Theorem 2.1, it is instructive to parametrize the probabilities as

(2.5) $$ \begin{align} p_1 = n^{-\theta_1}, \quad p_2 = n^{-\theta_2}, \quad \text{ and } \quad p_{12} = n^{-\theta_{12}}. \end{align} $$

The conditions in (1.1) impose the following restrictions on the values of $\theta _1, \theta _2, \theta _{12}$ :

$$ \begin{align*}\Theta := \{ \boldsymbol \theta = (\theta_1, \theta_2, \theta_{12} ) : \theta_1, \theta_2, \theta_{12}> 0 \text{ and } \theta_{12} \geq \max\{\theta_1, \theta_2\}\}.\end{align*} $$

Then (2.2) implies

(2.6) $$ \begin{align} X(\boldsymbol{H}, \boldsymbol G_n) \stackrel{P} \rightarrow \begin{cases} 0, & \Delta_{\boldsymbol H} < 0, \\ \infty, & \Delta_{\boldsymbol H}> 0, \end{cases} \end{align} $$

where

(2.7) $$ \begin{align} \Delta_{\boldsymbol H} & = \Delta_{\boldsymbol{H}}(\boldsymbol \theta) \\ & = \min_{ \substack{\boldsymbol{F} \subseteq \boldsymbol{H} \\ |E(\boldsymbol{F})| \geq 1 } } \bigg \{ |V(\boldsymbol{F})|- \theta_1 |E(F^{(1)})\setminus E(F^{(2)})|- \theta_2 |E(F^{(2)})\setminus E(F^{(1)})| \nonumber \\ & \hspace{1.25in} - \theta_{12} |E(F^{(1)})\cap E(F^{(2)})| \bigg \} , \nonumber \end{align} $$

with the minimum taken over all submultiplexes $\boldsymbol {F} = (V(\boldsymbol {F}), F^{(1)}, F^{(2)}) \subseteq \boldsymbol {H}$ . Note that condition $\Delta _{\boldsymbol H}> 0$ is equivalent to the condition for all $\boldsymbol {F} \subseteq \boldsymbol {H}$ with $|E(\boldsymbol F)| \geq 1$ ,

(2.8) $$ \begin{align} \ell_{\boldsymbol F}(\boldsymbol \theta) & := |V(\boldsymbol{F})|- \theta_1 |E(F^{(1)})\setminus E(F^{(2)})|- \theta_2 |E(F^{(2)})\setminus E(F^{(1)})| \nonumber \\ & \hspace{0.75in} - \theta_{12} |E(F^{(1)})\cap E(F^{(2)})|> 0. \end{align} $$

This defines an open halfspace in $\mathbb R^3$ that contains the origin. Hence, the parameter values for which the count of $\boldsymbol {H}$ in $\boldsymbol G_n$ diverges, are given by (recall (2.6)):

$$ \begin{align*}\partial_{\boldsymbol H}^+ := \{(\theta_1, \theta_2, \theta_{12}) \in \Theta: \Delta_{\boldsymbol H}> 0\}\end{align*} $$

is formed by the intersection of finitely many halfspaces. Hence, it is a (possibly unbounded) convex polyhedral region contained in the open positive orthant of $\mathbb {R}^3$ . We will refer to this region as the satisfiability region for $\boldsymbol {H}$ . Note that the satisfiability region $\partial _{\boldsymbol H}^+ $ is determined by two types of linear constraints:

• • Constraints of the form (2.8) which are open halfspaces in $\mathbb {R}^3$ . These will be referred to as the main constraints.

• • The feasibility constraint $\theta _{12} \geq \max \{\theta _1, \theta _2\}$ , which is the intersection of the closed halfspaces $\theta _{12} \geq \theta _1$ and $\theta _{12} \geq \theta _2$ . (The $\theta _1, \theta _2, \theta _{12}> 0 $ are also feasibility constraints, which are enforced by considering the positive orthant of $\mathbb {R}^3$ .)

Hence, a boundary piece of $\partial _{\boldsymbol H}^+$ may or may not be included in the region, depending on whether it arises from a strict main constraint or a non-strict feasibility constraint. The unsatisfiability region

$$ \begin{align*}\partial_{\boldsymbol H}^- := \{(\theta_1, \theta_2, \theta_{12}) \in \Theta: \Delta_{\boldsymbol H} < 0\}\end{align*} $$

consists of the parameter values for which there are asymptotically no copies of $\boldsymbol {H}$ in $\boldsymbol G_n$ . These two regions are separated by the threshold surface

$$ \begin{align*}\partial_{\boldsymbol H} := \{(\theta_1, \theta_2, \theta_{12}) \in \Theta: \Delta_{\boldsymbol H} = 0\} ,\end{align*} $$

which forms a polyhedral surface in $\mathbb R^3$ . The submultiplexes of $\boldsymbol H$ which determine the condition $\Delta _{\boldsymbol H} = 0$ will play an important role in our analysis. This is formalized in the following definition.

To illustrate the ideas described above, we consider the following examples.

Example 2.3 Consider the edge-triangle multiplex as shown in Figure 2(a):

(2.9) $$ \begin{align} \boldsymbol{\mathcal{R}} = (\{1, 2, 3\}, \mathcal{R}^{(1)}, \mathcal{R}^{(2)} ) , \end{align} $$

with $E(\mathcal {R}^{(1)})= \{(1, 2), (2, 3), (1, 3)\}$ , which corresponds to the triangle in layer 1 with edges colored in blue, and $E(\mathcal {R}^{(2)}) = \{(2, 3)\}$ , which corresponds to the edge in layer 2 colored in red. In this case, the main constraints determining the boundary of the region $\partial _{\boldsymbol {\mathcal {R}}}^{+}$ are:

• • $2 \theta _1 + \theta _{12} < 3 $ : This corresponds to taking $\boldsymbol F = \boldsymbol {\mathcal {R}}$ in (2.8).

• • $\theta _{12} < 2$ : This corresponds to taking $\boldsymbol F = \boldsymbol {\mathcal {O}} := (\{2, 3\}, \mathcal {O}^{(1)}, \mathcal {O}^{(2)})$ , where $\mathcal {O}^{(1)}$ and $\mathcal {O}^{(2)}$ are both the single edge $(2,3)$ .

  Figure 2

  (a) The edge-triangle multiplex $\boldsymbol {\mathcal {R}}$ defined in (2.9), (b) the full phase diagram in 3D, and (c) the 2D phase diagram assuming $\theta _1=\theta _2= \theta $ .

  

  Figure 2 Long description

  The figure consists of three panels labeled a, b, and c.

  * Panel a is a network diagram with three nodes labeled 1, 2, and 3 arranged in a triangle. Blue straight lines connect all three nodes. A red curved line also connects nodes 2 and 3, representing a multiplex edge.

  * Panel b is a three-dimensional plot with axes labeled theta sub 1, theta sub 2, and theta sub 1 2. It shows a complex geometric solid with red, blue, and dark gray faces representing a phase space volume.

  * Panel c is a two-dimensional line graph. The x-axis is labeled theta and the y-axis is labeled theta sub 1 2. A blue-shaded polygonal region is bounded by points O at (0,0), Q sub 1 at (1,1), Q sub 2 at (0.5,2), and Q sub 3 at (0,2). The region inside the polygon is labeled many copies of R. The area outside the polygon, shaded in light gray, is labeled no copies of R. A solid red line connects Q sub 3 to Q sub 2 and Q sub 2 to Q sub 1. Dashed blue and black lines form the other boundaries of the blue region.

In addition one has the feasibility constraint $\max \{\theta _1, \theta _2\} \leq \theta _{12}$ . These together generate the three-dimensional satisfiability region shown in Figure 2(b): The red plane corresponds to the equation $2 \theta _1 + \theta _{12} =3 $ , the blue plane corresponds to $\theta _{12} = 2$ , and the black planes correspond to $\max \{\theta _1, \theta _2\} = \theta _{12}$ . In Figure 2(c), we show the two-dimensional slice of this region, where $\theta _1=\theta _2= \theta $ (this corresponds to the case where the graphs in the marginal layers have the same distribution). Then, $\partial _{\boldsymbol {\mathcal {R}}}^+$ is the two-dimensional region:

$$ \begin{align*}\partial_{\boldsymbol{\mathcal{R}}}^+ := \{ (\theta, \theta_{12}) : \theta, \theta_{12}> 0 , \theta \leq \theta_{12}, 2 \theta + \theta_{12} < 3, \theta_{12} < 2 \} .\end{align*} $$

This is the blue polygonal region together with the blue line segment $(O, Q_1)$ (excluding the origin O and the point $Q_1$ ) shown in Figure 2(c). The threshold curve $\partial _{\boldsymbol {\mathcal {R}}}$ is the red polyline segment $[Q_1, Q_2, Q_3)$ (including the points $Q_1$ and $Q_2$ and excluding the point $Q_3$ ), and the unsatisfiability region $\partial _{\boldsymbol {\mathcal {R}}}^{-}$ is shown in gray in Figure 2(c). Note that for all points $\boldsymbol \theta = (\theta , \theta _{12})$ on the open segment $(Q_1, Q_2)$ , $\boldsymbol {\mathcal {R}}$ is the unique $\boldsymbol \theta $ -extremal multiplex. On the other hand, for all points on the open segment $(Q_2, Q_3)$ , the multiplex $\boldsymbol {\mathcal {O}}$ defined above is the unique $\boldsymbol \theta $ -extremal multiplex. Also, at the point $Q_2$ , both $\boldsymbol {\mathcal {R}}$ and $\boldsymbol {\mathcal {O}}$ are $\boldsymbol \theta $ -extremal. Furthermore, at the point $Q_1$ , there are three $\boldsymbol \theta $ -extremal multiplexes: the original multiplex $\boldsymbol {\mathcal {R}}$ , the graph $R^{(1)}$ (which is the blue-colored triangle in layer 1), and the cross layer triangle on the vertices $\{1,2, 3\}$ formed by the blue edges $\{(1, 2), (1, 3)\}$ in layer 1 and the red edge $(2, 3)$ in layer 2.

Example 2.4 Consider the multiplex shown in Figure 3(a):

(2.10) $$ \begin{align} \boldsymbol{\mathcal{P}} = (\{1, 2, 3, 4, 5\}, \mathcal{P}^{(1)}, \mathcal{P}^{(2)} ) , \end{align} $$

where $E(\mathcal {P}^{(1)}) = \{(1, 2), (2, 3), (2, 5), (3, 4), (4, 5)\}$ , which is the graph in layer 1 with edges colored in blue, and $E(\mathcal {P}^{(2)}) = \{(2, 3), (1, 3) \}$ , which is the graph in layer 2 with edges colored in red.

Figure 3

(a) The multiplex $\boldsymbol {\mathcal {P}}$ defined in (2.10), (b) the full phase diagram in 3D, and (c) the 2D phase diagram assuming $\theta _1=\theta _2= \theta $ .

Figure 3 Long description

Panel a is a network graph with five numbered nodes. Node 1 is at the top, connected to nodes 2 and 3. Node 2 is connected to nodes 3 and 5. Node 3 is connected to node 4. Node 5 is connected to node 4. Edges are colored blue and red. Panel b is a 3D plot with axes theta sub 1, theta sub 2, and theta sub 1 2. It displays a complex 3D polytope with facets colored in green, red, blue, purple, and black. Panel c is a 2D graph with theta on the x-axis and theta sub 1 2 on the y-axis. A blue shaded region is bounded by points O at 0,0, Q sub 1, Q sub 2, Q sub 3, and Q sub 4. The blue region is labeled many copies of P. A gray shaded region to the right is labeled no copies of P. The boundary between the regions is marked with red line segments connecting the Q points.

The satisfiability region for this multiplex is shown in Figure 3(b), and the two-dimensional slice, where $\theta _1=\theta _2= \theta $ is shown in Figure 3(c). In this case, the satisfiability region $\partial _{\boldsymbol {\mathcal {P}}}^+$ is the blue polygonal region together with the blue line segment $(O, Q_1)$ (excluding the origin O and the point $Q_1$ ) as shown in Figure 3(c). The boundary curve $\partial _{\boldsymbol {\mathcal {P}}}$ is the red polyline segment $[Q_1, Q_2, Q_3, Q_4)$ (including the points $Q_1$ , $Q_2$ , and $Q_3$ and excluding the point $Q_4$ ), and $\partial _{\boldsymbol {\mathcal {P}}}^{-}$ is the gray region in Figure 3(c). In this case, the $\boldsymbol \theta $ -extremal multiplexes on the boundary are:

• • on the open line segment $(Q_1,Q_2)$ , $\boldsymbol {\mathcal {P}}$ is uniquely $\boldsymbol \theta $ -extremal;

• • on $(Q_2,Q_3)$ , the submultiplex induced on the vertices $\{1, 2, 3\}$ is uniquely $\boldsymbol \theta $ -extremal;

• • on $(Q_3,Q_4)$ , the submultiplex induced on the vertices $\{2, 3\}$ (which is isomorphic to the multiplex $\boldsymbol {\mathcal {O}}$ defined in Example 2.3) is uniquely $\boldsymbol \theta $ -extremal.

Moreover, at the point $Q_2$ , both $\boldsymbol {\mathcal {P}}$ and the submultiplex induced on the vertices $\{1, 2, 3\}$ are $\boldsymbol \theta $ -extremal. Similarly, at $Q_3$ , both the submultiplexes induced on the vertices $\{1, 2, 3\}$ and $\{2,3\}$ are $\boldsymbol \theta $ -extremal. Furthermore, at $Q_1$ , there are three distinct $\boldsymbol \theta $ -extremal submultiplexes: the original multiplex $\boldsymbol {\mathcal {P}}$ and two non-induced submultiplexes $\tilde {\boldsymbol {\mathcal {P}}}$ and $\boldsymbol {\mathcal {P}}'$ defined as follows: $\tilde {\boldsymbol {\mathcal {P}}} = \left (\{1,2,3,4,5\}, E(\mathcal {P}^{(1)}), \{(1,3)\}\right )$ and $\boldsymbol {\mathcal {P}}' = \left (\{1,2,3,4,5\}, E(\mathcal {P}^{(1)})\setminus \{(2,3)\}, E(\mathcal {P}^{(2)})\right )$ .

2.2 Asymptotic normality in the satisfiability region

Once the threshold for the emergence of a multiplex $\boldsymbol {H}$ is obtained, the next natural question is to determine the limiting distribution of $X(\boldsymbol {H}, \boldsymbol G_n)$ in the satisfiability region (where $\boldsymbol {G}_n$ contains a diverging number of copies of $\boldsymbol {H}$ ). For the Erdős–Rényi random graph $G(n, p_1)$ , it is well known that the number of copies of a fixed subgraph H is asymptotically normal, whenever $G_n$ contains a diverging number of copies of H (which corresponds to the condition $n p_1^{m_H} \gg 1$ ) [Reference Barbour, Karoński and Ruciński3, Reference Janson17, Reference Nowicki26, Reference Ruciński33] (see [Reference Janson, Łuczak and Ruciński18, Chapter 6] for a comprehensive discussion). In this section, we will derive the analogous result for submultiplexes, under the parametrization (2.5).

To state the result, recall the definition of the Wasserstein distance between two random variables X and Z, to be denoted by $d_{\mathrm {Wass}}(X, Z)$ , from [Reference Chen, Goldstein and Shao11, Chapter 4]. Define

(2.11) $$ \begin{align} Z(\boldsymbol H, \boldsymbol G_n) := \frac{ X(\boldsymbol H, \boldsymbol G_n) - \mathbb{E} [X(\boldsymbol H, \boldsymbol G_n) ]}{ \sqrt{ \mathrm{Var}[X(\boldsymbol H, \boldsymbol G_n)] } }. \end{align} $$

The following theorem establishes the asymptotic normality of $Z(\boldsymbol H, \boldsymbol G_n)$ with a rate of convergence in terms of the Wasserstein distance.

Theorem 2.6 Suppose $\boldsymbol H = (V(\boldsymbol {H}), H^{(1)}, H^{(2)})$ is a fixed multiplex with at least one edge. Then, with the parametrization (2.5), the following holds:

(2.12) $$ \begin{align} d_{\mathrm{Wass}} (Z(\boldsymbol H, \boldsymbol G_n), N(0, 1) ) \lesssim_{\boldsymbol H} \frac{1}{\sqrt{n^{\Delta_{\boldsymbol H}(\boldsymbol \theta)}}} , \end{align} $$

where $\Delta _{\boldsymbol H}(\boldsymbol \theta )$ is defined in (2.7). This implies that $Z(\boldsymbol H, \boldsymbol G_n) \stackrel {D} \rightarrow N(0, 1)$ , whenever $\Delta _{\boldsymbol H}(\boldsymbol \theta )> 0$ .

The proof of Theorem 2.6 is given in Section 4. The proof uses Stein’s method based on dependency graphs, which bounds the distance to normality in the Wasserstein distance. This result shows that the number of copies of any submultiplex $\boldsymbol H$ in the correlated Erdős–Rényi random multiplex $\boldsymbol {G}_n$ is asymptotically normal, for all parameter values for which the count of $\boldsymbol H$ in $\boldsymbol G_n$ diverges in probability, in the parametrization (2.5). This is depicted by the colored polyhedral regions in Figures 2 and 3 for their respective examples.

2.3 Distribution on the boundary surface

In this section, we consider the regime where $\Phi _{\boldsymbol H} \asymp 1$ (or in the parametrization (2.5), $\Delta _{\boldsymbol H} = 0$ ). This is the boundary between the regimes in which the probability of containing $\boldsymbol H$ in $\boldsymbol {G}_n$ tends to $0$ and $1$ , respectively. Deriving the distribution of $X (\boldsymbol H, \boldsymbol G_n)$ in this regime is an intriguing problem. To motivate our results, let us begin by recalling the analogous results for the Erdős–Rényi model $G(n, p_1)$ when $p_1$ is at the threshold (for a particular subgraph H). More precisely, consider a fixed subgraph H and $G_n \sim G(n, p_1)$ , such that $n p_1^{m(H)} \rightarrow c \in (0, \infty )$ satisfies the threshold condition (recall the definition of $m(H)$ from (2.4)). Then, $X(H, G_n)$ has the following properties:

1. (P1) If H is strictly balanced (recall Remark 2.2), then $X(H, G_n)$ converges to a Poisson distribution (see [Reference Janson, Łuczak and Ruciński18, Theorem 3.19]).

2. (P2) If H is unbalanced, then $\mathbb {E}[X(H, G_n)] \gg 1$ at the threshold. In this case, there is a deterministic sequence $a_n(H) \gg 1$ such that the asymptotic distribution of $\frac {X(H, G_n)}{a_n(H) }$ coincides with that of $X(H', G_n)$ , for a certain balanced subgraph $H'$ of H. Hence, the problem reduces to the balanced case (see [Reference Ruciński34, Section 4] for details).

3. (P3) If H is balanced, but not strictly balanced, then the limiting distribution of $X(H, G_n)$ can, in principle, be described (using the notion of grading [Reference Bollobás and Wierman8]), but it has no universal compact form. In particular, it depends on the structure and the number of subgraphs that maximize (2.4) (see [Reference Janson, Łuczak and Ruciński18, Section 3.3] for examples).

Our goal in this section is to derive analogous results for submultiplexes in the correlated Erdős–Rényi model. The first step toward this is to define the notion of balance in the multiplex setting. Note that since we have a threshold surface, the definition of balance will depend on which parameter value on the surface is chosen. For this, recall the definition of $\ell _{\boldsymbol {F}}(\cdot )$ from (2.8).

Definition 2.2 Fix a multiplex $\boldsymbol H =(V(\boldsymbol H), H^{(1)}, H^{(2)})$ and a point $\boldsymbol \theta = (\theta _1, \theta _2, \theta _{12}) \in \partial _{\boldsymbol H}$ . Then $\boldsymbol H$ is said to be $\boldsymbol \theta $ -balanced if $\ell _{\boldsymbol H}(\boldsymbol \theta ) = 0$ and

(2.13) $$ \begin{align} \ell_{\boldsymbol F}(\boldsymbol \theta) \geq 0 \text{ for every proper submultiplex } \boldsymbol F \subset \boldsymbol H, \text{ with } |E(\boldsymbol F)| \geq 1. \end{align} $$

If the inequality in (2.13) is strict, then $\boldsymbol H$ is said to be strictly $\boldsymbol \theta $ -balanced. Furthermore, if $\ell _{\boldsymbol H}(\boldsymbol \theta )> 0$ and $\ell _{\boldsymbol F}(\boldsymbol \theta ) = 0$ , for some submultiplex $\boldsymbol F \subset \boldsymbol H$ , with $|E(\boldsymbol F)| \geq 1$ , then $\boldsymbol H$ is said to be $\boldsymbol \theta $ -unbalanced.

We begin with the case when $\boldsymbol {H}$ is strictly $\boldsymbol \theta $ -balanced. Let $\mathrm {Aut}(\boldsymbol H)$ denote the collection of all permutations of $V(\boldsymbol H)$ that preserve the edge sets in both layers. Then we have the following result, which is proved in Section 5.

Theorem 2.8 Fix a multiplex $\boldsymbol H =(V(\boldsymbol H), H^{(1)}, H^{(2)})$ and a point $\boldsymbol \theta = (\theta _1, \theta _2, \theta _{12}) \in \partial _{\boldsymbol H}$ such that $\boldsymbol {H}$ is strictly $\boldsymbol \theta $ -balanced and $\theta _{12}> \max \{\theta _1, \theta _2\}$ . Then

$$ \begin{align*} X(\boldsymbol{H}, \boldsymbol{G}_n) \xrightarrow{D} \mathrm{Pois}\left(\frac{1}{|\mathrm{Aut}(\boldsymbol H)|}\right). \end{align*} $$

Next, we consider the case where $\boldsymbol H$ is $\boldsymbol {\theta }$ -unbalanced. In this case, we can rescale $X(\boldsymbol {H}, \boldsymbol G_n)$ such that its asymptotic distribution coincides with that of a $\boldsymbol {\theta }$ -balanced submultiplex of $\boldsymbol {H}$ . Toward this, we need a few definitions: To begin with, fix a point $\boldsymbol \theta = (\theta _1, \theta _2, \theta _{12}) \in \partial _{\boldsymbol H}$ and recall the notion of $\boldsymbol \theta $ -extremal from Definition 2.1. Denote the collection of $\boldsymbol \theta $ -extremal submultiplexes of $\boldsymbol H$ as $\mathcal {A}_{\boldsymbol H}(\boldsymbol \theta )$ . The core of $\boldsymbol H$ is defined as the largest $\boldsymbol \theta $ -extremal submultiplex of $\boldsymbol H$ , that is, the unique maximum element in $\mathcal {A}_{\boldsymbol H}(\boldsymbol \theta )$ in terms of multiplex containment (which is well defined by Lemma 6.1).Footnote ¹ We also require the notion of an extension of a multiplex. Let $\boldsymbol F\subseteq \boldsymbol H$ be a fixed multiplex, and let $\boldsymbol F'$ be a copy of $\boldsymbol F$ . An extension of $\boldsymbol F'$ to $\boldsymbol H$ is a copy $\boldsymbol H'$ of $\boldsymbol H$ such that $\boldsymbol F'\subseteq \boldsymbol H'$ . Given a fixed copy $\overline {\boldsymbol H}'$ of the core $\overline {\boldsymbol H}$ , let $\mathcal {E}_n(\overline {\boldsymbol H}';\overline {\boldsymbol H},\boldsymbol H)$ denote the number of distinct copies $\boldsymbol H'$ of $\boldsymbol H$ satisfying $\overline {\boldsymbol H}'\subseteq \boldsymbol H' \subseteq \boldsymbol G_n\cup \overline {\boldsymbol H}'$ . By exchangeability, the distribution of this random variable does not depend on the particular copy $\overline {\boldsymbol H}'$ . We therefore write $\mathcal {E}_n(\overline {\boldsymbol H},\boldsymbol H)$ for a random variable having this common distribution.

Theorem 2.10 Fix a multiplex $\boldsymbol H =(V(\boldsymbol H), H^{(1)}, H^{(2)})$ and a point $\boldsymbol \theta = (\theta _1, \theta _2, \theta _{12}) \in \partial _{\boldsymbol H}$ . Then, with the parametrization (2.5),

(2.14) $$ \begin{align} \left|\frac{X(\boldsymbol H, \boldsymbol G_n)}{\mathbb{E}[\mathcal{E}_n(\overline{\boldsymbol{H}}, \boldsymbol{H})]} - X(\overline{\boldsymbol H}, \boldsymbol G_n) \right| \xrightarrow{P} 0. \end{align} $$

The proof of Theorem 2.10 is given in Section 6. A main technical step in the proof is to show that the core $\overline {\boldsymbol H}$ is well defined. The challenge here is that, unlike in the case of graphs (single-layer networks), the notions of balanced/extremal depend on the parameter value $\boldsymbol \theta \in \partial _{\boldsymbol H}$ . The key observation here is that $\ell _{\boldsymbol F}(\boldsymbol \theta )$ is modular (see (6.2) for the definition), for $\boldsymbol \theta \in \partial _{\boldsymbol H}$ , as $\boldsymbol F$ ranges over the set of $\boldsymbol \theta $ -extremal multiplexes. Using this, we can establish that the core is well defined. Then by estimating the number of extensions of a planted core together with a second-moment argument, the result in (2.14) follows.

A useful special case is when $\boldsymbol H =(V(\boldsymbol H), H^{(1)}, H^{(2)})$ is $\boldsymbol {\theta }$ -unbalanced such that $|\mathcal A_{\boldsymbol H}(\boldsymbol \theta )| = 1$ , that is, there is a unique $\boldsymbol \theta $ -extremal submultiplex (which is not $\boldsymbol H$ itself). Then the core $\overline {\boldsymbol {H}}$ is strictly $\boldsymbol {\theta }$ -balanced and invoking Theorems 2.8 and 2.10, we have the following result.

Corollary 2.12 Fix a multiplex $\boldsymbol H =(V(\boldsymbol H), H^{(1)}, H^{(2)})$ and a point $\boldsymbol \theta = (\theta _1, \theta _2, \theta _{12}) \in \partial _{\boldsymbol H}$ such that $\theta _{12}> \max \{\theta _1, \theta _2\}$ and $|\mathcal A_{\boldsymbol H}(\boldsymbol \theta )| = 1$ . Then,

$$ \begin{align*} \frac{X(\boldsymbol H, \boldsymbol G_n)}{\mathbb{E}[\mathcal{E}_n(\overline{\boldsymbol{H}}, \boldsymbol{H})]} \xrightarrow{D} \mathrm{Pois}\left(\frac{1}{ |\mathrm{Aut}(\overline{\boldsymbol H})| }\right). \end{align*} $$

To illustrate the above results, let us return to the edge-triangle multiplex from Example 2.3.

6.1 Proof of (6.1)

We begin with the following lemma.

Now, suppose $\boldsymbol F \in \mathcal {A}_{\boldsymbol H}(\boldsymbol \theta )$ and $\hat {\boldsymbol F}$ is the completion of $\boldsymbol F$ . This means, by Lemma 6.2, $0 \leq \ell _{\hat {\boldsymbol F}}(\boldsymbol \theta )\leq \ell _{\boldsymbol F}(\boldsymbol \theta ) = 0$ . Hence, $\ell _{\hat {\boldsymbol F}}(\boldsymbol \theta ) = 0$ , that is, $\hat {\boldsymbol F} \in \mathcal {A}_{\boldsymbol H}(\boldsymbol \theta )$ .

6.2 Proof of (6.2)

Let $\boldsymbol Q = (V(\boldsymbol Q), Q^{(1)}, Q^{(2)}) \text { and } \boldsymbol R = (V(\boldsymbol R), R^{(1)}, R^{(2)})$ be two complete submultiplexes in $\mathcal {A}_{\boldsymbol H}(\boldsymbol \theta )$ . Observe that both sides of (6.2) are linear functions of $\theta _1, \theta _2, \theta _{12}$ . To begin with, observe that $ |V( \boldsymbol {Q} \cup \boldsymbol {R})| = |V( \boldsymbol {Q})| + |V(\boldsymbol {R})| - |V( \boldsymbol {Q} \cap \boldsymbol {R})|$ . Hence, the constant terms on both sides of (6.2) are equal. Next, consider the coefficients of $\theta _1$ on both sides of (6.2). To this end, note that

$$ \begin{align*} & \left(E(Q^{(1)}) \cup E(R^{(1)})\right) \setminus \left(E(Q^{(2)}) \cup E(R^{(2)})\right) \\ & = \left(E(Q^{(1)}) \cup E(R^{(1)})\right) \cap \left( E(Q^{(2)})^{c} \cap E(R^{(2)})^{c} \right) \\ & = \left(E(Q^{(1)}) \cap E(Q^{(2)})^{c} \cap E(R^{(2)})^{c}\right) \cup \left(E(R^{(1)}) \cap E(Q^{(2)})^{c} \cap E(R^{(2)})^{c}\right). \end{align*} $$

Observe, if $(u,v) \in E(Q^{(1)}) \cap E(Q^{(2)})^{c}$ , then $(u,v)$ is an edge only in layer 1 of  $ \boldsymbol {Q}$ . Therefore, by completeness of $ \boldsymbol {Q}$ , $(u,v)$ can only be an edge in one layer of  $\boldsymbol H$ . This means $(u,v) \in E(R^{(2)})^c$ . Thus, $E(Q^{(1)}) \cap E(Q^{(2)})^{c} \cap E(R^{(2)})^{c} = E(Q^{(1)}) \cap E(Q^{(2)})^{c}$ . Similarly, $E(R^{(1)}) \cap E(Q^{(2)})^{c} \cap E(R^{(2)})^{c} = E(R^{(1)}) \cap E(R^{(2)})^{c}$ . Combining the above gives

$$ \begin{align*} & \left(E(Q^{(1)}) \cup E(R^{(1)})\right) \setminus \left(E(Q^{(2)}) \cup E(R^{(2)})\right) \nonumber \\ & = \left(E(Q^{(1)}) \setminus E(Q^{(2)})\right) \cup \left(E(R^{(1)}) \setminus E(R^{(2)})\right). \end{align*} $$

Hence,

(6.4) $$ \begin{align} & \left|\left(E(Q^{(1)}) \cup E(R^{(1)})\right) \setminus \left(E(Q^{(2)}) \cup E(R^{(2)})\right)\right| \nonumber \\ & = \left|E(Q^{(1)}) \setminus E(Q^{(2)})\right|+ \left|E(R^{(1)}) \setminus E(R^{(2)})\right| \nonumber \\ & \hspace{0.25in} - \left|\left(E(Q^{(1)}) \setminus E(Q^{(2)})\right) \cap \left(E(R^{(1)}) \setminus E(R^{(2)})\right)\right|. \end{align} $$

Note that

$$ \begin{align*} & (E(Q^{(1)}) \setminus E(Q^{(2)})) \cap (E(R^{(1)}) \setminus E(R^{(2)})) \nonumber \\ & = (E(Q^{(1)})\cap E(R^{(1)}))\setminus (E(Q^{(2)})\cup E(R^{(2)})) \nonumber \\ & \subseteq (E(Q^{(1)})\cap E(R^{(1)}))\setminus (E(Q^{(2)})\cap E(R^{(2)})). \end{align*} $$

We will show that the inclusion in the other direction also holds. For this, suppose

$$ \begin{align*}(u,v) \in (E(Q^{(1)})\cap E(R^{(1)}))\setminus (E(Q^{(2)})\cap E(R^{(2)})).\end{align*} $$

Then $(u,v)\in E(Q^{(1)})\cap E(R^{(1)})$ and $(u,v)\in E(Q^{(2)})^c \cup E(R^{(2)})^c$ . Hence, there are two possibilities:

• • $(u,v)\notin E(Q^{(2)})$ . This means $(u,v) \in E(Q^{(1)}) \setminus E(Q^{(2)})$ . Also, by completeness of $ \boldsymbol {Q}$ , $(u,v)\notin E(H^{(2)})$ , and, as a result, $(u,v) \notin E(R^{(2)})$ . This shows $(u,v) \in E(R^{(1)}) \setminus E(R^{(2)})$ . Hence, $(u,v) \in (E(Q^{(1)}) \setminus E(Q^{(2)})) \cap (E(R^{(1)}) \setminus E(R^{(2)}))$ .

• • $(u,v)\notin E(R^{(2)})$ . In this case, similarly, it can be shown that $(u,v) \in (E(Q^{(1)}) \setminus $ $E(Q^{(2)})) \cap (E(R^{(1)}) \setminus E(R^{(2)}))$ .

Hence, combining the above shows

$$ \begin{align*} & (E(Q^{(1)}) \setminus E(Q^{(2)})) \cap (E(R^{(1)}) \setminus E(R^{(2)})) \nonumber \\ & = (E(Q^{(1)})\cap E(R^{(1)}))\setminus (E(Q^{(2)})\cup E(R^{(2)})) \nonumber \\ & = (E(Q^{(1)})\cap E(R^{(1)}))\setminus (E(Q^{(2)})\cap E(R^{(2)})). \end{align*} $$

Therefore, from (6.4),

$$ \begin{align*} & \left|\left(E(Q^{(1)}) \cup E(R^{(1)})\right) \setminus \left(E(Q^{(2)}) \cup E(R^{(2)})\right)\right| \nonumber \\ & = \left|E(Q^{(1)}) \setminus E(Q^{(2)})\right|+ \left|E(R^{(1)}) \setminus E(R^{(2)})\right| \nonumber \\ & \hspace{0.25in} - \left|\left(E(Q^{(1)}) \cap E(R^{(1)})\right) \setminus \left(E(Q^{(2)}) \cap E(R^{(2)})\right)\right|. \end{align*} $$

This shows that the coefficients of $\theta _1$ on both sides of (6.2) are equal. Similarly, it can be shown that the coefficients of $\theta _2$ on both sides of (6.2) are equal. Finally, consider the coefficients $\theta _{12}$ on both sides of (6.2). This gives

(6.5) $$ \begin{align} & (E(Q^{(1)}) \cup E(R^{(1)})) \cap (E(Q^{(2)}) \cup E(R^{(2)})) \nonumber \\ & = (E(Q^{(1)}) \cap E(Q^{(2)}) ) \cup (E(R^{(1)}) \cap E(R^{(2)}) ) \nonumber \\ & \hspace{0.25in} \cup (E(Q^{(1)}) \cap E(R^{(2)}) ) \cup (E(Q^{(2)}) \cap E(R^{(1)}) ). \end{align} $$

Note that

(6.6) $$ \begin{align} (E(Q^{(1)}) \cap E(Q^{(2)}) ) \cup (E(Q^{(1)}) \cap E(R^{(2)}) ) = E(Q^{(1)}) \cap E(Q^{(2)}). \end{align} $$

Clearly, the RHS is contained in the LHS. Now, suppose $(u, v) \in (E(Q^{(1)}) \cap E(R^{(2)})) \setminus ( E(Q^{(1)}) \cap E(Q^{(2)}) )$ . This means $(u, v) \in (E(Q^{(1)}) \cap E(R^{(2)}))$ and $ (u, v) \notin E(Q^{(2)})$ . Then by completeness of $ \boldsymbol {Q}$ , $ (u, v) \notin E(H^{(2)})$ , and as a result, $(u, v) \notin E(R^{(2)})$ , which is a contradiction. Hence, $(E(Q^{(1)}) \cap E(R^{(2)})) \setminus ( E(Q^{(1)}) \cap E(Q^{(2)}) ) = \emptyset $ , and (6.6) holds. Similarly,

(6.7) $$ \begin{align} (E(R^{(1)}) \cap E(R^{(2)}) ) \cup (E(Q^{(2)}) \cap E(R^{(1)}) ) = E(R^{(1)}) \cap E(R^{(2)}). \end{align} $$

Combining (6.5)–(6.7) gives $(E(Q^{(1)}) \cup E(R^{(1)})) \cap (E(Q^{(2)}) \cup E(R^{(2)})) =$ $(E(Q^{(1)}) \cap E(Q^{(2)}) ) \cup (E(R^{(1)}) \cap E(R^{(2)}) )$ . Hence,

$$ \begin{align*} & |(E(Q^{(1)}) \cup E(R^{(1)})) \cap (E(Q^{(2)}) \cup E(R^{(2)}))| \nonumber \\ & = | E(Q^{(1)}) \cap E(Q^{(2)})| + | E(R^{(1)}) \cap E(R^{(2)}) | \nonumber \\ & \hspace{0.25in} - | E(Q^{(1)}) \cap E(Q^{(2)}) \cap E(R^{(1)}) \cap E(R^{(2)})|. \nonumber \end{align*} $$

This shows that the coefficients of $\theta _{12}$ on both sides of (6.2) are equal.

6.3 Completing the Proof of Theorem 2.10

Note that since $\overline {\boldsymbol H }$ is the core, $\ell _{\overline {\boldsymbol H }}(\boldsymbol \theta ) = 0$ . We begin by stating some consequences of the definition of the core.

• • By (6.1), the completion $\hat {\overline {\boldsymbol H}}$ is also $\boldsymbol \theta $ -extremal. Since ${\overline {\boldsymbol H}}$ is the maximum $\boldsymbol \theta $ -extremal submultiplex of $\boldsymbol H$ and ${\overline {\boldsymbol H}}\subseteq \hat {\overline {\boldsymbol H}}$ , it follows that $\hat {\overline {\boldsymbol H}}={\overline {\boldsymbol H}}$ . Thus, the core is complete.

• • Moreover, ${\overline {\boldsymbol H}}$ is the unique copy of its isomorphism type contained in $\boldsymbol H$ . Indeed, suppose that $\boldsymbol F\subseteq \boldsymbol H$ and $\boldsymbol F\cong {\overline {\boldsymbol H}}$ . Then $\ell _{\boldsymbol F}(\boldsymbol \theta )=0$ , so $\boldsymbol F$ is $\boldsymbol \theta $ -extremal. Since ${\overline {\boldsymbol H}}$ is the maximum extremal submultiplex, $\boldsymbol F\subseteq {\overline {\boldsymbol H}}$ . The multiplexes $\boldsymbol F$ and ${\overline {\boldsymbol H}}$ are isomorphic, and therefore have the same number of vertices and the same edge counts in both layers. Hence, the containment $\boldsymbol F\subseteq {\overline {\boldsymbol H}}$ forces $\boldsymbol F={\overline {\boldsymbol H}}$ . Consequently, every distinct image copy of $\boldsymbol H$ contains exactly one distinct image copy of ${\overline {\boldsymbol H}}$ .

• • If ${\overline {\boldsymbol H}}=\boldsymbol H$ , then $\mathcal {E}_n({\overline {\boldsymbol H}},\boldsymbol H)=1$ almost surely, and the quantity in (2.14) is identically zero. We may therefore assume that ${\overline {\boldsymbol H}}\subsetneq \boldsymbol H$ .

To proceed, fix a copy $\overline {\boldsymbol H}'$ of ${\overline {\boldsymbol H}}$ in the complete multiplex $\boldsymbol K_n$ . Let $\mathcal N_n(\overline {\boldsymbol H}')$ denote the collection of all distinct copies $\boldsymbol {H}'$ of $\boldsymbol H$ in $\boldsymbol K_n$ satisfying $\overline {\boldsymbol H}'\subseteq \boldsymbol {H}'$ . For $\boldsymbol {H}'\in \mathcal N_n(\overline {\boldsymbol H}')$ , define

$$ \begin{align*}Y_{\boldsymbol{H}'} := \boldsymbol 1 \{\boldsymbol{H}'\subseteq\boldsymbol G_n\cup\overline{\boldsymbol H}' \} \text{ and } Z_{\overline{\boldsymbol H}'} := \sum_{\boldsymbol{H}'\in\mathcal N_n(\overline{\boldsymbol H}')}Y_{\boldsymbol{H}'}.\end{align*} $$

Then $Z_{\overline {\boldsymbol H}'}$ has the same distribution as $\mathcal {E}_n({\overline {\boldsymbol H}},\boldsymbol H)$ . By exchangeability, this distribution does not depend on the particular copy $\overline {\boldsymbol H}'$ . Also, let $\mathcal C_n({\overline {\boldsymbol H}})$ be the collection of distinct copies of the core in $\boldsymbol K_n$ . Note that on the event $\{ \overline {\boldsymbol H}'\subseteq \boldsymbol G_n \}$ , one has ${\boldsymbol G_n\cup \overline {\boldsymbol H}'=\boldsymbol G_n}$ . Hence, $\boldsymbol 1\{ \overline {\boldsymbol H}'\subseteq \boldsymbol G_n \}Z_{\overline {\boldsymbol H}'}$ counts the copies of $\boldsymbol H$ occurring in $\boldsymbol G_n$ that contain the particular core copy $\overline {\boldsymbol H}'$ . Since every copy of $\boldsymbol H$ contains exactly one copy of ${\overline {\boldsymbol H}}$ ,

(6.8) $$ \begin{align} X(\boldsymbol H,\boldsymbol G_n) = \sum_{\overline{\boldsymbol H}'\in\mathcal C_n({\overline{\boldsymbol H}})} \boldsymbol 1\{ \overline{\boldsymbol H}'\subseteq\boldsymbol G_n \}Z_{\overline{\boldsymbol H}'} \end{align} $$

and $X({\overline {\boldsymbol H}},\boldsymbol G_n) = \sum _{\overline {\boldsymbol H}'\in \mathcal C_n({\overline {\boldsymbol H}})} \boldsymbol 1\{ \overline {\boldsymbol H}'\subseteq \boldsymbol G_n \}$ . Note that the random variables $\boldsymbol 1\{\overline {\boldsymbol H}'\subseteq \boldsymbol G_n \}$ and $Z_{\overline {\boldsymbol H}'}$ are independent. This is because, $\boldsymbol 1\{ \overline {\boldsymbol H}'\subseteq \boldsymbol G_n\}$ depends only on the edge vectors corresponding to the underlying edges of $\overline {\boldsymbol H}'$ . Also, since ${\overline {\boldsymbol H}}$ is complete, an extension does not impose an additional layer requirement on any of these underlying edges. After the edges of $\overline {\boldsymbol H}'$ have been planted, $Z_{\overline {\boldsymbol H}'}$ therefore depends only on edge vectors indexed by underlying pairs outside $E(\overline {\boldsymbol H}')$ . Hence, using (6.8), the triangle inequality, independence, and the Cauchy–Schwarz inequality, we obtain

(6.9) $$ \begin{align} \mathbb E\left[ \left|\frac{X(\boldsymbol H,\boldsymbol G_n)}{ \mathbb{E}[\mathcal{E}_n({\overline{\boldsymbol H}},\boldsymbol H)]} - X({\overline{\boldsymbol H}},\boldsymbol G_n) \right| \right] &\leq \sum_{\overline{\boldsymbol H}'\in\mathcal C_n({\overline{\boldsymbol H}})} \mathbb E\left[\boldsymbol 1\{\overline{\boldsymbol H}'\subseteq\boldsymbol G_n\} \left| \frac{Z_{\overline{\boldsymbol H}'}}{ \mathbb{E}[Z_{\overline{\boldsymbol H}'}] }-1 \right| \right] \nonumber \\ &= \mathbb E[X({\overline{\boldsymbol H}},\boldsymbol G_n)] \mathbb E\left[ \left| \frac{Z_{\overline{\boldsymbol H}'}}{ \mathbb{E}[Z_{\overline{\boldsymbol H}'}] }-1 \right| \right] \nonumber\\ &\leq \mathbb E[X({\overline{\boldsymbol H}},\boldsymbol G_n)] \sqrt{ \frac{ \mathrm{Var}[Z_{\overline{\boldsymbol H}'}]}{ \mathbb{E}[Z_{\overline{\boldsymbol H}'}]^2 } }. \end{align} $$

Note that $\mathbb E[X({\overline {\boldsymbol H}},\boldsymbol G_n)] \asymp _{\boldsymbol H} n^{|V(\overline {\boldsymbol H})|} \lambda _{p_1, p_2, p_{12}}({\overline {\boldsymbol H}}) = n^{\ell _{{\overline {\boldsymbol H}}}(\boldsymbol \theta )} = 1$ . Hence, to show (2.14), it suffices to prove that

(6.10) $$ \begin{align} \mathrm{Var}[Z_{\overline{\boldsymbol H}'}] \ll \mathbb{E}[Z_{\overline{\boldsymbol H}'}]^2. \end{align} $$

6.3.1 Proof of (6.10)

Since the core is complete, an extension of $\overline {\boldsymbol H}'$ does not require an additional layer on any underlying edge already used by $\overline {\boldsymbol H}'$ . Hence, for every $\boldsymbol {H}'\in \mathcal N_n(\overline {\boldsymbol H}')$ , $\mathbb P(Y_{\boldsymbol {H}'}=1) = \frac {\lambda _{p_1, p_2, p_{12}}(\boldsymbol H)} {\lambda _{p_1, p_2, p_{12}}({\overline {\boldsymbol H}})}$ . Furthermore, $|\mathcal N_n(\overline {\boldsymbol H}')|\asymp _{\boldsymbol H} n^{|V(\boldsymbol H)|-|V(\overline {\boldsymbol H})}$ . Hence, it follows that

(6.11) $$ \begin{align} \mathbb{E}[Z_{\overline{\boldsymbol H}'}] \asymp_{\boldsymbol H} n^{|V(\boldsymbol H)| - |V(\overline{\boldsymbol H})} \frac{\lambda_{p_1, p_2, p_{12}}(\boldsymbol H)} {\lambda_{p_1, p_2, p_{12}}({\overline{\boldsymbol H}})} = n^{\ell_{\boldsymbol H}(\boldsymbol\theta) -\ell_{{\overline{\boldsymbol H}}}(\boldsymbol\theta)} = n^{\ell_{\boldsymbol H}(\boldsymbol\theta)}. \end{align} $$

We now compute the variance of $Z_{\overline {\boldsymbol H}'}$ . For this, for an extension $\boldsymbol {H}'$ , define its residual underlying edge support by $S(\boldsymbol {H}') := E(\boldsymbol {H}')\setminus E(\overline {\boldsymbol H}')$ . For two extensions $\boldsymbol {H}',\boldsymbol H"$ , if $S(\boldsymbol {H}')\cap S(\boldsymbol H")=\varnothing $ , then $Y_{\boldsymbol {H}'}$ and $Y_{\boldsymbol H"}$ depend on disjoint collections of independent edge vectors and are therefore independent. For two extensions $\boldsymbol {H}',\boldsymbol H"$ satisfying $S(\boldsymbol {H}')\cap S(\boldsymbol H")\neq \varnothing $ , define the (one-sided) overlap multiplex $\boldsymbol F_{\boldsymbol {H}', \boldsymbol H"}$ by $V(\boldsymbol F_{\boldsymbol {H}', \boldsymbol H"}):= V(\boldsymbol {H}')\cap V(\boldsymbol H")$ , and, for $i\in \{1,2\}$ ,

$$\begin{align*}E(F_{\boldsymbol{H}', \boldsymbol H"}^{(i)}) := E((\overline{H}')^{(i)}) \cup \left[ \left( E((H')^{(i)})\setminus E((\overline{H}')^{(i)}) \right) \cap E(\boldsymbol H") \right]. \end{align*}$$

An argument similar to the one used in (3.8) gives

(6.12) $$ \begin{align} \mathbb P(Y_{\boldsymbol{H}'}=Y_{\boldsymbol H"}=1) \leq \frac{ \left( \lambda_{p_1, p_2, p_{12}}(\boldsymbol H)/\lambda_{p_1, p_2, p_{12}}({\overline{\boldsymbol H}}) \right)^2 }{ \lambda_{p_1, p_2, p_{12}}(\boldsymbol F_{\boldsymbol{H}', \boldsymbol H"}) / \lambda_{p_1, p_2, p_{12}}({\overline{\boldsymbol H}}) }. \end{align} $$

For every fixed isomorphism type $\boldsymbol F$ arising in this way, the number of ordered pairs $(\boldsymbol {H}',\boldsymbol H")$ satisfying $\boldsymbol F_{\boldsymbol {H}', \boldsymbol H"}\cong \boldsymbol F$ is at most $\lesssim _{\boldsymbol H} n^{2(|V(\boldsymbol H)| - |V(\overline {\boldsymbol H})| )-(|V(\boldsymbol F)| - |V(\overline {\boldsymbol H})|)}$ . Let $\mathcal F$ be the finite collection of isomorphism types of submultiplexes of $\boldsymbol H$ that properly contain a copy of ${\overline {\boldsymbol H}}$ and can arise as such an overlap. Then, using $\mathrm {Cov}[Y_{\boldsymbol {H}'},Y_{\boldsymbol H"}] \leq \mathbb P(Y_{\boldsymbol {H}'}=Y_{\boldsymbol H"}=1)$ , (6.11) and (6.12) gives

$$ \begin{align*} & \mathrm{Var}[Z_{\overline{\boldsymbol H}'}] \nonumber \\ & \lesssim_{\boldsymbol H}\, n^{2( |V(\boldsymbol H)| - |V(\overline{\boldsymbol H})|)} \left(\frac{\lambda_{p_1, p_2, p_{12}}(\boldsymbol H)} {\lambda_{p_1, p_2, p_{12}}({\overline{\boldsymbol H}})} \right)^2 \sum_{\boldsymbol F\in\mathcal F} \frac{ \lambda_{p_1, p_2, p_{12}}({\overline{\boldsymbol H}}) }{ n^{|V(\boldsymbol F)|- |V(\overline{\boldsymbol H})| } \lambda_{p_1, p_2, p_{12}}(\boldsymbol F) } \nonumber \\ & \lesssim_{\boldsymbol H} \mathbb{E}[Z_{\overline{\boldsymbol H}'}]^2 \sum_{\boldsymbol F\in\mathcal F} \frac{1}{n^{\ell_{\boldsymbol F}(\boldsymbol\theta)}} \ll \mathbb{E}[Z_{\overline{\boldsymbol H}'}]^2 , \end{align*} $$

since $\ell _{\boldsymbol F}(\boldsymbol \theta )> 0$ , for all $\boldsymbol F\in \mathcal F$ , by the maximality of the core. This proves (6.10).