Sparse random graphs with clustering

Introduction and results

In , a very general model for sparse random graphs was introduced, corresponding to an inhomogeneous version of $G(n,c/n)$, and many properties of this model were determined, in particular, the critical point of the phase transition where the giant component emerges. Part of the motivation was to unify many of the new random graph models introduced as approximations to real-world networks. Indeed, the model of includes many of these models as exact special cases, as well as the ‘mean-field’ simplified versions of many of the more complicated models. (The original forms are frequently too complex for rigorous mathematical analysis, so such mean-field versions are often studied instead.) Unfortunately, there are many models with key features that are not captured by their mean-field versions, and hence not by the model of . The main problem is that many real-world networks exhibit clustering: for example, while there are $n$ vertices and only $5n$ edges, there may be $10n$ triangles, say. In contrast, the model of , like $G(n,c/n)$, produces graphs that contain essentially no triangles or short cycles.

Most models introduced to approximate particular real-world networks turn out to be mathematically intractable, due to the dependence between edges. Nevertheless, many such models have been studied; as this is not our main focus, let us just list a few examples of early work in this field. One of the starting points in this area was the (homogeneous) ‘small-world’ model of Watts and Strogatz . Another was the observation of power-law degree sequences in various networks by Faloutsos, Faloutsos and Faloutsos , among others. Of the new inhomogeneous models, perhaps the most studied is the ‘growth with preferential attachment’ model introduced in an imprecise form by Barabási and Albert , later made precise as the ‘LCD model’ by Bollobás and Riordan . Another is the ‘copying’ model of Kumar, Raghavan, Rajagopalan, Sivakumar, Tomkins and Upfal , generalized by Cooper and Frieze , among others. For (early) surveys of work in this field see, for example, Barabási and Albert , Dorogovtsev and Mendes , or Bollobás and Riordan .

Roughly speaking, any sparse model with clustering must include significant dependence between edges, so one might expect it to be impossible to construct a general model of this type that is still mathematically tractable. However, it turns out that one can do this. The model that we shall define is essentially a generalization of that in , although we shall handle certain technicalities in a different way here.

Let us set the scene for our model. By a type space we simply mean a probability space $({\mathcal{S}},\mu)$. Often, we shall take ${\mathcal{S}}=$ or $(0,1]$ with $\mu$ Lebesgue measure. Sometimes we consider ${\mathcal{S}}$ finite. As will become clear, any model with ${\mathcal{S}}$ finite can be realized as a model with type space $$, but sometimes the notation will be simpler with${\mathcal{S}}$finite. More generally, as shown in , every instance of the random graph model we are going to describe can be realized as an equivalent model with type space$$. Hence, when it comes to proofs, we lose no generality by taking${\mathcal{S}}=$, but we usually prefer allowing an arbitrary type space, which is more flexible for applications. For example, as with the model in , type spaces such as${\mathcal{S}}=^{2}$ are likely to be useful for geometric applications, as in .

Let ${\mathcal{F}}$ consist of one representative of each isomorphism class of finite connected graphs, chosen so that if $F\in{\mathcal{F}}$ has $r$ vertices then $V(F)=[r]=\{1,2,\ldots,r\}$. Given $F\in{\mathcal{F}}$ with $r$ vertices, let $\kappa_{F}$ be a measurable function from ${\mathcal{S}}^{r}$ to $[0,\infty)$; we call $\kappa_{F}$ the kernel corresponding to $F$. A sequence ${\undertilde{\kappa}}=(\kappa_{F})_{F\in{\mathcal{F}}}$ is a kernel family. In our results we shall impose an additional integrability condition on ${\undertilde{\kappa}}$, but this is not needed to define the model.

Let ${\undertilde{\kappa}}$ be a kernel family and $n$ an integer; we shall define a random graph $G(n,{\undertilde{\kappa}})$ with vertex set $[n]=\{1,2,\ldots,n\}$. First let $x_{1},x_{2},\ldots,x_{n}\in{\mathcal{S}}$ be i.i.d. (independent and identically distributed) with the distribution $\mu$. Given ${\bf x}=(x_{1},\ldots,x_{n})$, construct $G(n,{\undertilde{\kappa}})$ as follows, starting with the empty graph. For each $r$ and each $F\in{\mathcal{F}}$ with $|F|=r$, and for every $r$-tuple of distinct vertices $(v_{1},\ldots,v_{r})\in[n]^{r}$, add a copy of $F$ on the vertices $v_{1},\ldots,v_{r}$ (with vertex $i$ of $F$ mapped to $v_{i}$) with probability

all these choices being independent. If $p>1$, then we simply add a copy with probability $1$. We shall often call the added copies of the various $F$ that together form $G(n,{\undertilde{\kappa}})$ atoms since, in our construction of $G(n,{\undertilde{\kappa}})$, they may be viewed as indivisible building blocks. Sometimes we refer to them as small graphs, although there is in general no bound on their sizes. Usually we think of $G(n,{\undertilde{\kappa}})$ as a simple graph, in which case we simply replace any multiple edges by single edges. Typically there will be very few multiple edges, so this makes little difference.

Note that we assume that the atoms of $G(n,{\undertilde{\kappa}})$ are connected. The extension to the case where some atoms may be disconnected is discussed in Section 5.

The reason for dividing by $n^{r-1}$ in (1) is that we wish to consider sparse graphs; indeed, our main interest is the case when $G(n,{\undertilde{\kappa}})$ has $O(n)$ edges. As it turns out, we can be slightly more general; however, when $\kappa_{F}$ is integrable (which we shall always assume), the expected number of added copies of each graph $F$ is $O(n$). Note that all incompletely specified integrals are with respect to the appropriate $r$-fold product measure $\mu^{r}$ on ${\mathcal{S}}^{r}$.

There are several plausible choices for the normalization in (1). The one we have chosen means that if $\kappa_{F}=c$ is constant, then (asymptotically) there are on average $cn$ copies of $F$ in total, and each vertex is on average in $rc$ copies of $F$. An alternative is to divide the expression in (1) by $r$; then (asymptotically) each vertex would on average be in $c$ copies of $F$. Another alternative, natural when adding cliques only but less so in the general case, would be to divide by $r!$; this is equivalent to considering unordered sets of $r$ vertices instead of ordered $r$-tuples. When there is only one kernel, corresponding to adding edges, this would correspond to the normalization used in , and in particular to that of the classical model $G(n,c/n)$; the normalization we use here differs from this by a factor of 2. Yet another normalization would be to divide by $\operatorname{aut}(F)$, the number of automorphisms of $F$; this is equivalent to considering the distinct copies of $F$ in $K_{n}$, which is natural but leads to extra factors $\operatorname{aut}(F)$ in many formulae, and we do not find that the advantages outweigh the disadvantages.

As in , there are several minor variants of $G(n,{\undertilde{\kappa}})$; perhaps the most important is the Poisson multi-graph version of $G(n,{\undertilde{\kappa}})$. In this variant, for each $F$ and each $r$-tuple, we add a Poisson $\operatorname{Po}(p)$ number of copies of $F$ with this vertex set, where $p$ is given by (1), and we keep multiple edges.

Alternatively, we could add a Poisson number of copies and delete multiple edges, which is the same as adding one copy with probability $1-e^{-p}$ and no copy otherwise. More generally, we could add one copy of $F$ with probability $p+o(p)$, and two or more copies with probability $o(p)$. As long as the error terms are uniform over graphs $F$ and $r$-tuples $(v_{1},\ldots,v_{r})$, all our results will apply in this greater generality. Since this will follow by simple sandwiching arguments (after reducing to the ‘bounded’ case; see Definition 2.9), we shall consider whichever form of the model is most convenient; usually this turns out to be the Poisson multi-graph form.

Under certain mild conditions, the results of imply a strong form of asymptotic equivalence between the various versions of the model. For example, if we add copies of $F$ with probability $p+O(p^{2})$, where the implied constant is uniform over $F$ and $(v_{1},\dots,v_{r})$, and

then the resulting model is equivalent to that with probability $p$, in that the two random graphs can be coupled to agree whp; this is a straightforward modification of [30, Corollary 2.13(i)]. Extending the argument in [30, Example 3.2], it can be shown that (2) holds if

This certainly holds for the bounded kernel families (see Definition 2.9) that we consider in most of our proofs, although (2) is easy to verify directly for such kernel families.

In the special case where all $\kappa_{F}$ are zero apart from $\kappa_{K_{2}}$, the kernel corresponding to an edge, we recover (essentially) a special case of the model of ; we call this the edge-only case, since we add only edges, not larger graphs. We write $\kappa_{2}$ for $\kappa_{K_{2}}$. Note that in the edge-only case, given ${\bf x}$, two vertices $i$ and $j$ are joined with probability

The correction term will never matter, so we may as well replace $\kappa_{2}$ by its symmetrized version. In fact, we shall always assume that $\kappa_{F}$ is invariant under the action of the automorphism group $\operatorname{Aut}(F)$ of the graph $F$. In other words, if $\phi:[r]\to[r]$ is a permutation such that $\phi(i)\phi(j)\in E(F)$ if and only if $ij\in E(F)$, then we assume that $\kappa_{F}(\phi(x_{1}),\ldots,\phi(x_{r}))=\kappa_{F}(x_{1},\ldots,x_{r})$ for all $x_{1},\ldots,x_{r}\in{\mathcal{S}}$. In the Poisson version, or if we add copies of graphs $F$ with probability $1-e^{-p}$, the correction terms in (3) and its generalizations disappear: in the edge-only case, given ${\bf x}$, vertices $i$ and $j$ are joined with probability $1-\exp\bigl(-(\kappa_{2}(x_{i},x_{j})+\kappa_{2}(x_{j},x_{i}))/n\bigr)$, and in general we obtain exactly the same random graph if we symmetrize each $\kappa_{F}$ with respect to $\operatorname{Aut}(F)$.

Before proceeding to deeper properties, let us note that the expected number of added copies of $F$ is $(1+O(n^{-1}))n\int_{{\mathcal{S}}^{|F|}}\kappa_{F}$. Unsurprisingly, the actual number turns out to be concentrated about this mean. Let

be the asymptotic edge density of ${\undertilde{\kappa}}$. Since every copy of $F$ contributes $e(F)$ edges, the following theorem is almost obvious, provided we can ignore overlapping edges. A formal proof will be given in Section 7. (A similar result for the total number of atoms is given in Lemma 9.4.)

As in , our main focus will be the emergence of the giant component. By the component structure of a graph $G$, we mean the set of vertex sets of its components, i.e., the structure encoding only which vertices are in the same component, not the internal structure of the components themselves. When studying the component structure of $G(n,{\undertilde{\kappa}})$, the model can be simplified somewhat. Recalling that the atoms $F\in{\mathcal{F}}$ are connected by definition, when we add an atom $F$ to a graph $G$, the effect on the component structure is simply to unite all components of $G$ that meet the vertex set of $F$, so only the vertex set of $F$ matters, not its graph structure. We say that ${\undertilde{\kappa}}$ is a clique kernel family if the only non-zero kernels are those corresponding to complete graphs; the corresponding random graph model $G(n,{\undertilde{\kappa}})$ is a clique model. For questions concerning component structure, it suffices to study clique models. For clique kernels we write $\kappa_{r}$ for $\kappa_{K_{r}}$; as above, we always assume that $\kappa_{r}$ is symmetric, here meaning invariant under all permutations of the coordinates of ${\mathcal{S}}^{r}$. Given a general kernel family ${\undertilde{\kappa}}$, the corresponding (symmetrized) clique kernel family is given by $\bar{{\undertilde{\kappa}}}=(\kappa_{r})_{r\geq 2}$ with

where $\mathfrak{S}_{r}$ denotes the symmetric group of permutations of $[r]$. (This is consistent with our notation $\kappa_{2}=\kappa_{K_{2}}$.) In the Poisson version, with or without merging of parallel edges, the probability of adding some connected graph $F$ on a given set of $r$ vertices is exactly the same in $G(n,{\undertilde{\kappa}})$ and $G(n,\bar{{\undertilde{\kappa}}})$, so there is a natural coupling of these random graphs in which they have exactly the same component structure. In the non-Poisson version, the probabilities are not quite the same, but close enough for our results to transfer from one to the other. Thus, when considering the size (meaning number of vertices) of the giant component in $G(n,{\undertilde{\kappa}})$, we may always replace ${\undertilde{\kappa}}$ by the corresponding clique kernel family.

It is often convenient to think of a clique model as a random hypergraph, with the cliques as the hyperedges; for this reason we call a clique kernel family a hyperkernel. Note that each unordered set of $r$ vertices corresponds to $r!$ $r$-tuples, so the probability that we add a $K_{r}$ on a given set of $r$ vertices is $r!\kappa_{r}(x_{v_{1}},\ldots,x_{v_{r}})/n^{r-1}$. (More precisely, this is the expected number of $K_{r}$s added with this vertex set.)

2 A branching process

Associated to each hyperkernel ${\undertilde{\kappa}}=(\kappa_{r})_{r\geq 2}$, there is a branching process ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ with type space ${\mathcal{S}}$, defined as follows. We start with generation $0$ consisting of a single particle whose type is chosen randomly from ${\mathcal{S}}$ according to the distribution $\mu$. A particle $P$ of type $x$ gives rise to children in the next generation according to a two-step process: first, for each $r\geq 2$, construct a Poisson process $Z_{r}$ on ${\mathcal{S}}^{r-1}$ with intensity

We call the points of $Z=\bigcup_{r\geq 2}Z_{r}$ the child cliques of $P$. There are $r-1$ children of $P$ for each child clique $(x_{2},\ldots,x_{r})\in{\mathcal{S}}^{r-1}$, one each of types $x_{2},\ldots,x_{r}$. Thus the types of the children of $P$ form a multiset on ${\mathcal{S}}$, with a certain compound Poisson distribution we have just described. As usual, the children of different particles are independent of each other, and of the history.

Considering the relationship to the graph $G(n,{\undertilde{\kappa}})$, the initial factor $r$ in (6) arises because a particular vertex $v$ may be any one of the $r$ vertices in an $r$-tuple $(v_{1},\ldots,v_{r})$ on which we add a $K_{r}$.

We also consider the branching processes ${\mathfrak{X}}_{{\undertilde{\kappa}}}(x)$, $x\in{\mathcal{S}}$, defined exactly as ${\mathfrak{X}}_{{\undertilde{\kappa}}}$, except that we start with a single particle of the given type $x$.

3 Two integral operators

We shall consider two integral operators naturally associated to ${\mathfrak{X}}_{{\undertilde{\kappa}}}$. Given any (measurable) $f:{\mathcal{S}}\to$, define $S_{{\undertilde{\kappa}}}(f)$ by

(The factors $r$ in (7) and in the definition of ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ are unfortunate consequences of our choice of normalization.)

Let $P$ be a particle of ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ in generation $t$ with type $x$, and suppose that each particle in generation $t+1$ of type $y$ has some property $\mathcal{Q}$ with probability $f(y)$, independently of the other particles. Given a child clique $(x_{2},\ldots,x_{r})$ of $P$, the bracket in the definition of $S_{{\undertilde{\kappa}}}$ expresses the probability that one or more of the $r-1$ corresponding child particles has property $\mathcal{Q}$. Hence $S_{{\undertilde{\kappa}}}(f)(x)$ is the expected number of child cliques containing a particle with property $\mathcal{Q}$, and, from the Poisson distribution of the child cliques, $\Phi_{{\undertilde{\kappa}}}(f)(x)$ is the probability that there is at least one such clique, i.e., the probability that at least one child of $P$ has property $\mathcal{Q}$.

Let $\rho({\undertilde{\kappa}})$ denote the survival probability of the branching process ${\mathfrak{X}}_{{\undertilde{\kappa}}}$, and $\rho_{\undertilde{\kappa}}(x)$ the survival probability of ${\mathfrak{X}}_{{\undertilde{\kappa}}}(x)$. Assuming for the moment that the function $\rho_{\undertilde{\kappa}}:{\mathcal{S}}\to$ is measurable, from the comments above and the independence built into the definition of ${\mathfrak{X}}_{{\undertilde{\kappa}}}$, we see that the function $\rho_{\undertilde{\kappa}}$ satisfies

Using simple standard arguments as in , for example, it is easy to check that $\rho_{\undertilde{\kappa}}$ is given by the maximum solution to this equation, i.e., the pointwise supremum of all solutions $f:{\mathcal{S}}\to$ to

see Lemma 2.1 below. From the definitions of ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ and ${\mathfrak{X}}_{{\undertilde{\kappa}}}(x)$, it is immediate that

Let us note two simple consequences of this fact. For any sequence $(y_{i})_{i}$ in $$we have${1-\prod_{i}(1-y_{i})}\leq\sum_{i}y_{i}$, so

for any $f:{\mathcal{S}}\to$. Also, ${1-\prod_{i}(1-y_{i})}>0$ if and only if $\sum_{i}y_{i}>0$. Since the integral of a non-negative function is positive if and only if the function is positive on a set of positive measure, it follows that for any $f:{\mathcal{S}}\to$ we have

4 Main results

In most of our results we shall need to impose some sort of integrability condition on our kernel family; the exact condition depends on the context.

(i) A kernel family ${\undertilde{\kappa}}=(\kappa_{F})_{F\in{\mathcal{F}}}$ is integrable if

This means that the expected number of atoms containing a given vertex is bounded.

(ii) A kernel family ${\undertilde{\kappa}}=(\kappa_{F})_{F\in{\mathcal{F}}}$ is edge integrable if

Note that a hyperkernel $(\kappa_{r})$ is integrable if and only if $\sum_{r\geq 2}r\int_{{\mathcal{S}}^{r}}\kappa_{r}<\infty$, and edge integrable if and only if $\sum_{r\geq 2}r^{2}\int_{{\mathcal{S}}^{r}}\kappa_{r}<\infty$.

Since we only consider connected atoms $F$, it is clear that

We are now ready to state our main result; we write $C_{i}$ for the number of vertices in the $i$th largest component of a graph $G$.

Let ${\undertilde{\kappa}}^{\prime}=(\kappa^{\prime}_{F})_{F\in{\mathcal{F}}}$ be an irreducible, integrable kernel family, and let ${\undertilde{\kappa}}=(\kappa_{r})_{r\geq 2}$ be the corresponding hyperkernel, given by (5). Then

The reducible case reduces to the irreducible one; see Remark 4.5.

Unsurprisingly, part of the proof of Theorem 1.5 involves showing that (in the hyperkernel case) the branching process captures the ‘local structure’ of $G(n,{\undertilde{\kappa}})$; see Section 3 and in particular Lemma 3.2. So Theorem 1.5 can be seen as saying that within this broad class of models the local structure determines the size of the giant component. Of course, the restriction is important, as shown by the fact that the global assumption of irreducibility is necessary.

This is perhaps surprising: it tells us that for such uniform hyperkernels, the critical point where a giant component emerges is determined only by the total number of edges added; it does not matter what size cliques they lie in, even though, for example, the third edge in every triangle is ‘wasted’. This is not true for arbitrary kernel families: we must first replace each atom by a clique.

5 Relationship to the results in [10]

In the edge-only case, the present results are almost (see below) special cases of those . The set-up here is much simpler, as we choose to insist that the vertex types $x_{1},\ldots,x_{n}$ are i.i.d. This avoids many of the complications arising in . In one way, the present set-up is, even in the edge-only case, more general than that considered in : with the types i.i.d., there is no need to restrict the kernels other than to assume integrability (in we needed them continuous a.e.), and one does not need to impose the ‘graphicality’ assumption of . Thus the edge-only case here actually complements the results in . We could form a common generalization, but we shall not do this in detail; we believe that it is just a question of combining the various technicalities here and in , and that no interesting new difficulties arise. Of course, these technicalities are rather beside the point of the present paper; our interest is the extension from kernels to hyperkernels. This turns out not to be as straightforward as one might perhaps expect. The problem is that the correlation between edges forces us to deal with a non-linear operator, namely $S_{{\undertilde{\kappa}}}$.

The rest of the paper is organized as follows. In the next section we prove the results about the non-Poisson branching process ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ that we shall need later, the most important of which is Theorem 1.7. In Section 3 we consider the local coupling between the graph and the branching process, showing in particular that the ‘right’ number of vertices are in components of any fixed size. In Section 4 we complete the proof of Theorem 1.5, showing that whp there is at most one ‘large’ component, which is then a ‘giant’ component of the right size. We briefly discuss percolation on the graphs $G(n,{\undertilde{\kappa}})$ in Section 5. In Sections 6 and 7 we consider simpler properties of $G(n,{\undertilde{\kappa}})$, namely the asymptotic degree distribution and the number of subgraphs isomorphic to a given graph. Our results in Section 7 include Theorem 1.3 as a simple special case. In Section 8 we illustrate the flexibility of the model by carrying out explicit calculations for a special case, giving graphs with power-law degree sequences with a range of exponents and a range of clustering and mixing coefficients; see Section 8 for the definitions of these coefficients. Finally, in Section 9 we discuss connections between our model and various notions of graph limit, and state two open questions.

Analysis of the branching process

In this section, which is the heart of the paper, we forget about graphs, and study the (compound Poisson) branching process ${\mathfrak{X}}_{{\undertilde{\kappa}}}$. One might expect the arguments of to carry over mutatis mutandis to the present context, but in the branching process analysis this is very far from the truth; this applies especially to the proof of Theorem 2.4 below.

Throughout the section we work with an integrable hyperkernel ${\undertilde{\kappa}}=(\kappa_{r})_{r\geq 2}$, i.e., we assume that $\int{\undertilde{\kappa}}=\sum_{r}r\int\kappa_{r}<\infty$. Our main aim in this section is to prove Theorem 1.7.

so $\lambda(x)$ is the expected number of child cliques of a particle of type $x$. We have

which is finite by our integrability assumption (13). It follows that $\lambda(x)<\infty$ holds almost everywhere. Changing each kernel $\kappa_{r}$ on a set of measure zero, we may assume that $\lambda(x)$ is finite for all $x$. (Such a change is irrelevant for the branching process and for the graph.) From now on, we thus assume that $\lambda(x)<\infty$ holds for all $x$, for any hyperkernel ${\undertilde{\kappa}}$ we consider.

Since a Poisson random variable with finite mean is always finite, any particle in ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ has a finite number of child cliques, and hence a finite number of children, even though the expected number of children may perhaps be infinite. Hence, the event that the branching process dies out (i.e., that some generation is empty) coincides with the event that it is finite.

Using this fact, we have the following, standard result. Recall that $\rho_{\undertilde{\kappa}}(x)$ denotes the survival probability of the branching process ${\mathfrak{X}}_{{\undertilde{\kappa}}}(x)$ that starts with a single particle of type $x$, and $\rho_{\undertilde{\kappa}}$ denotes the function $x\mapsto\rho_{\undertilde{\kappa}}(x)$ .

The function $\rho_{\undertilde{\kappa}}$ satisfies the functional equation (8). Furthermore, if $f:{\mathcal{S}}\to$ is any other solution to (8), then $0\leq f(x)\leq\rho_{\undertilde{\kappa}}(x)<1$ holds for every $x$.

Let $\rho_{t}(x)$ be the probability that ${\mathfrak{X}}_{{\undertilde{\kappa}}}(x)$ survives for at least $t$ generations, so $\rho_{0}$ is identically $1$. Conditioned on the set of child cliques, and hence children, of the root, each child of type $y$ survives for $t$ further generations with probability $\rho_{t}(y)$. These events are independent for different children by the definition of the branching process, so $\rho_{t+1}=\Phi_{{\undertilde{\kappa}}}(\rho_{t})$. The result follows from the monotonicity of $\Phi_{{\undertilde{\kappa}}}$ and the fact that $\rho_{t}(x)\searrow\rho_{\undertilde{\kappa}}(x)$, noting that $\Phi_{{\undertilde{\kappa}}}(1)(x)=1-e^{-\lambda(x)}<1$ for the strict inequality. ∎

Let us remark for the last time on the measurability of the functions we consider: in the proof above, $\rho_{0}$ is measurable by definition. From the definition of $\Phi_{{\undertilde{\kappa}}}$ and the measurability of each $\kappa_{k}$, it follows by induction that each $\rho_{t}$ is measurable, and hence that $\rho_{\undertilde{\kappa}}$ is. Similar arguments apply in many places later, but we shall omit them.

We next turn to the uniqueness of the non-zero solution (if any) to (8). The key ingredient in establishing this is the following simple inequality concerning the non-linear operator $S_{{\undertilde{\kappa}}}$.

Let ${\undertilde{\kappa}}$ be an integrable hyperkernel, and let $f$ and $g$ be measurable functions on ${\mathcal{S}}$ with $0\leq f\leq g\leq 1$. Then

We may write $S_{{\undertilde{\kappa}}}$ as $\sum_{r\geq 2}S_{r}$, where $S_{r}$ is the non-linear operator corresponding to the single kernel $\kappa_{r}$, so $S_{r}(f)$ is defined by the summand in (7). It suffices to prove that

We shall in fact show that for any (distinct) $x_{1},\ldots,x_{r}\in{\mathcal{S}}$ we have

Since $\kappa_{r}$ is symmetric, (15) follows. (In fact, (15) can be true in general only if (16) always holds, considering the symmetrization of a delta function.) Now (16) can be viewed as an inequality in $2r$ variables $f(x_{1}),\ldots,f(x_{r}),g(x_{1}),\ldots,g(x_{r})$. This inequality is linear in each variable. Furthermore, it is linear in each pair $(f(x_{i})$, $g(x_{i}))$. In proving (16) for any $0\leq f\leq g\leq 1$, we may thus assume that for each $i$ one of three possibilities holds: $0=f(x_{i})=g(x_{i})$, $f(x_{i})=g(x_{i})=1$, or $f(x_{i})=0$ and $g(x_{i})=1$. In other words, we may assume that $f$ and $g$ are $\{0,1\}$-valued.

Suppose then for a contradiction that (16) fails for some $\{0,1\}$-valued $f$ and $g$ with $f\leq g$. Then there must be some permutation $\pi$ such that

which we may take without loss of generality to be the identity permutation. Since both sides of (17) are $\{0,1\}$-valued, the left must be $1$ and the right $0$. Since the left is $1$, we have $f(x_{1})=1$, so, using $f\leq g$, $g(x_{1})=1$. But now for the right hand side of (17) to be 0 the final product in (17) must be $1$, so $f(x_{i})=0$ for $i=2,\ldots,r$, i.e., $f$ takes the value $1$ only once. Of course, $g$ must take the value $1$ at least twice, otherwise we have equality. But now the left hand side of (16) is exactly $(r-1)!$, coming from terms with $\pi(1)=1$ and hence $f(x_{\pi(1)})=1$. The right hand side is at least $(r-1)!$, from any $\pi$ mapping $1$ to some $j\neq 1$ with $g(x_{j})=1$. Hence (16) holds after all, giving a contradiction and completing the proof. ∎

If ${\undertilde{\kappa}}$ is reducible, then (8) may in general have several non-zero solutions. To prove uniqueness in the irreducible case we need to know what irreducibility tells us about $S_{{\undertilde{\kappa}}}$.

If there exists a measurable $f:{\mathcal{S}}\to$ with $0<\mu\{f>0\}<1$ and $\{S_{{\undertilde{\kappa}}}f>0\}\subseteq\{f>0\}$, then ${\undertilde{\kappa}}$ is reducible.

In fact, taking $f$ to be a suitable indicator function, one can check that the converse of Lemma 2.3 also holds.

Using Lemmas 2.2 and 2.3 it is easy to deduce uniqueness of any non-zero solution to (8).

Let ${\undertilde{\kappa}}$ be an irreducible, integrable hyperkernel, and let $f$ and $g$ be solutions to (8) with $0\leq f(x)\leq g(x)\leq 1$ for every $x$. Then either $f=0$ or $f=g$. In particular, the only solutions to (8) are $\rho_{\undertilde{\kappa}}$ and the zero function, which may or may not coincide.

We may suppose that $f$ is not $0$ a.e.; otherwise, $f=\Phi_{{\undertilde{\kappa}}}(f)$ would be identically zero. Since $f$ solves (8), we have $\{f=0\}=\{S_{{\undertilde{\kappa}}}f=0\}$, so by Lemma 2.3 we cannot have $0<\mu\{f>0\}<1$. The only possibility left is that $\mu\{f>0\}=1$, i.e., $f>0$ a.e. Turning to $g$, since ${\undertilde{\kappa}}$ is integrable, we have $S_{{\undertilde{\kappa}}}(g)(x)\leq S_{{\undertilde{\kappa}}}(1)(x)=\lambda(x)<\infty$ for a.e. $x$, and thus $g=\Phi_{{\undertilde{\kappa}}}(g)<1$ a.e.

Since $f$ and $g$ solve (8), we have $S_{{\undertilde{\kappa}}}(f)(x)=-\log(1-f(x))$ and $S_{{\undertilde{\kappa}}}(g)(x)=-\log(1-g(x))$. Hence,

whenever $0\leq f\leq g\leq 1$, with strict inequality whenever $0<f<g$. Since ${\undertilde{\kappa}}$ is integrable, it is immediate from the definition (7) that $S_{{\undertilde{\kappa}}}f$ and $S_{{\undertilde{\kappa}}}g$ are integrable, and it follows that

with strict inequality unless $f=g$ a.e. Since Lemma 2.2 gives the reverse inequality, we have $f=g$ a.e., and thus $f=\Phi_{{\undertilde{\kappa}}}f=\Phi_{{\undertilde{\kappa}}}g=g$. The second statement then follows from Lemma 2.1. ∎

Although simple, the proof of Theorem 2.4 above is a little mysterious from a branching process point of view. It is tempting to think that the result is ‘obvious’, and indeed that a corresponding result should hold for any Galton–Watson process. However, some conditions are certainly necessary, and it is not clear what the right conditions are for a general process. (Irreducibility is always needed, of course.) In , a corresponding result is proved for a general branching process satisfying a certain continuity assumption; the proof uses the convexity property $\Phi(\lambda f)\geq\lambda\Phi(f)$ for any function $0\leq f\leq 1$ and any $0\leq\lambda\leq 1$, which holds for all Galton–Watson branching processes. In Theorem 2.4, continuity is not needed, but some kind of symmetry is; there does not seem to be an obvious common generalization of these results.

Indeed, the next example shows that the situation is not that simple: in the compound Poisson case (as opposed to the simple Poisson case), symmetry of the relevant linear operator is not enough.

Define the non-linear operator $\Phi$ associated to ${\mathfrak{X}}$ in the natural way, so $\Phi(f)(x)$ is the probability that at least one child of the root of type $x$ has a certain property, if each child of type $y$ has this property independently with probability $f(y)$. As before, the survival probability $\rho(x)$ satisfies $\rho=\Phi(\rho)$.

Let $\tau(x)$ denote the probability that the process survives transiently, i.e., survives forever, but, for each $i$, contains in total only finitely many particles of type $i$. Consider the ‘forward process’ given by ignoring backward children. This is simply a Poisson Galton–Watson process with on average 2 offspring, and so survives with some positive probability. Also, given that it survives, there is a positive probability that for every $t$, generation $t$ contains at most $3^{t}$ particles, say. But since the particles in generation $t$ have type $x+t$, the expected number of sets of backwards children of all particles in the forward process is at most $\sum_{t\geq 0}3^{t}4^{-t-1}<\infty$, and with positive probability the particles in the forward process have no backwards children. But in this case, the forward process is the whole process, and the process survives transiently. Hence $\tau(x)>0$ for every $x$.

Let $\sigma(x)=\rho(x)-\tau(x)$ be the probability that the process survives recurrently. Considering the children of the initial particle, we see that $\sigma=\Phi(\sigma)$. The process restricted to any two consecutive types is already supercritical, and so has positive probability of surviving by alternating between these types. Thus $\sigma(x)>0$ for all $x$. We showed above that $\tau(x)=\rho(x)-\sigma(x)>0$ for all $x$, so $0<\sigma(x)<\rho(x)$, and $f=\Phi(f)$ has (at least) two non-zero solutions, namely $\sigma$ and $\rho$.

Lemmas 5.12 and 5.13 of carry over to the present context, with only minor modifications. Given functions $f_{1},f_{2},\ldots$ and $f$, we write $f_{n}\nearrow f$ if the sequence $(f_{n})$ is monotone increasing and converges to $f$ pointwise.

If $0\leq f\leq 1$ and $\Phi_{{\undertilde{\kappa}}}(f)\geq f$, then $\Phi_{{\undertilde{\kappa}}}^{m}(f)\nearrow g$ as $m\to\infty$, for some $1\geq g\geq f$ with $\Phi_{{\undertilde{\kappa}}}(g)=g$.

Since $f\leq\Phi_{{\undertilde{\kappa}}}(f)$, monotonicity of $\Phi_{{\undertilde{\kappa}}}$ gives $\Phi_{{\undertilde{\kappa}}}(f)\leq\Phi_{{\undertilde{\kappa}}}^{2}(f)$ and, by induction, $\Phi_{{\undertilde{\kappa}}}^{m}(f)\leq\Phi_{{\undertilde{\kappa}}}^{m+1}(f)$ for all $m\geq 0$. Since $0\leq\Phi_{{\undertilde{\kappa}}}^{m}(f)\leq 1$, it follows that $g(x)=\lim_{m\to\infty}\Phi_{{\undertilde{\kappa}}}^{m}(f)(x)$ exists for every $x$, and $0\leq g\leq 1$. From monotone convergence we have $S_{{\undertilde{\kappa}}}(g)=\lim_{m\to\infty}S_{{\undertilde{\kappa}}}(\Phi_{k}^{m}(f))$, from which it follows that $\Phi_{{\undertilde{\kappa}}}(g)=g$. ∎

If there is a function $f:{\mathcal{S}}\to$, not a.e. $0$, such that $S_{{\undertilde{\kappa}}}(f)\geq(1+\delta)f$ for some $\delta>0$, then $\rho({\undertilde{\kappa}})>0$.

The proof is the same as that of Lemma 5.13 in , using $S_{{\undertilde{\kappa}}}$ in place of $T_{\kappa}$. ∎

We call a hyperkernel ${\undertilde{\kappa}}=(\kappa_{r})_{r\geq 2}$ bounded if two conditions hold: only finitely many of the $\kappa_{r}$ are non-zero, and each $\kappa_{r}$ is bounded.

Similarly (for later use), a general kernel family $(\kappa_{F})_{F\in{\mathcal{F}}}$ is bounded if only finitely many of the $\kappa_{F}$ are non-zero, and each $\kappa_{F}$ is bounded.

Given a hyperkernel ${\undertilde{\kappa}}=(\kappa_{r})$, for each $M>0$ we let ${{\undertilde{\kappa}}^{M}}$ be the bounded hyperkernel obtained from $\kappa$ by truncating each $\kappa_{r}$, $r\leq M$, at $M$, and replacing $\kappa_{r}$ by a zero kernel for $r>M$. Thus

The truncation ${{\undertilde{\kappa}}^{M}}=(\kappa^{M}_{F})_{F\in{\mathcal{F}}}$ of a general kernel family $(\kappa_{F})_{F\in{\mathcal{F}}}$ is defined similarly, replacing the condition $r\leq M$ by $|F|\leq M$.

We slightly modify the proof of Lemma 5.16 of .

We may assume that $0\leq f\leq 1$. If $0\leq y_{i}\leq\gamma<1$, $i=1,\dots,r$, then (by induction) $1-\prod_{i=1}^{r}(1-y_{i})\geq(1-\gamma)^{r-1}\sum_{i=1}^{r}y_{i}$, and it follows that if $\gamma>0$ is chosen small enough, then

Since $S_{{\undertilde{\kappa}}}(\gamma f)\geq S_{{{\undertilde{\kappa}}^{M}}}(\gamma f)$, the result follows. ∎

Theorem 1.7 follows by combining the results above.

Having proved Theorem 1.7, our next aim is to prove Theorem 1.5. The basic strategy will involve comparing the neighbourhoods of a vertex in the random graph $G(n,{\undertilde{\kappa}})$ with the branching process ${\mathfrak{X}}_{{\undertilde{\kappa}}}$. As in , it will be convenient to carry out the comparison only for certain restricted hyperkernels. In order to deduce results about $G(n,{\undertilde{\kappa}})$ in general, one needs approximation results both for the graph and for the branching process. We now turn to such results for branching processes.

If ${\undertilde{\kappa}}\leq{\undertilde{\kappa}}^{\prime}$, then $\rho({\undertilde{\kappa}})\leq\rho({\undertilde{\kappa}}^{\prime})$. ∎

(i) Let ${\undertilde{\kappa}_{n}}$, $n=1,2,\dots$, be a sequence of hyperkernels on $({\mathcal{S}},\mu)$ increasing a.e. to an integrable hyperkernel ${\undertilde{\kappa}}$. Then $\rho_{{\undertilde{\kappa}_{n}}}\nearrow\rho_{\undertilde{\kappa}}$ a.e. and $\rho({\undertilde{\kappa}_{n}})\nearrow\rho({\undertilde{\kappa}})$.

(ii) Let ${\undertilde{\kappa}_{n}}$, $n=1,2,\dots$, be a sequence of integrable hyperkernels on $({\mathcal{S}},\mu)$ decreasing a.e. to ${\undertilde{\kappa}}$. Then $\rho_{{\undertilde{\kappa}_{n}}}\searrow\rho_{\undertilde{\kappa}}$ a.e. and $\rho({\undertilde{\kappa}_{n}})\searrow\rho({\undertilde{\kappa}})$. ∎

(i) Let ${\undertilde{\kappa}_{n}}$, $n=1,2,\dots$, be a sequence of hyperkernels on $({\mathcal{S}},\mu)$ increasing a.e. to a hyperkernel ${\undertilde{\kappa}}$. Then, for every $k\geq 1$, $\rho_{\geq k}({\undertilde{\kappa}_{n}};x)\nearrow\rho_{\geq k}({\undertilde{\kappa}};x)$ for a.e. $x$ and $\rho_{\geq k}({\undertilde{\kappa}_{n}})\nearrow\rho_{\geq k}({\undertilde{\kappa}})$.

(ii) Let ${\undertilde{\kappa}_{n}}$, $n=1,2,\dots$, be a sequence of integrable hyperkernels on $({\mathcal{S}},\mu)$ decreasing a.e. to ${\undertilde{\kappa}}$. Then, for every $k\geq 1$, $\rho_{\geq k}({\undertilde{\kappa}_{n}};x)\searrow\rho_{\geq k}({\undertilde{\kappa}};x)$ for a.e. $x$ and $\rho_{\geq k}({\undertilde{\kappa}_{n}})\searrow\rho_{\geq k}({\undertilde{\kappa}})$. ∎

The assumption that ${\undertilde{\kappa}_{n}}$ be integrable in Theorems 2.12(ii) and 2.13(ii) can be weakened to $\lambda_{{\undertilde{\kappa}_{n}}}(x)<\infty$ for a.e. $x$, where $\lambda_{{\undertilde{\kappa}_{n}}}(x)$ is the expected number of child cliques in ${\mathfrak{X}}_{{\undertilde{\kappa}_{n}}}$ of a particle of type $x$; see .

Local coupling

We now turn to the local coupling between our random graph and the corresponding branching process, relating the distribution of small components in $G(n,{\undertilde{\kappa}})$ to the branching process ${\mathfrak{X}}_{{\undertilde{\kappa}}}$. In , we were essentially forced to condition on the vertex types, since these were allowed to be deterministic to start with. Here, with i.i.d. vertex types, there is no need to do so. This allows us to couple directly for all bounded hyperkernels, rather than simply for finite type ones.

We shall consider a variant of the usual component exploration process, designed to get around the following problem. When we test edges from a given vertex $v$ to all other vertices, the probability of finding a given edge $vw$ depends on the type of $w$ as well as that of $v$. Hence, not finding such an edge changes the conditional distribution of the type of $w$. If the kernel is well behaved, it is easy to see that this is a small effect. Rather than quantify this, it is easier to embed $G(n,{\undertilde{\kappa}})$ inside a larger random graph with uniform kernels. Testing edges in the larger graph does not affect the conditional distribution of the vertex types; we make this precise below. In doing so, it will be useful to take the hypergraph viewpoint: given a hyperkernel ${\undertilde{\kappa}}$, let $H(n,{\undertilde{\kappa}})$ be the hypergraph on $[n]$ constructed according to the same rules as $G(n,{\undertilde{\kappa}})$, except that instead of adding a $K_{r}$ we add a hyperedge with $r$ vertices. In fact, we consider the Poisson version of the model, allowing multiple copies of the same hyperedge.

Let ${\undertilde{\kappa}}$ be a bounded hyperkernel, and let ${\undertilde{\kappa}}^{+}$ be a corresponding upper bound, so $\kappa^{+}_{r}$ is the constant kernel $M$ for $r\leq R$, and zero for $r>R$, while $\kappa_{r}\leq\kappa^{+}_{r}$ holds pointwise for all $r$.

Taking, as usual, our vertex types $x_{1},\ldots,x_{n}\in{\mathcal{S}}$ to be independent, each having the distribution $\mu$, we construct coupled random (multi-)hypergraphs $H_{n}$ and $H^{+}_{n}$ on $[n]$ as follows: first construct $H^{+}_{n}=H(n,{\undertilde{\kappa}}^{+})$ by taking, for every $2\leq r\leq R$, a Poisson $\operatorname{Po}(r!M/n^{r-1})$ number of copies of each possible $r$-element hyperedge, with all these numbers independent. Although in our formal definition of $H^{+}_{n}$ we first decide the vertex types, $H^{+}_{n}$ is clearly independent of these types. Hence, given $H^{+}_{n}$, the types are (still) i.i.d. with distribution $\mu$.

Given $H^{+}_{n}$ and the i.i.d. types $x_{1},\ldots,x_{n}$ of the vertices, we may form $H_{n}$ by selecting each hyperedge $\{v_{1},\ldots,v_{r}\}$ of $H_{n}^{+}$ to be a hyperedge of $H_{n}$ with probability $\kappa_{r}(x_{v_{1}},\ldots,x_{v_{r}})/M$, independently of all other hyperedges. It is easy to see that this gives the right distribution for $H_{n}=H(n,{\undertilde{\kappa}})$. (If we disallowed multiple copies of an edge, there would be an irrelevant small correction here.)

Turning to the branching processes, there is an analogous coupling of ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ and ${\mathfrak{X}}_{{\undertilde{\kappa}}^{+}}$: first construct ${\mathfrak{X}}_{{\undertilde{\kappa}}^{+}}$, which may be viewed as a single-type process, according to our two-step construction via child cliques. Then assign each particle a type according to the distribution $\mu$, independently of the other particles and of the branching process. Then form the child cliques in ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ by keeping each child clique in ${\mathfrak{X}}_{{\undertilde{\kappa}}^{+}}$ with an appropriate probability depending on the types, deleting not only the children corresponding to deleted child cliques, but also all their descendants.

Let $v\in[n]$ be chosen uniformly at random, independently of $H_{n}$ and $H_{n}^{+}$. Let $\Gamma_{d}$ denote the $d$-neighbourhood of $v$ in $H_{n}$, and $\Gamma_{d}^{+}$ that in $H_{n}^{+}$. Counting the expected number of cycles shows that for any fixed $d$, the hypergraph $\Gamma_{d}^{+}$ is whp treelike. Furthermore, standard arguments as for $G(n,c/n)$ show that one may couple $\Gamma_{d}^{+}$ and the first $d$ generations of ${\mathfrak{X}}_{{\undertilde{\kappa}}^{+}}$ so as to agree in the natural sense whp. When $\Gamma_{d}^{+}$ is treelike, then $\Gamma_{d}\subset\Gamma_{d}^{+}$ may be constructed using exactly the same random deletion process that gives (the first $d$ generations of) ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ as a subset of ${\mathfrak{X}}_{{\undertilde{\kappa}}^{+}}$. It follows that $\Gamma_{d}$ and the first $d$ generations of ${\mathfrak{X}}_{{\undertilde{\kappa}}}$ may be coupled to agree whp.

Recalling that $G(n,{\undertilde{\kappa}})$ and $H_{n}$ have the same components, for any fixed $k\geq 1$ one can determine whether the component containing $v$ has exactly $k$ vertices by examining $\Gamma_{k+1}$. Writing $N_{k}(G)$ for the number of vertices of a graph $G$ that are in components of size $k$, it follows that

As in , starting from two random vertices easily gives a corresponding second moment bound, giving convergence in probability.

Let ${\undertilde{\kappa}}$ be a bounded hyperkernel. Then

Of course it makes no difference whether we work with $N_{k}$ or $N_{\geq k}=n-\sum_{j=1}^{k-1}N_{j}$: Lemma 3.1 also tells us that

The extension to arbitrary hyperkernels is easy from Theorem 2.13.

Let ${\undertilde{\kappa}}$ be an integrable hyperkernel. Then for each fixed $k$ we have

As in , we simply approximate ${\undertilde{\kappa}}$ by bounded hyperkernels. For $M>0$ let ${{\undertilde{\kappa}}^{M}}$ be the truncated hyperkernel defined by (18).

Let $k\geq 1$ be fixed, and let $\varepsilon>0$ be arbitrary. From monotone convergence and integrability,

say. By Theorem 2.13(i), increasing $M$ if necessary, we may also assume that

Since ${{\undertilde{\kappa}}^{M}}\leq{\undertilde{\kappa}}$ holds pointwise, we may couple the hypergraphs $H_{n}^{\prime}$ and $H_{n}$ associated to $G(n,{{\undertilde{\kappa}}^{M}})$ and $G(n,{\undertilde{\kappa}})$ so that $H_{n}^{\prime}\subseteq H_{n}$. Recall that $G(n,{\undertilde{\kappa}})$ is produced from $H_{n}$ by replacing each hyperedge $E$ with $r$ vertices by an $r$-clique. However, as noted earlier, if we form $G_{n}$ from $H_{n}$ by replacing each $E$ by any connected simple graph on the same set of vertices, then $G_{n}$ and $G(n,{\undertilde{\kappa}})$ will have exactly the same component structure, and in particular $N_{\geq k}(G_{n})=N_{\geq k}(G(n,{\undertilde{\kappa}}))$. Let us form $G_{n}$ and $G_{n}^{\prime}$ in this way from $H_{n}$ and $H_{n}^{\prime}$, replacing any hyperedge with $r$ vertices by some tree on the same set of vertices. Recalling that $H_{n}^{\prime}\subseteq H_{n}$, we may of course assume that $G_{n}^{\prime}\subseteq G_{n}$.

Writing $e_{r}(H)$ for the number of $r$-vertex hyperedges in a hypergraph $H$,

Recalling that $G_{n}^{\prime}\subseteq G_{n}$ and noting that adding one edge to a graph cannot change $N_{\geq k}$ by more than $2k$, we see that with probability at least $1-\varepsilon$ we have

The giant component

The local coupling results of the previous section easily give us the ‘right’ number of vertices in large components. As usual, we will pass from this to a giant component by using the ‘sprinkling’ method of Erdős and Rényi , first uncovering the bulk of the edges, and then using the remaining ‘sprinkled’ edges to join up the large components. The following lemma gathers together the relevant consequences of the results in the previous section.

holds whp, where $G_{n}^{\prime}=G(n,(1-\delta){\undertilde{\kappa}})$.

we may and shall assume that $\omega=o(n)$. Since $C_{1}(G_{n})\leq\max\{\omega,N_{\geq\omega}(G_{n})\}$, the first statement of the lemma follows.

For the second, we may of course assume that $\rho({\undertilde{\kappa}})>\varepsilon$; otherwise, there is nothing to prove. As $\delta\to 0$, from Theorem 2.12(i) we have $\rho((1-\delta){\undertilde{\kappa}})\to\rho({\undertilde{\kappa}})$. Fix $\delta>0$ with $\rho((1-\delta){\undertilde{\kappa}})>\rho({\undertilde{\kappa}})-\varepsilon/2$, and let $G_{n}^{\prime}=G(n,(1-\delta){\undertilde{\kappa}})$. Applying (22) to $G_{n}^{\prime}$, there is some $\omega=\omega(n)\to\infty$ such that