Proof of Lemma 4.1.Let $H_1, H_2 ,\ldots$ be an enumeration of finite graphs in $\mathcal{G}_*$ . For positive integers i, n, define the event

\begin{align*}B(i,n) = \bigl\{\exists j \le i\,:\, | p_{r_j}(G_n, H_j) - {\mathbb{P}}( B_{r_j}(G^*) \cong H_j) | > i^{-1} \bigr\},\end{align*}

where $r_j$ is the radius of $H_j$ . By the assumption of the lemma, ${\mathbb{P}}(B(i,n)) \to 0$ for each $i=1,2,\ldots.$ Define $N_1 = 1$ , $N_i, i = 2,3,\ldots$ by taking

\begin{align*}N_i = 1 + \sup \bigl\{n > N_{i-1} \,:\, {\mathbb{P}}(B(i,n)) > i^{-1}\bigr\}.\end{align*}

Let $i(n) = \max\{i \,:\, N_i \le n\}$ . Now let $A = \bigl\{n\,:\, \overline{B(i(n),n)} \bigr\}$ . We have ${\mathbb{P}}(n \not \in A) = {\mathbb{P}}(B(i(n), n)) \le i(n)^{-1} \to 0$ . For any sequence of events $\{A_n, n\ge1\}$ on the same probability space $(\Omega, {\mathcal{F}}, {\mathbb{P}})$ , we have

(4.6) \begin{equation}{\mathbb{P}}(\cap_{m \ge 1} \cup_{n\ge m} A_n) \ge \lim \sup {\mathbb{P}}(A_n).\end{equation}

Thus

\begin{align*}{\mathbb{P}}(|A| = \infty) \ge \lim \sup {\mathbb{P}}\bigl(\overline{B(i(n),n)}\bigr) = 1.\end{align*}

Now, by the definition of B(i, n) on the event $|A| = \infty$ , we have $(G_n, v_n^*) \,\xrightarrow{d}\, G^*$ as $n\to\infty$ , $n \in A$ .

Proof of Lemma 4.2. ( $\Leftarrow$ ) The function $(\mathcal{G}_*, d_{\operatorname{loc}}) \to \mathbb{R}$ that maps (G, v) to ${\mathbb I}_{B_r(G,v) \cong H}$ is bounded and continuous for each $r\ge 0$ and connected rooted graph H.

( $\Rightarrow$ ) Without loss of generality we may assume $\{(G_n,v_n^*)\}$ are defined on a single probability space. Let A be a random set guaranteed by Lemma 4.1. Suppose there is some $\epsilon > 0$ , a bounded continuous function f, and an infinite subset of positive integers B, such that ${\mathbb{P}}( |{\mathbb{E}}(f(G_n,v_n^*)\mid G_n) - {\mathbb{E}} f(G^*)| > \epsilon) > \epsilon$ for all $n \in B$ . Define a random set $C = \{n \in B\,:\, |{\mathbb{E}}(f(G_n,v_n^*)\mid G_n) - {\mathbb{E}} f(G^*)| > \epsilon\}$ . Since for $n \in A \cap B$ we have ${\mathbb{P}}(n \in A \cap C) \ge \epsilon - {\mathrm{o}} (1)$ , by (4.6) ${\mathbb{P}}(|A \cap C| = \infty) \ge \epsilon$ . However, $(G_n,v_n^*) \,\xrightarrow{d}\, G^*$ when $n \to \infty, n \in A$ , by (1.1), which contradicts our assumption.

Proof of Lemma 4.3. We can assume $n_1 \ge 1$ .

(i) $\Leftrightarrow$ (ii) This follows by Lemma 2.1, since Lemma 4.2 implies convergence in distribution of $d_n^{h-1}$ to $(d^*)^{h-1}$ .

(i) $\Rightarrow$ (4.1), (iii) Assume (i). Then there is a positive sequence $a_n \to 0$ , such that $|{\mathbb{E}} d_n^{h-1} - {\mathbb{E}} (d^*)^{h-1}| \le a_n$ . The empirical $(h-1)$ th moment of the degree of $G_n$ is $D_n = n_1^{-1} \hom\!(K_{1,h-1}, G_n)$ . Also, $D_n = \sum_{H \in \mathcal{S}} d_{H}(\mathrm{root}(H))^{h-1} p_r(G_n, H)$ , where $\mathcal{S}$ consists of graphs in $\mathcal{G}_*$ of radius 1. Since ${\mathbb{E}} D_n = {\mathbb{E}} d_n^{h-1}$ , it follows by (i) and (3.1) that $D_n \xrightarrow{p} {\mathbb{E}}(d^*)^{h-1}$ . So there is a positive sequence $\epsilon_n \to 0$ , such that for all n,

\begin{equation*}{\mathbb{P}}\bigl(|D_n - {\mathbb{E}} (d^*)^{h-1}| > \epsilon_n\bigr) \le \epsilon_n.\end{equation*}

We may assume that $\epsilon_n \ge a_n$ . Let the random set C consist of those n for which $|D_n - {\mathbb{E}} (d^*)^{h-1}| \le \epsilon_n$ . It follows by (4.6) that ${\mathbb{P}}(|C| = \infty) = 1$ , ${\mathbb{P}}(n \in C) \to 1$ and on the event $|C| = \infty$ , $D_n \to {\mathbb{E}} (d^*)^{h-1}$ as $n \to \infty$ , $n \in C$ .

Let A be the random set guaranteed by Lemma 4.1. On the event $|A \cap C| = \infty$ , the subsequence of graphs $\{G_n, n \in A \cap C\}$ satisfies the conditions of Theorem 2.1.

Assume (4.1) does not hold. Then there is $H^{\prime} \in \mathcal{R}(H)$ , $\epsilon > 0$ and a deterministic infinite set D of positive integers such that for all $n \in D$ ,

\begin{align*}{\mathbb{P}}( |X_n - {\mathbb{E}} X^*| > \epsilon) > \epsilon.\end{align*}

Here $X_n = n_1^{-1}\, \mathrm{emb}(H, G_n)$ and $X^* = \mathrm{emb}^{\prime}(H^{\prime}, G^*, r^*)$ . Let $D_1 \subseteq D$ consist of those n in D for which $|X_n - {\mathbb{E}} X^*| > \epsilon$ . Again, by (4.6), we get that ${\mathbb{P}}(|A\cap C \cap D_1| = \infty) \ge \epsilon$ . On this event $X_n \not \to {\mathbb{E}} X^*$ as $n \to \infty, n \in A \cap C$ . This is a contradiction to Theorem 2.1(iii).

It remains to show (iii). Write $Y_n = n_1^{-1} \hom\!(H, G_n)$ . Trivially, $X_n \le Y_n$ , and by Lemma 2.2 $Y_n \le D_n$ . So, for any $t > 0$ ,

\begin{align*}{\mathbb{E}} X_n {\mathbb I}_{X_n > t} \le {\mathbb{E}} Y_n {\mathbb I}_{Y_n > t} \le {\mathbb{E}} D_n {\mathbb I}_{D_n > t}.\end{align*}

Since ${\mathbb{E}} D_n \to {\mathbb{E}} (d^*)^{h-1}$ and $D_n \xrightarrow{p} {\mathbb{E}} (d^*)^{h-1}$ , $D_n$ is uniformly integrable, and so is $X_n$ . Since $X_n$ also converges in probability by (4.1), (iii) follows by Lemma 2.1.

(iii) $\Rightarrow$ (i) The proof is identical to that of the corresponding implication of Theorem 2.1.

Proof of Corollary 4.1. Apply Lemma 4.3.

Proof of Corollary 4.2. For non-empty G, we have

\begin{equation*}g(G) = \dfrac {\hom\!(P_4, G)} {\mathrm{emb}(K_2, G)},\quad b(G) = \dfrac {\hom\!(K_{1,2}, G)} {\mathrm{emb}(K_2, G)},\quad b^{\prime}(G) = \dfrac {\hom\!(K_{1,3}, G)} {\mathrm{emb}(K_2, G)}.\end{equation*}

Let S(t, j) denote Stirling numbers of the second kind. Using Lemma 4.3,

\begin{align*}&\dfrac 1 n\ \mathrm{emb}(K_2, G_n) \xrightarrow{p} {\mathbb{E}} d^*, \\ & \dfrac 1 n \hom\!(P_4, G_n) \\ & \quad = \dfrac 1 n \bigl(\mathrm{emb}(P_4, G_n) + \mathrm{emb}(K_3, G_n) + 2\ \mathrm{emb}(P_3, G_n) + \mathrm{emb}(K_2, G_n) \bigr) \\ &\quad \xrightarrow{p} {\mathbb{E}} \bigl( \mathrm{emb}^{\prime}(P^{\prime}_4, G^*) + \mathrm{emb}^{\prime}(K^{\prime}_3, G^*) + \mathrm{emb}(K_{1,2}^{\prime}, G^*) + \mathrm{emb}(P^{\prime}_3, G^*) + \mathrm{emb}^{\prime}(K^{\prime}_2, G^*)\bigr) \\ & \quad = {\mathbb{E}} \hom^{\prime}\!(P^{\prime}_4, G^*,r^*), \\ & \dfrac 1 n \hom\!(K_{1,t}, G_n) = \dfrac 1 n \sum_{j=1}^t S(t, j) \mathrm{emb}(K_{1,j}, G_n) \xrightarrow{p} {\mathbb{E}} \hom^{\prime}\!(K^{\prime}_{1,t}, G^*,r^*) = {\mathbb{E}} (d^*)^t\end{align*}

for $t = 2, 3$ . The claim follows by the definition of r(G).

Proof of Corollary 4.3. Note that $\pi_k(G_n) \xrightarrow{p} {\mathbb{P}}(d^*=k) > 0$ and when $\pi_k(G) > 0$ we have

(4.7) \begin{align} r_k(G) &= \dfrac{{\mathbb{E}} \bigl( d_{G}(u_2^*) {\mathbb I}_{d_{G_n}(u_1^*)=k} {\mathbb I}_{u_1^*u_2^* \in G} \mid G_n=G \bigr)} {{\mathbb{P}}(d_{G_n}(u_1^*) = k, u_1^*u_2^* \in G \mid G_n = G)} \notag \\ &=\dfrac{(n_1)_2^{-1} H(G)} {k (n_1-1)^{-1} \pi_k(G)} \notag \\ & = n_1^{-1} H(G) (k \pi_k(G))^{-1}, \end{align}

where H(G) is the number of homomorphisms from $P_3 = x y z$ to G so that x is mapped to a vertex of degree k. Let $H_t(G)$ denote the number of such homomorphisms where additionally y is mapped to a vertex of degree at most t, and let ${\bar H}_t(G) = H(G) - H_t(G)$ .

Fix $\delta > 0$ . We will show that for any $\epsilon > 0$ and all n large enough,

(4.8) \begin{equation} {\mathbb{P}}\bigl(|n_1^{-1}H(G_n) - {\mathbb{E}} {\mathbb I}_{d^*=k}\hom^{\prime}\!(P^{\prime}_3, G^*, r^*) | > \delta\bigr) \le \epsilon, \end{equation}

i.e. $n_1^{-1}H(G_n) \xrightarrow{p} {\mathbb{E}} {\mathbb I}_{d^*=k}\hom^{\prime}\!(P^{\prime}_3, G^*, r^*)$ .

By Lemma 4.2,

\begin{align*} n_1^{-1} H_t(G_n) &= {\mathbb{E}}\Biggl({\mathbb I}_{d_{G_n}(u_1^*)=k} \sum_{u\,:\, u u_1^* \in G_n} d_{G_n}(u) {\mathbb I}_{d_{G_n}(u) \le t} \biggm| G_n\Biggr) \\ &\xrightarrow{p} h_t^* = {\mathbb{E}} \Biggl({\mathbb I}_{d^*=k} \sum_{u\,:\, u r^* \in G^*} d_{G^*}(u) {\mathbb I}_{d_{G^*}(u) \le t}\Biggr). \end{align*}

Also, $h_t^* \to h^* = {\mathbb{E}} {\mathbb I}_{d^* = k} \hom^{\prime}\!(P^{\prime}_3, G^*, r^*)$ as $t \to \infty$ since ${\mathcal L}((G_n, v^*_n) \mid G_n) \,\xrightarrow{p}\, {\mathcal L}(G^*)$ and $h^* \le {\mathbb{E}} \hom^{\prime}\!(P^{\prime}_3, G^*, r^*) < \infty$ by Lemma 4.3. Therefore we can pick $t_1$ such that for $t \ge t_1$ and all n large enough,

\begin{align*} {\mathbb{P}}\biggl(|n_1^{-1} H_{t}(G_n) - h_{t}^*| > \dfrac \delta 4\biggr) \le \dfrac \epsilon 4, \quad |h_{t}^* - h^*| \le \dfrac \delta 4 \end{align*}

and so

(4.9) \begin{equation} {\mathbb{P}}\biggl(|n_1^{-1} H_{t}(G_n) - h^*|> \dfrac \delta 2\biggr) \le \dfrac \epsilon 2. \end{equation}

Next, note that

\begin{align*} \bar{H}_t(G_n) \le \sum_{v \in V(G_n)} d_{G_n}(v)^2 {\mathbb I}_{d_{G_n}(v) > t}. \end{align*}

So, by Markov’s inequality,

\begin{align*} {\mathbb{P}}\bigl(n_1^{-1} {\bar H}_t(G_n) > \delta/2\bigr) \le 2 \delta^{-1} n_1^{-1} {\mathbb{E}} {\bar H}_t(G_n) \le 2 \delta^{-1} {\mathbb{E}} d_n^2 {\mathbb I}_{d_n > t}. \end{align*}

Now $d_n^2$ is uniformly integrable by Lemma 4.3, so there is $t_2$ such that for all $t \ge t_2$ and all large enough n,

(4.10) \begin{equation} {\mathbb{P}}\bigl(n_1^{-1} {\bar H}_{t}(G_n) > \delta/2\bigr) \le \dfrac \epsilon 2. \end{equation}

Now (4.8) follows by setting $t = \max\!(t_1, t_2)$ and combining (4.7), (4.9), and (4.10).

Proof of Lemma 4.4. Let $Z_1, Z_2, \ldots \sim D_2^* - 1$ and $D_1$ be independent. For a random variable X with ${\mathbb{E}} X \in (0, \infty)$ and its size-biased version $X^*$ , we have

\begin{align*} {\mathbb{E}} (X^*-1)_j = \sum_{m \ge 1} (m-1)_j \dfrac{m {\mathbb{P}}(X=m)} {{\mathbb{E}} X} = \dfrac{ {\mathbb{E}} (X)_{j+1}} {{\mathbb{E}} X}, \quad j = 1, 2, \ldots . \end{align*}

Thus, using the assumptions and Remark 3.1,

(4.11) \begin{equation} {\mathbb{E}} (Z_1)_j = {\mathbb{E}} (D_2)_{j+1} ({\mathbb{E}} D_2)^{-1} < \infty \quad \text{for } j=1, \ldots, k. \end{equation}

Similarly ${\mathbb{E}} Z_1^k = ({\mathbb{E}} D_2)^{-1} {\mathbb{E}} D_2^{k+1} < \infty$ . Write

\begin{align*} \binom k {k_1, \ldots, k_j} = \dfrac {k!} {k_1! \cdots k_j!}. \end{align*}

Conditioning on $D_1$ , using linearity of expectation and symmetry, we get

(4.12) \begin{align} {\mathbb{E}} (d^*)^k &= {\mathbb{E}} \Biggl(\sum_{i=1}^{D_1} Z_i\Biggr)^k \notag \\ & = \sum \binom {k} {k_1, \ldots, k_j} {\mathbb{E}} \binom {D_1} {j} {\mathbb{E}} Z_1^{k_1} \times \cdots \times {\mathbb{E}} Z_j^{k_j} \in (0,\infty). \end{align}

Here the sum is over all j and all tuples of positive integers $(k_1, \ldots, k_j)$ such that $k_1 + \cdots + k_j = k$ . Write $d_n = d_{G_n}(v^*_n)$ and recall that $v^*_n$ is a uniformly random vertex from $V(G_n)$ . By Theorem 3.1 ${\mathcal L}((G_n,v^*_n)\mid G_n) \,\xrightarrow{p}\, {\mathcal L}(G^*)$ , so $d_n^k \xrightarrow{d} (d^*)^k$ . By Fatou’s lemma,

\begin{align*} {\mathbb{E}} (d^*)^k \le \lim \inf {\mathbb{E}} d_n^k. \end{align*}

We assume without loss of generality that in case (iv) the sequences $d_1(n)$ and $d_2(n)$ (not to be confused with the random variable $d_n$ ) are symmetric random permutations of two fixed-degree sequences (each permutation of a particular sequence is equally likely). So in all cases (i)–(iv) by symmetry ${\mathbb{E}} d_{G_n}(v_1)^k = {\mathbb{E}} d_n^k$ , where $v_1$ is a fixed vertex in $V(G_n)$ . For each of the random intersection graph models we will show

(4.13) \begin{equation} {\mathbb{E}} d_{G_n}(v_1)^k \le {\mathbb{E}} (d^*)^k + {\mathrm{o}} (1). \end{equation}

Let ${\mathcal T} \sim {\mathcal T}(D_1,D_2)$ . Assume that $D_1 = d_{\mathcal T}(\mathrm{root}({\mathcal T}))$ , $x_1, \ldots, x_{D_1}$ are the children of $\mathrm{root}({\mathcal T})$ and $Z_i$ is the number of children of $x_i$ . For each n define a bipartite graph (a tree) $\tilde{H}_n$ as follows. On the event $D_1 > n_2$ , let $\tilde{H}_n$ be a tree consisting of just the root $\tilde{v}_1$ . On the event $D_1 \le n_2$ , let $\tilde{H}_n$ be the subtree induced by generations 0, 1 and 2 of ${\mathcal T}$ , but take only the first $Z^{\prime}_i = Z_i {\mathbb I}_{Z_i \le n_1 -1}$ children for the node $x_i$ , $i = 1, \ldots, D_1$ . Label the root $v_1$ . Given $D_1, Z_1, \ldots, Z_{D_1}$ , draw labels for $x_1, \ldots, x_{D_1}$ from ${V^{2}}$ uniformly at random without replacement and draw $Z^{\prime}_i$ distinct labels from ${V^{1}} \setminus \{v_1\}$ for the children of $x_i$ $i=1,\ldots,D_1$ , for each i (conditionally) independently. Here ${V^{i}} = V_i(H_n)$ is the set of first $n_i$ vertices of the fixed ground set ${\mathcal V}^i$ as in Theorem 3.1.

Write $\tilde{d}_n = {\mathbb I}_{D_1 \le n_2} \sum_{i=1}^{D_1} Z^{\prime}_i$ and notice that ${\tilde d}_n$ is an upper bound on the degree of $v_1$ in the resulting intersection graph. We have, as in (4.12),

(4.14) \begin{align} {\mathbb{E}} {\tilde d}_n^k \notag &= \sum \binom k {k_1, \ldots, k_j} {\mathbb{E}} \binom {D_1} j {\mathbb I}_{D_1 \le n_2} {\mathbb{E}} (Z^{\prime}_1)^{k_1}\times \cdots \times {\mathbb{E}} (Z^{\prime}_t)^{k_t} \\ &= {\mathbb{E}} (d^*)^k - {\mathrm{o}} (1). \end{align}

Here we used (4.11), (4.12) and bounds

\begin{align*} {\mathbb{E}} (D_1)_j {\mathbb I}_{D_1 \le n_2} = {\mathbb{E}} (D_1)_j - {\mathrm{o}} (1), \quad {\mathbb{E}} (Z^{\prime}_1)^j = {\mathbb{E}} Z_1^j - {\mathbb{E}} Z_1^j {\mathbb I}_{Z_1 > n_1 -1} = {\mathbb{E}} Z_1^j - {\mathrm{o}} (1), \end{align*}

valid for any $j \le k$ by Lemma 2.1. Thus it suffices to prove that ${\mathbb{E}} d_{G_n}(v_1)^k \le {\mathbb{E}} {\tilde d}_n^k + {\mathrm{o}} (1)$ . Recall that $H_n$ is the bipartite graph underlying the intersection graph $G_n$ . Call a path xyz good if $x = v_1$ , $y \in {\mathcal V}_2$ and $z \in {\mathcal V}_1 \setminus \{v_1\}$ . We have

\begin{align*}d_{G_n}(v_1) \le \sum {\mathbb I}(v_1 w v, H_n) \quad \text{and}\quad {\tilde d}_n = \sum {\mathbb I}(v_1 w v, {\tilde H}_n)\end{align*}

where the sum is over all good paths $v_1 w v$ and ${\mathbb I}(F, H)$ is the indicator of the event that $F \subseteq E(H)$ .

For any graph H we denote $v(H) = |V(H)|$ and $e(H) = |E(H)|$ . If H is bipartite (more precisely, 2-coloured), $v_j(H)$ , $j=1, 2$ denotes the size of jth part $V_j$ of H. Define an equivalence relation between bipartite graphs $H^{\prime} = (V^{\prime}_1, V^{\prime}_2, E^{\prime})$ , $H^{\prime\prime} = (V^{\prime\prime}_1, V^{\prime\prime}_2, E^{\prime\prime})$ : $H^{\prime} \sim H^{\prime\prime}$ if and only if there is an isomorphism from H ′ to H ^′′ that maps $V^{\prime}_j$ to $V^{\prime\prime}_j$ , $j=1,2$ . Let ${\mathcal{F}}_k$ consist of one member for each equivalence class of all graphs formed from a union of k good paths (a not necessarily disjoint union of graphs $G_1 = (V_1, E_1), \ldots, G_k = (V_k, E_k)$ is a graph $(V_1 \cup \cdots \cup V_k, E_1 \cup \cdots \cup E_k)$ ). For $H^{\prime} \in {\mathcal{F}}_k$ , let N(H ′) be the number of distinct tuples of k good paths whose union is a bipartite graph H ^′′ with parts $V^{\prime\prime}_1 \subseteq {V^{1}}$ and $V^{\prime\prime}_2 \subseteq {V^{2}}$ such that $H^{\prime\prime} \sim H^{\prime}$ . It is easy to see that there are positive constants c(H ′), C(H ′) such that, for all n large enough,

(4.15) \begin{equation}N(H^{\prime}) = c(H^{\prime}) (n_1)_{v_1(H^{\prime})-1} (n_2)_{v_2(H^{\prime})} = C(H^{\prime}) n_1^{v(H^{\prime}) - 1} (1 + {\mathrm{o}} (1)).\end{equation}

By linearity of expectation,

\begin{align*}&{\mathbb{E}} d_{G_n}(v_1)^k \le {\mathbb{E}} \Bigl(\sum {\mathbb I}(v_1 w v, H_n)\Bigr)^k =\sum_{H^{\prime} \in {\mathcal{F}}_k} N(H^{\prime}) {\mathbb{E}} {\mathbb I}(H^{\prime}, H_n),\end{align*}

and similarly

\begin{align*}{\mathbb{E}} {\tilde d}_n^k = \sum_{H^{\prime} \in {\mathcal{F}}_k} N(H^{\prime}) {\mathbb{E}} {\mathbb I}(H^{\prime}, {\tilde H}_n).\end{align*}

Using (4.14), (4.15) and the fact that ${\mathcal{F}}_k$ is finite, in order to prove (4.13) it suffices to check that

(4.16) \begin{equation}{\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) \le {\mathbb{E}} {\mathbb I}(H^{\prime}, \tilde{H}_n) + {\mathrm{o}} \bigl(n_1^{-v(H^{\prime})+1}\bigr) \quad \text{for each } H^{\prime} \in {\mathcal{F}}_k.\end{equation}

So fix any $H^{\prime} \in {\mathcal{F}}_k$ . Suppose $v_2(H^{\prime}) = t$ and the degrees of vertices in $V_2(H^{\prime})$ are $b_1, \ldots, b_t$ . Note that $b_j \le k+1$ for $j = 1, \ldots, t$ . Conditioning on $D_1$ and the positions of generation 1 nodes labelled $V_2(H^{\prime})$ and using (4.11)

(4.17) \begin{align}{\mathbb{E}} {\mathbb I}(H^{\prime}, {\tilde H}_n) &= {\mathbb{E}} \dfrac {(D_1)_t {\mathbb I}_{D_1 \le n_1}} {(n_2)_t} \dfrac{(Z^{\prime}_1)_{b_1-1}} {(n_1 - 1)_{b_1-1}} \times \cdots \times\dfrac{(Z^{\prime}_t)_{b_t-1}} {(n_1 - 1)_{b_t-1}} \notag\\ &= n_2^{-t} n_1^{-e(H^{\prime}) + t} {\mathbb{E}} (D_1)_t \prod_{i=1}^t {\mathbb{E}} (Z^{\prime}_i)_{b_i-1} (1+{\mathrm{o}} (1)) \notag\\ &= \beta^{-t} n_1^{-e(H^{\prime})} {\mathbb{E}} (D_1)_t ({\mathbb{E}} D_2)^{-t} \prod_{i=1}^t {\mathbb{E}} (D_2)_{b_i} (1+{\mathrm{o}} (1)).\end{align}

Now if H ′ is a tree then $e(H^{\prime}) = v(H^{\prime})-1$ , and (4.16) follows if

(4.18) \begin{equation} {\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) \le {\mathbb{E}} {\mathbb I}(H^{\prime}, \tilde{H}_n) (1 + {\mathrm{o}} (1)).\end{equation}

Meanwhile, if H ′ has a cycle then $e(H^{\prime}) \ge v(H^{\prime})$ and ${\mathbb{E}} {\mathbb I}(H^{\prime}, {\tilde H}_n) = {\mathrm{O}} \bigl(n_1^{-v(H^{\prime})}\bigr)$ , so (4.16) follows whenever

(4.19) \begin{equation}{\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) = {\mathrm{o}} \bigl(n^{-v(H^{\prime})+1}\bigr).\end{equation}

We now consider (4.16) for each model separately.

(i) Active intersection graph. Let $a_1, \ldots, a_s$ be the degrees of vertices in $V_1(H^{\prime})$ . We can assume $a_1 = d_{H^{\prime}}(v_1) = t$ . Of course, $a_j \le k$ , $j = 1, \ldots, s$ . Since the vertices in $V_1(H^{\prime})$ choose their neighbours independently, using Lemma 2.1,

\begin{align*}{\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) = {\mathbb{E}} \prod_{i=1}^s \dfrac { (X_v)_{a_i}} { (n_2)_{a_i}} = n_2^{-e(H^{\prime})} \prod_{i=1}^s {\mathbb{E}} (D_1)_{a_i} (1 + {\mathrm{o}} (1)).\end{align*}

If H ′ has a cycle then $e(H^{\prime}) \ge v(H^{\prime})$ and ${\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) = {\mathrm{O}} \bigl(n_1^{-e(H^{\prime})}\bigr)$ , so (4.19) holds.

By Remark 3.1, $D_2 \sim \operatorname{Po} (\beta^{-1} {\mathbb{E}} D_1)$ . So ${\mathbb{E}} (D_2)_{b_i} = (\beta^{-1} {\mathbb{E}} D_1)^{b_i}$ . Thus (4.17) reduces to

\begin{align*}{\mathbb{E}} {\mathbb I}(H^{\prime}, {\tilde H}_n) = (\beta n_1)^{-e(H^{\prime})} {\mathbb{E}} (D_1)_t ({\mathbb{E}} D_1)^{e(H^{\prime}) - t} (1 + {\mathrm{o}} (1))\end{align*}

If H ′ has no cycle, then $a_j = 1$ for all $j \ge 2$ . Thus

\begin{align*}{\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) &\le n_2^{-e(H^{\prime})} {\mathbb{E}} (D_1)_t ({\mathbb{E}} D_1)^{e(H^{\prime})-t} (1 + {\mathrm{o}} (1))\end{align*}

and (4.19) follows.

(ii) Passive intersection graph. Since $b_i \le k+1$ for $i = 1, \ldots, t$ by assumption (ii) of the lemma,

\begin{align*}{\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) = {\mathbb{E}} \prod_{i=1}^s \dfrac { (X_v)_{b_i}} {(n_1)_{b_i}} = n_1^{-e(H^{\prime})} \prod_{i=1}^s {\mathbb{E}} (D_2)_{b_i} (1 + {\mathrm{o}} (1)).\end{align*}

Using Remark 3.1, $D_1 \sim \operatorname{Po} (\beta {\mathbb{E}} D_2)$ , so ${\mathbb{E}} (D_1)_t = \beta^t ({\mathbb{E}} D_2)^t$ . Therefore (4.17) reduces to

\begin{align*}{\mathbb{E}} {\mathbb I}(H^{\prime}, {\tilde H}_n) = n_1^{-e(H^{\prime})} \prod_{i=1}^s {\mathbb{E}} (D_2)_{b_i} (1 + {\mathrm{o}} (1))\end{align*}

and (4.16) follows.

(iii) Inhomogeneous random intersection graph. Let $\{\xi_u\,:\, u \in V(H^{\prime})\}$ be independent random variables such that $\xi_u \sim \xi^{(i)}$ for $u \in V_i(H^{\prime})$ , $i = 1, 2$ . Write $a \wedge b = \min(a,b)$ . Then

\begin{align*}{\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) &= {\mathbb{E}} \prod_{uv \in E(H^{\prime})}\biggl( \dfrac {\xi_u \xi_v} {\sqrt{n_1 n_2}} \wedge 1\biggr) \\ &\le \beta^{-e(H^{\prime})/2}n_1^{-e(H^{\prime})} \prod_{u \in V(H^{\prime})} {\mathbb{E}} \xi_u^{d_{H^{\prime}}(u)} (1 + {\mathrm{o}} (1)).\end{align*}

If H ′ contains a cycle, then by the assumption that ${\mathbb{E}} (\xi^{(1)})^k$ and ${\mathbb{E}} (\xi^{(2)})^{k+1}$ are finite, we get that ${\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) = {\mathrm{O}} \bigl(n_1^{-v(H^{\prime})}\bigr)$ , so (4.19) holds. If H ′ is a tree then

(4.20) \begin{equation}{\mathbb{E}} {\mathbb I}(H^{\prime}, H_n) \le \beta^{-e(H^{\prime})/2} n_1^{-e(H^{\prime})} {\mathbb{E}} \bigl(\xi^{(1)}\bigr)^t \bigl({\mathbb{E}} \xi^{(1)}\bigr)^{s-1} \prod_{j=1}^t {\mathbb{E}} \bigl(\xi^{(2)}\bigr)^{b_j} (1 + {\mathrm{o}} (1)).\end{equation}

Using Remark 3.1, we have $D_1 \sim \operatorname{Po} \bigl(\beta^{1/2} \xi^{(1)} {\mathbb{E}} \xi^{(2)}\bigr)$ and $D_2 \sim \operatorname{Po} \bigl(\beta^{-1/2} \xi^{(2)} {\mathbb{E}} \xi^{(1)}\bigr)$ , so ${\mathbb{E}} (D_1)_t = \beta^{t/2} {\mathbb{E}} (\xi^{(1)}) ^ t ({\mathbb{E}} \xi^{(2)})^t$ and ${\mathbb{E}} (D_2)_j = \beta^{-j/2} {\mathbb{E}} (\xi^{(2)}) ^ j ({\mathbb{E}} \xi^{(1)})^j$ for $j \le k+1$ . Putting these estimates into (4.17) and simplifying, we get the expression on the right-hand side of (4.20). Then (4.18) follows.

(iv) Random configuration graph. For $i = 1, 2$ , let

\begin{align*} \tilde{d}_{i, m} = n_i^{-1} \sum_{v \in {V^{i}}} (d_{i,v})_m. \end{align*}

Recall that $N = \sum_{u \in {V^{1}}}^{n_1} d_{1,u}$ is the total number of half-edges in each of the parts. Since $n_1, n_2 \to \infty$ and by the assumption of the lemma $N n_1^{-1} \to {\mathbb{E}} D_1$ , there exists $\omega_n \to \infty$ such that for all n

(4.21) \begin{equation} n_1,n_2, N \ge \omega_n, \quad \omega_n \ge k+2. \end{equation}

The probability that $H_n$ contains H ′ as a subgraph is at most

\begin{align*} a(H^{\prime}) = \dfrac {1} {(N)_{e(H^{\prime})}} {\mathbb{E}} \prod_{u \in V(H^{\prime})} (d_{H_n}(u))_{d_{H^{\prime}}(u)}. \end{align*}

Here the product counts the number of ways to choose particular half-edges forming H ′. Let $(u_1^*, \ldots, u_s^*)$ and $(w_1^*, \ldots, w_t^*)$ be independent uniformly random tuples of distinct vertices from $V_1(H_n)$ and $V_2(H_n)$ respectively. Using symmetry, (4.21), and the assumption of the lemma,

\begin{align*} a(H^{\prime}) & = \dfrac {1} {(N)_{e(H^{\prime})}} {\mathbb{E}} \prod_{i=1}^s \bigl(d_{1,u_i^*}\bigr)_{a_i} \prod_{j=1}^t \bigl(d_{2,w_j^*}\bigr)_{b_j} \\ & \le \dfrac {1} {(N)_{e(H^{\prime})}} \prod_{i=1}^s \tilde{d}_{1, a_i} \prod_{j=1}^t \tilde{d}_{2, b_j}(1 + {\mathrm{o}} (1)) \\ & = ({\mathbb{E}} D_1 n_1)^{-e(H^{\prime})} \prod_{i=1}^s {\mathbb{E}} (D_1)_{a_i} \prod_{j=1}^t {\mathbb{E}} (D_2)_{b_j} (1+{\mathrm{o}} (1)). \end{align*}

Again, if H ′ has a cycle then (4.19) follows. Otherwise, if H ′ is a tree, then since ${\mathbb{E}} D_1 n_1 = {\mathbb{E}} D_2 n_2 (1+{\mathrm{o}} (1))$ we have ${\mathbb{E}} D_1 = \beta {\mathbb{E}} D_2$ and

\begin{align*} ({\mathbb{E}} D_1)^{-e(H^{\prime})} \prod_{i=1}^s {\mathbb{E}} (D_1)_{a_i} = {\mathbb{E}} (D_1)_t \dfrac { ({\mathbb{E}} D_1) ^{s-1}} { ({\mathbb{E}} D_1)^{s+t-1}} = \beta^{-t} {\mathbb{E}} (D_1)_t ({\mathbb{E}} D_2)^{-t}. \end{align*}

By comparing a(H ′) with (4.17), we see that (4.18) holds.