Sparse graphs: metrics and random models

Introduction

In a series of papers, Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi (see and the references therein) introduced several natural metrics for graphs, and showed that they are equivalent, in that if $(G_{n})$ is a sequence of graphs with $|G_{n}|\to\infty$, then if $(G_{n})$ is Cauchy with respect to one of these metrics then it is Cauchy with respect to all of them. Moreover, there is a natural completion of the space of graphs with respect to any of these metrics, consisting of (equivalence classes of) graphons, i.e., symmetric measurable functions $\kappa:^{2}\to$. Throughout this paper we assume without loss of generality that $G_{n}$ has $n$ vertices; we do not require $G_{n}$ to be defined for all $n$, but only for a sequence $n_{i}\to\infty$. While the results just mentioned apply to all sequences $(G_{n})$, they are meaningful only for dense graphs, where $e(G_{n})=\Theta(n^{2})$. More precisely, any sequence with $e(G_{n})=o(n^{2})$ converges to the zero graphon.

A different connection between graphs and objects related to graphons arises in the work of Bollobás, Janson and Riordan . Throughout this paper, by a kernel $\kappa$ we shall mean a symmetric integrable function $\kappa:^{2}\to[0,\infty)$; note that graphons are a special case of kernels. Roughly speaking, in an arbitrary kernel $\kappa$ was used to define a sparse inhomogeneous random graph $G(n,\kappa)=G_{1/n}(n,\kappa)$, although the details are rather involved.

When studying, for example, the random graph $G(n,p)$, there are many possibilities for $p$ as a function of $n$; which is most natural depends on what kind of properties one is interested in. Nevertheless, there are two canonical ranges of particular interest: the dense case, $p=\Theta(1)$, and the (extremely) sparse case, $p=\Theta(1/n)$, the minimum sensible density. Here we are not only studying random graphs, but it is still true that the most natural special cases are the densest graphs, those with $\Theta(n^{2})$ edges, studied by Lovász and Szegedy and Borgs, Chayes, Lovász, Sós and Vesztergombi , for example, and the sparsest graphs, those with $\Theta(n)$ edges, as studied by Bollobás, Janson and Riordan . Here we consider the second range, taking $p=p(n)=1/n$ as our normalizing density.

One might expect that graphs with $\Theta(n)$ edges are somehow simpler than denser graphs, but in fact the reverse is often the case, particularly for the random graph $G(n,p)$. As a trivial example, note that there is significant variation in the vertex degrees in $G(n,c/n)$, while the degrees in $G(n,p)$ are concentrated around their mean if $np\to\infty$. For this reason, we expect graphs with $\Theta(n)$ edges to be much harder to work with in the present context, which turns out to be the case. Indeed, as we shall see, hardly any of the results in apply to such graphs.

One advantage of the extremely sparse case is that there is a unique natural normalization: except where explicitly indicated otherwise, in this paper we fix $p=1/n$ as our normalizing function. We shall discuss several metrics in turn, starting with the cut metric. Before doing so, let us recall a few definitions from (for example) .

Throughout this paper, by a kernel we mean an integrable function $\kappa:^{2}\to[0,\infty)$ with $\kappa(x,y)=\kappa(y,x)$ for all $x$, $y$. A rearrangement of a kernel $\kappa$ is any kernel $\kappa^{(\tau)}$ defined by $\kappa^{(\tau)}(x,y)=\kappa(\tau(x),\tau(y))$, where $\tau:\to$ is a measure-preserving bijection. We write $\kappa\approx\kappa^{\prime}$ if there is a rearrangement $\kappa^{(\tau)}$ of $\kappa$ with $\kappa^{\prime}=\kappa^{(\tau)}$ a.e.

A kernel $\kappa$ is of finite type if there is a finite partition $(A_{1},\ldots,A_{n})$ of $$such that$\kappa$is constant on each set$A_{i}\times A_{j}$. Given a graph$G_{n}$with$n$vertices and a normalizing function$p=p(n)$, we write$\kappa_{G_{n}}$for the finite-type kernel associated to$G_{n}$, defined by partitioning$$into$n$intervals$I_{i}$of length$1/n$and setting$\kappa_{G_{n}}$equal to$1/p$on$I_{i}\times I_{j}$if$ij\in E(G_{n})$, and to equal to otherwise. Note that the definition of$\kappa_{G_{n}}$depends on our normalizing function$p=p(n)$.

Given subsets $U$, $W$ of $V(G_{n})$, we write $e(U,W)=e_{G_{n}}(U,W)$ for the number of edges of $G$ from $U$ to $W$, i.e., the number of ordered pairs $(u,w)$ with $u\in U$, $w\in W$ and $uw\in E(G_{n})$. Suppressing the dependence on $G_{n}$, we write

for the normalized density of edges from $U$ to $W$ in $G_{n}$.

As in , given a kernel $\kappa$ and a normalizing function $p=p(n)$, we write $G_{p}(n,\kappa)$ for the random graph defined by choosing vertex types $x_{1},\ldots,x_{n}$ independently and uniformly from $$, and, given these types, joining each pair$\{i,j\}$of vertices with probability$\min\{p\kappa(x_{i},x_{j}),1\}$, independently of all other pairs. When$p=1/n$this is a special case of the sparse inhomogeneous model of Bollobás, Janson and Riordan ; in the sequence$x_{1},\ldots,x_{n}$is not assumed to be i.i.d., so the model there is much more general. On the other hand, in there are certain technical assumptions, including that$\kappa$is continuous almost everywhere. These assumptions are not needed here, since the i.i.d. sequence case is always well behaved; see the discussion in or . When$p=1$and$\kappa$is bounded by$1$, then$G_{p}(n,\kappa)$is what is called a$\kappa$-random graph by Lovász and Szegedy .

Often in what follows we consider sequences $(G_{n})$ of random graphs, i.e., sequences of probability distributions on $n$-vertex graphs. In general, there is no canonical coupling between these distributions for different $n$, so formally we should only consider convergence in probability. However, in many cases the error bounds one obtains are strong enough to give almost sure convergence for any coupling, and one can in any case ensure almost sure convergence by passing to a suitable subsequence. Since the relevant ‘in probability’ notions of (for example) Cauchy sequences are perhaps unfamiliar and distracting, we shall often implicitly fix a coupling and consider almost sure convergence instead.

The cut metric and Szemerédi’s Lemma

Let us briefly recall the definitions of the cut norm of Frieze and Kannan , and the cut metric, defined for kernels and dense graphs by Borgs, Chayes, Lovász, Sós and Vesztergombi , and adapted to sparse graphs in .

where the supremum is over all pairs of measurable subsets of $$. The cut metric is defined for kernels by

where the infimum is over all rearrangements of $\kappa_{2}$. The cut metric is extended to graphs by mapping a graph $G_{n}$ to the corresponding finite-type kernel $\kappa_{G_{n}}$. Note that this mapping depends on the normalizing function $p=p(n)$, so when applying the cut metric to graphs we should more properly speak of the $p$-cut metric. However, all our metrics will depend on the normalizing function $p$, so most of the time we shall not indicate this dependence.

In the dense and intermediate ranges, one of the key results used in the study of the cut metric is some form of Szemerédi’s Lemma . In the extremely sparse setting, there is no way to apply Szemerédi’s Lemma: the ‘bounded density’ assumption considered in [12, Section 4] can only be satisfied if $e(G_{n})=o(n)$, and there is no reasonable way to define an $(\varepsilon,p)$-regular partition so that such a thing exists at all! Correspondingly, many of the nice properties of the cut metric fail when $p=1/n$, as we shall now see.

so $e(G_{n})/n\to\int\kappa/2$. In particular, $G_{n}$ has $\Theta(n)$ edges.

Let $M_{n}$ be a largest matching in $G_{n}$. We claim that there is a constant $c>0$ such that, for $n$ large enough, $M_{n}$ contains at least $cn$ edges. Otherwise, passing to a subsequence, we may assume that $|M_{n}|/n\to 0$. Writing $A_{n}$ for the vertex set of $M_{n}$, and $B_{n}$ for its complement, we have $e(B_{n},B_{n})=0$. Let $X_{n}$ be the subset of $$corresponding to$B_{n}$under the rearrangement$\tau_{n}$. Then, from (3),$\int_{X_{n}\times X_{n}}\kappa\to 0$. Writing$\mu$for Lebesgue measure, we have$\mu(X_{n})=|B_{n}|/n\to 1$, so from basic properties of integration it follows that$\int_{X_{n}\times X_{n}}\kappa\to\int_{^{2}}\kappa$, which is positive by assumption. This contradiction proves the claim.

Fix $c>0$ for which the claim above holds. Since $\kappa$ is integrable, we have $\int\kappa 1_{\{\kappa>C\}}\to 0$ as $C\to\infty$, where $1_{\{\kappa>C\}}:^{2}\to\{0,1\}$ is the indicator function of the event that $\kappa(x,y)>C$. In particular, there is a $C<\infty$ with $\int\kappa 1_{\{\kappa>C\}}\leq c/4$. Fix an $n$ with $n>4C/c$, noting that if $S\subset^{2}$ satisfies $\mu(S)\leq 1/n$, then

Choosing $n$ large enough, we may assume from (3) that there is a $\kappa^{\prime}\approx\kappa$ with

Let $\{u_{1}w_{1},\ldots,u_{r}w_{r}\}$ be a matching in $G_{n}$ with $r\geq cn$; such a matching exists by our claim. Let $U=\{u_{i}\}$ and $W=\{w_{i}\}$. Identifying subsets of $V(G)$ with subsets of $$ in the natural way, from (5) we have

Let $U^{\prime}$ be a random subset of $U$ obtained by selecting each vertex independently with probability $1/2$, and let $W^{\prime}$ be the complementary subset of $W$, defined by $W^{\prime}=\{w_{i}:u_{i}\notin U_{i}\}$. The edges of our matching never appear as edges from $U^{\prime}$ to $W^{\prime}$. On the other hand, any other edge $u_{i}w_{j}$, $i\neq j$, from $U$ to $W$ has probability $1/4$ of appearing. Hence,

Similarly, writing $S\subset^{2}$ for the union of the $r$ $1/n$-by-$1/n$ squares corresponding to the edges $u_{i}w_{i}$, we have

Combining the last three displayed equations using the triangle inequality, and noting that $\mu(S)=r/n^{2}\leq 1/n$, it follows that

always holds, which implies a corresponding upper bound on the difference of the expectations. Since $c/25<c/16$, we obtain a contradiction, completing the proof. ∎

The argument above in fact shows much more.

If $e(G_{n})=o(n)$ then $(G_{n})$ is trivially Cauchy, so we may assume that $(G_{n})$ is Cauchy.

For two graphs $G_{1}$, $G_{2}$ with the same number of vertices, the (normalized) edit distance between $G_{1}$ and $G_{2}$ is the minimum number of edge changes (additions or deletions) needed to turn one of the graphs into a graph isomorphic to the other, divided by $pn^{2}$:

Note that Lemma 2.3 becomes false if the condition that $o(n)$ vertices meet $o(n)$ edges is omitted, as shown by the example mentioned earlier, where $G_{n}$ and $G_{n}^{\prime}$ are two instances of the random graph $G(\sqrt{n},1/2)$, each with $n-\sqrt{n}$ isolated vertices added.

For every $c>1$ there is a $\delta=\delta(c)>0$ such that, if $G_{1}$ and $G_{2}$ are independent instances of $G(n,c/n)$, then whp the unnormalized edit distance between $G_{1}$ and $G_{2}$ is at least $\delta n$.

Let us start with an observation about $G(n,c/n)$. Let $0<a<b$ be constants; we shall estimate the probability of the event $E_{\delta}(H)$ that $G_{2}=G(n,c/n)$ contains all but at most $\delta n$ edges of some graph $H^{\prime}$ isomorphic to $H$, where $H$ is any given graph with $\lfloor an\rfloor$ vertices and at least $bn$ edges, and $\delta<b/2$. There are $\binom{n}{\lfloor an\rfloor}$ choices for the vertex set of $H^{\prime}$, and then at most $\lfloor an\rfloor!$ graphs $H^{\prime}$ with this vertex set isomorphic to $H$. Finally, given $H^{\prime}$, there are crudely at most $\delta n\binom{e(H)}{\delta n}$ choices for the edges of $H^{\prime}$ to omit, while the probability that $G(n,c/n)$ contains the remaining edges is at most $(c/n)^{e(H)-\delta n}$. Hence,

If $a$, $b$ and $\delta$ are constants with $\delta<b-a$, then the final probability is $o(1)$.

Using the results of Bollobás, Janson and Riordan , the proof above may be extended easily to the much more general model $G_{1/n}(n,\kappa)$, although one first needs to decide what the appropriate statement is. As in , let $T_{\kappa}$ be the integral operator associated to $\kappa$, defined by

and let $||T_{\kappa}||$ be its $L^{2}$-norm. Roughly speaking, it was shown in that $G_{1/n}(n,\kappa)$ has a giant component if and only if $||T_{\kappa}||>1$. (There is a slight caveat here: the results of assume that $\kappa$ is continuous almost everywhere; this assumption is only needed due to the more general choice of the vertex types made there. It is easy to see that these results apply to general $\kappa$ if we choose the vertex types i.i.d., as we do in the definition of $G_{1/n}(n,\kappa)$; this is discussed in .)

As shown in [9, Proposition 8.11], the graph $G_{1/n}(n,\kappa)$ satisfies the assumptions of Lemma 2.3. Putting the pieces together, we have thus proved the following result.

Tree counts

Let $F$ be a connected graph which is not a tree. The denominator in the definition of $t_{p}(F,G_{n})$ or $s_{p}(F,G_{n})$ is $\Theta(n^{|F|}p^{e(F)})$, which is order $1$ if $F$ is unicyclic, and tends to zero if $F$ contains two or more cycles. This suggests that, in this range, the parameters $s_{p}(F,\cdot)$ and $t_{p}(F,\cdot)$ make sense only if $F$ is a tree, i.e., that we should take for $\mathcal{A}$ the set $\mathcal{T}$ of (isomorphism classes of) finite trees. Indeed, with $F$ unicyclic, convergence of $s_{p}(F,G_{n})$ simply means that for large $n$, every $G_{n}$ contains the same number of copies of $F$. This condition is very far from the kind of global graph property we are looking for. Since the expected number of copies of a connected graph $F$ in $G(n,c/n)$ tends to infinity if and only if $F$ is tree, roughly speaking we do not expect to see small cycles in graphs with $\Theta(n)$ edges. Of course, there are natural examples of extremely sparse graphs containing many short cycles, but we should handle these differently; see Section 7. For now, we shall consider graphs that, like $G(n,c/n)$, contain few short cycles. More formally, throughout this section we assume that $(G_{n})$ is asymptotically treelike, in the sense that

for any connected $F$ that is not a tree. Under a suitable assumption on the degrees in $G_{n}$, it suffices to impose condition (7) for cycles.

Under the assumption (7), it is easy to see that the parameters $(s_{p}(T,G_{n}))_{T\in\mathcal{T}}$ and $(t_{p}(T,G_{n}))_{T\in\mathcal{T}}$ are essentially equivalent. In particular, up to a $o(1)$ error, for any tree $T$, $t_{p}(T,G_{n})$ can be written as a linear combination of the parameters $s_{p}(T^{\prime},G_{n})$, $|T^{\prime}|\leq|T|$, and vice versa. We shall work with $s_{p}(T,G_{n})$, which is more natural. Adjusting the normalizing constant very slightly, we shall simply set

As in , we assume that the normalized counts of all admissible subgraphs remain bounded. In other words, we shall assume that

for each tree $T$. In fact, it will be convenient to make the stronger assumption that the tree counts are exponentially bounded, i.e., that there is a constant $C$ such that

for every tree $T$. For example, taking $T$ to be a star, this condition implies that the $k$th moment of the degree of a random vertex of $G_{n}$ is at most $C^{k}+o(1)$ as $n\to\infty$. As in , writing $\mathcal{F}$ for the set of isomorphism classes of finite graphs, and enumerating the set $\mathcal{T}$ of isomorphism classes of finite trees as $T_{1},T_{2},\ldots$, define a map

In this section, the main questions we shall consider are: which points $X$ of $^{\mathcal{T}}$ are realizable as limits of sequences $(s_{p}(G_{n}))$, where $(G_{n})$ is asymptotically treelike and has bounded tree counts, and how do these limit points relate to kernels? In fact, we shall reformulate these questions slightly.

We start with some simple observations. First note that if $(G_{n})$ is asymptotically treelike, then

(The $o(1)$ correction appears because of the possibility that the $t+1$ neighbourhood of a random vertex $v$ contains a cycle while the $t$ neighbourhood does not.) Using $L^{1}$ convergence, it follows that

More generally, consider the following two ways of picking a (not uniformly) random vertex of $G_{n}$. (A) pick a vertex $v$ with probability proportional to its degree. (B) pick a vertex $w$ with probability proportional to its degree, then choose an edge incident with $w$ uniformly, and let $v$ be the other end of this edge. It is easy to see that (A) and (B) give the same distribution for the vertex $v$ - indeed, we are simply choosing an edge $e$ of $G$ at random, and then picking an end of $e$ at random. In (B) we ‘change our minds’ after picking the random end, which makes no difference. The equivalence of (A) and (B) gives rise to a consistency condition on our distributions $\pi$.

Using the equivalence of the procedures (A) and (B) above for picking a random vertex of $G_{n}$, it is easy to see that if $\pi$ arises as the local limit of one of our sequences $(G_{n})$, then $\pi$ is shift invariant, in that ${\widetilde{\pi}}^{*}={\widetilde{\pi}}$. It is tempting to believe that this condition is sufficient, but in fact, as pointed out to us by Gábor Elek, this is not the case, as we shall now explain.

An infinite graph is called quasi-transitive if the action of its automorphism group on the vertex set induces a finite number of orbits, i.e., if there are only finitely many different ‘types’ of vertices in the graph. A quasi-transitive tree may be described by a square matrix $A=(a_{ij})$ specifying, for each $i$ and $j$, the number of type-$j$ neighbours each vertex of type $i$ has. Also, given any square matrix $A$ with non-negative integer entries in which $a_{ij}>0$ if and only if $a_{ji}>0$, one can construct a corresponding quasi-transitive tree. (This correspondence is not one-to-one; it may be that vertices corresponding to different rows of $A$ end up having the same type. For example, if each row of $A$ has the same sum $d$, then $T$ is simply the $d$-regular tree. It is easy to describe conditions on $A$ under which this kind of ‘collapse’ does not happen.)

A non-unimodular tree. Let $T$ be the infinite (unrooted) tree corresponding to the matrix

Thus vertices in $T$ have degree 2, 3 or 4, each vertex has one neighbour of the ‘next’ degree (where $2$ follows $4$), and 1, 2 or 3 neighbours of the previous degree. There are three rooted trees corresponding to $T$; let us call these $T_{2}$, $T_{3}$ and $T_{4}$, where the root of $T_{i}$ has degree $i$.

A little calculation shows that taking $\pi_{2}=9/20$, $\pi_{3}=7/20$ and $\pi_{4}=4/20$ gives a shift-invariant distribution supported on $\{T_{2},T_{3},T_{4}\}$, so this shift-invariant distribution is not a local limit.

The reason for the terminology ‘non-unimodular’ above will become clear in Section 7. A different example of a non-unimodular tree is given in Example 3.1 of Benjamini, Lyons, Peres and Schramm , corresponding to the matrix

where the expectation is over the choice of a random rooted tree $(T,x)$ with distribution $\pi$. The argument is as above so let us just outline it: let $(G_{n})$ be a sequence of finite graphs converging to $\pi$ in the appropriate sense. In each $G_{n}$, draw a directed edge from a vertex $x$ to a neighbour $y$ if and only if $(\Gamma_{\leq t}(x),x,y)\in A$, where $\Gamma_{\leq t}(x)$ is the $t$-neighbourhood of $x$ in $G_{n}$. Now the limiting fraction of vertices of $G_{n}$ whose $t$-neighbourhood has a certain form is given by $\pi$. It follows that the expected out-degree of a random vertex of $G_{n}$ converges to the left-hand side of (8). On the other hand, the limiting fraction of vertices of $G_{n}$ whose $(t+1)$-neighbourhood has a certain form is again given by $\pi$. From the $(t+1)$-neighbourhood of $x$ one can obtain the $t$-neighbourhood of each neighbour $y$ of $x$, and thus decide whether we drew an edge from $y$ to $x$. It follows that the expected in-degree converges to the right-hand side of (8). Since in any finite directed graph, the average out- and in-degrees are equal, (8) follows.

where the expectation is over the $\pi$-random rooted tree $(T,x)$, and the sum is over all neighbours $y$ of $x$. Note that $f$ must be isomorphism invariant, but if the root $x$ of $T$ has degree $d$, then there are $d$ terms in the sums above, even if several of these correspond to isomorphic doubly-rooted trees. Note also that it suffices to consider functions $f$ that are characteristic functions of measurable sets.

We have seen above that if $\pi$ is a local limit then $\pi$ must be involution invariant. This observation was first made (in a slightly different context) by Benjamini and Schramm ; we return to this in Section 7. We do not know whether this necessary condition on $\pi$ is sufficient. (See also Question 7.1.)

The sequence $(G_{n})$ above will necessarily be asymptotically treelike (otherwise the total weight of $\pi$ would be less than $1$, so $\pi$ would not be a probability distribution). However, in the question above we have lost the condition that the tree counts of $(G_{n})$ be exponentially bounded. Such a condition may or may not be needed to get sensible limiting behaviour. To avoid possible complications, in the first draft of this paper we posed the following variant of Question 3.2.

Question 3.3 has now been answered in the affirmative by Elek .

Tree counts in random graphs

Adopting the terminology of Bollobás, Janson and Riordan , let $({\mathcal{S}},\mu)$ be an arbitrary probability space. By a kernel on $({\mathcal{S}},\mu)$ we mean an integrable, symmetric, non-negative function on ${\mathcal{S}}\times{\mathcal{S}}$. So far we have almost always taken ${\mathcal{S}}=$ and $\mu$ Lebesgue measure, but the notation is more convenient if we are rather more general here. As in (but taking the special case where the vertex types are i.i.d.), suppressing the dependence on $({\mathcal{S}},\mu)$ in the notation, we may form a random graph $G_{1/n}(n,\kappa)$ as follows: let $x_{1},\ldots,x_{n}\in{\mathcal{S}}$ be i.i.d. with the distribution $\mu$, and then, given $(x_{1},\ldots,x_{n})$, join each pair of vertices $\{i,j\}\subset[n]^{(2)}$ with probability $\min\{\kappa(x_{i},x_{j})/n,1\}$, independently of the other pairs. We say that vertex $i$ has type $x_{i}$ and call $({\mathcal{S}},\mu)$ the type space.

Let ${\mathfrak{X}}_{\kappa}$ be the multi-type Poisson Galton–Watson branching process naturally associated to $\kappa$: we start in generation with a single particle whose type is distributed according to $\mu$. A particle of type $x$ has children whose types form a Poisson process on ${\mathcal{S}}$ with the distribution $\kappa(x,y)\,d\mu(y)$: the number of such children in a measurable set $A\subset{\mathcal{S}}$ is Poisson with mean $\int_{A}\kappa(x,y)\,d\mu(y)$. As usual, the children of different particles are independent, and independent of the history. This branching process is the key to the analysis of the random graph $G_{1/n}(n,\kappa)$ in .

This is the distributional equivalent of the convergence in moments given by $s_{p}(T,G_{1/n}(n,\kappa))\to s(T,\kappa)$ for every tree $T$.

In the light of the comments above, we should like to answer the following question: when do two different branching processes ${\mathfrak{X}}_{\kappa_{1}}$ and ${\mathfrak{X}}_{\kappa_{2}}$ give rise to the same random tree? In other words, when is $\pi_{\kappa_{1}}=\pi_{\kappa_{2}}$? It is not hard to check that, at least for bounded $\kappa$, the counts $(s(T,\kappa))_{T\in\mathcal{T}}$ determine $\pi_{\kappa}$ and vice versa, so this is the same question as that asked at the start of the section. Since $\pi_{\kappa}$ directly describes the local structure of $G_{1/n}(n,\kappa)$, we consider the present branching process formulation more informative.

There is an obvious case when $\pi_{\kappa_{1}}=\pi_{\kappa_{2}}$: let $\kappa_{i}$ be a kernel on $({\mathcal{S}}_{i},\mu_{i})$. We say that $\kappa_{1}$ refines $\kappa_{2}$, and write $\kappa_{1}\prec\kappa_{2}$, if there is a measure-preserving map $\tau:{\mathcal{S}}_{1}\to{\mathcal{S}}_{2}$ such that for $\mu_{1}$-almost every $x\in{\mathcal{S}}_{1}$ we have

for all measurable $A\subset{\mathcal{S}}_{2}$. (This is a very different notion to that appearing in [12, Subsection 2.4], despite the superficial similarity to $\kappa_{1}=\kappa_{2}^{(\tau)}$.) In other words, if we take a particle of ${\mathfrak{X}}_{\kappa_{1}}$ and look at the distribution of the images under $\tau$ of the types of its children, then this distribution depends only on the image of the type of the original particle, and it does so according to the kernel $\kappa_{2}$. From this description it is immediate that if $\kappa_{1}\prec\kappa_{2}$, then $\pi_{\kappa_{1}}=\pi_{\kappa_{2}}$.

From now on we shall concentrate on the finite-type case, i.e., take ${\mathcal{S}}$ to be finite. Note that there is a natural correspondence between this case and the case of kernels $\kappa$ on $^{2}$ that are piecewise constant on rectangles. In this case $\kappa_{1}\prec\kappa_{2}$ simply means that the types associated to $\kappa_{1}$ may be grouped together to form the types associated to $\kappa_{2}$, and the distribution of the grouped types of the children of a particle in ${\mathfrak{X}}_{\kappa_{1}}$ is what it should be in ${\mathfrak{X}}_{\kappa_{2}}$.

The relation $\prec$ is clearly transitive. Hence the natural conjecture is that two kernels give the same distribution on trees if and only if they have a common refinement. Or should it be if and only if they are both refinements of a common ‘coarsening’? In fact, somewhat surprisingly, the two are equivalent!

Let $\kappa_{i}$ have type-space $({\mathcal{S}}_{i},\mu_{i})$. Since the definition of $\prec$ ignores sets of measure zero, we may assume that each $\mu_{i}$ is a strictly positive measure on the finite set ${\mathcal{S}}_{i}$.

Fix two components $C$ and $C^{\prime}$ of $G$, which need not be distinct. For each edge $e\in C$ set

The statement of Theorem 4.1 makes sense in the general case, without the restriction to finite-type kernels, but the proof as written does not. It is easy to adapt the proof that (ii) implies (i) to the general case, but it does not seem to be easy to prove that (i) implies (ii) in general. Indeed, it is not impossible that this implication is false in the general case.

Our main aim in this section is to prove the following result.

The proof will be a little involved (although most of the difficulties are notational rather than actual), so we shall start by illustrating a very simple special case of the basic idea.

The tree $T_{1}$ is simply a star, so its distribution is determined by the distribution of the degree of the root, i.e., the distribution of the number $d_{0}$ of children of the initial particle of ${\mathfrak{X}}_{\kappa}$. As in , for each $x\in{\mathcal{S}}$, let us write

Let $x$ be a type with $\lambda(x)>0$. From the definition of ${\mathfrak{X}}_{\kappa}$, the types of the children of a particle of type $x$ form a Poisson process on ${\mathcal{S}}$ with intensity measure $\mu_{x}$, defined by $\,d\mu_{x}(y)=\kappa(x,y)\,d\mu(y)$. In order to understand the distribution of $T_{2}$, we consider the offspring expected degree distribution $\lambda_{2}(x)$, the image of $\mu_{x}(y)$ under the map $y\mapsto\lambda_{1}(y)$. Thus, if $\mu_{x}$ were a probability measure, $\lambda_{2}(x)$ would be the distribution of $\lambda_{1}(Y)$ when $Y$ has the distribution $\mu_{x}$; in general, neither $\mu_{x}$ nor $\lambda_{2}(x)$ is a probability measure: they both have total mass $\mu_{x}({\mathcal{S}})=\lambda_{1}(x)$.

Similarly, for $k\geq 3$, we define $\lambda_{k}(x)$ to be the image of the measure $\mu_{x}(y)$ under the map $y\mapsto\lambda_{k-1}(y)$. Thus

Note that for a given $x$, $\lambda_{1}(x)=\lambda(x)$ is a real number, $\lambda_{2}(x)$ is a measure on the reals, $\lambda_{3}(x)$ is a measure on the set of measures on the reals, and so on. If $\kappa$ is of finite type, then all these measures are discrete. By the $k$-th order expected degree distribution $\Lambda_{\kappa}$ of $\kappa$, we mean the distribution of $\lambda_{k}(x)$ when $x$ is chosen randomly with distribution $\mu$.

We shall deduce Theorem 4.2 from the following lemma.

Fix $k\geq 1$, and let $\kappa$ be a finite-type kernel. Then the distribution $\Lambda_{k}$ determines the distribution of $T_{k}$ and vice versa.

The restriction to finite-type kernels is presumably not needed here, but simplifies the proofs, avoiding any possible difficulties associated to choosing the right notion of convergence. Note that we have already proved the case $k=1$.

Before proving Lemma 4.3, let us show that Theorem 4.2 does indeed follow.

Given a finite-type kernel $\kappa$ on $({\mathcal{S}},\mu)$, define an equivalence relation $\sim$ on ${\mathcal{S}}$ by $x\sim y$ if $\lambda_{k}(x)=\lambda_{k}(y)$ for every $k$. If $x\not\sim y$, then there is some smallest $k=k(x,y)$ such that $\lambda_{k}(x)\neq\lambda_{k}(y)$. Let $K$ be an upper bound on the set $\{k(x,y):x,y\in{\mathcal{S}},x\not\sim y\}$, which exists since ${\mathcal{S}}$ is finite. Since $\lambda_{k+1}(x)$ determines $\lambda_{k}(x)$, we have $\lambda_{K}(x)\neq\lambda_{K}(y)$ whenever $x\not\sim y$, so

Note that $K$ is determined by the set $\Lambda_{k}$, $k=0,1,2,\ldots$: we may take $K$ to be the smallest integer such that the distribution of $\lambda_{K+1}$ (which then determines that of $\lambda_{K}$) has property (12).

It remains to prove Lemma 4.3. Note the lemma makes two separate statements; in proving Theorem 4.2 we only used one of these, that the distribution of $T_{k}$ determines that of $\Lambda_{k}$. We shall prove Lemma 4.3 by induction; for this we need both statements. In fact, to make the induction work, we shall need to prove a little more.

Let $\kappa$ be a kernel on the finite type-space $({\mathcal{S}},\mu)$. The measure $\mu$ plays two roles in the branching process ${\mathfrak{X}}_{\kappa}$: it appears in the distribution of the offspring of a particle, and also in the distribution of the type of the initial particle. It will be convenient to generalize ${\mathfrak{X}}_{\kappa}$ slightly as follows: let $\mu_{0}$ be any probability measure on ${\mathcal{S}}$, and let ${\mathfrak{X}}_{\kappa}(\mu_{0})$ be the branching process defined as ${\mathfrak{X}}_{\kappa}$, but starting with a single particle of type distributed according to $\mu_{0}$. Note that ${\mathfrak{X}}_{\kappa}(\mu_{0})$ depends on $\mu$ as well as $\mu_{0}$, and that ${\mathfrak{X}}_{\kappa}(\mu)={\mathfrak{X}}_{\kappa}$.

Let $\Lambda_{k}(\mu_{0})$ denote the distribution of $\lambda_{k}(x)$ when $x$ is chosen randomly with distribution $\mu_{0}$, so $\Lambda_{k}(\mu)=\Lambda_{k}$. Also, let $T_{k}(\mu_{0})$ denote the random rooted tree obtained from the first $k$ generations of ${\mathfrak{X}}_{\kappa}(\mu_{0})$ by forgetting the types of the particles. The following lemma is slightly stronger than Lemma 4.3, which can be recovered by setting $\mu_{0}=\mu$.

Fix $k\geq 1$, let $\kappa$ be a finite-type kernel on $({\mathcal{S}},\mu)$, and let $\mu_{0}$ be a probability measure on ${\mathcal{S}}$. Then (i) the distribution $\Lambda_{k}(\mu_{0})$ determines the distribution of $T_{k}(\mu_{0})$, and (ii) the distribution of $T_{k}(\mu_{0})$ determines $\Lambda_{k}(\mu_{0})$.

Suppose then that $k\geq 2$ and that (i) holds with $k$ replaced by $k-1$. It is easy to see that it suffices to prove (i) with $\mu_{0}$ concentrated on a single type $x$, in which case $\Lambda_{k}(\mu_{0})=\lambda_{k}(x)$. Let us fix the type $x\in{\mathcal{S}}$ of the root, writing ${\mathfrak{X}}_{\kappa}(x)={\mathfrak{X}}_{\kappa}(\delta_{x})$ for the branching process ${\mathfrak{X}}_{\kappa}$ started with a single particle of type $x$.

Let $X_{1}$ denote the first generation of ${\mathfrak{X}}_{\kappa}(x)$. Given $X_{1}$, the descendants of a particle $v$ in $X_{1}$ have the distribution of ${\mathfrak{X}}_{\kappa}(y)$, where $y$ is the type of $v$, and the subtrees corresponding to different $v$ are independent. By induction, the distribution of the first $k-1$ generations of the descendants of $v$ are determined by $\lambda_{k-1}(y)$. Hence, given $X_{1}$, the conditional distribution of $T_{k}$ depends only on the multiset $M=\{\lambda_{k-1}(y)\}$, where $y$ runs over the types in $X_{1}$. Given the type $x$ of the root, the types of the particles in $X_{1}$ form a Poisson process on ${\mathcal{S}}$ with intensity measure $\mu_{x}$. Hence, $M$ is a Poisson process on the appropriate space of distributions with intensity measure $\lambda_{k}(x)$. In particular, the distribution of $M$, and hence that of $T_{k}$, is determined by $\lambda_{k}(x)$, completing the proof of part (i) by induction.

Theorem 4.2 shows that there are many examples of different kernels that give rise to the same branching process, and hence to the same distribution of tree counts in the corresponding random graphs $G_{1/n}(n,\kappa)$. One extremely special case concerns homogeneous kernels: we say that $\kappa$ is homogeneous with degree $c$ if $\int_{y}\kappa(x,y)\,dy=c$ for almost every $x$. In this case, ${\mathfrak{X}}_{\kappa}$ seen without types becomes a standard single-type Galton–Watson branching process ${\mathfrak{X}}_{c}$ in which each particle has a Poisson number of children with mean $c$. Writing $c$ also for the constant kernel taking the value $c$, Theorem 4.2 shows that $\pi_{\kappa}=\pi_{c}$ if and only if $\kappa$ is homogeneous with degree $c$. (This special case is essentially trivial, however: one need consider only the first generation of the branching process.)

The partition metric

In the spirit of the rest of the paper, we say that two graphs with $n$ vertices are essentially the same if one can be changed into a graph isomorphic to the other by adding and deleting $o(pn^{2})$ edges, where $p=p(n)$ is our normalizing function, as usual. (Of course, the definition makes formal sense only for two sequences.) Otherwise, they are essentially different. In all previous sections, graphs that were essentially the same were treated as equivalent, in the sense that their distance in any of the metrics we considered tends to zero.

Let $p=1/n$, and let $\kappa$ be a kernel whose corresponding branching process always dies out. In the notation of Bollobás, Janson and Riordan , we assume that the operator $T_{\kappa}$ corresponding to the kernel $\kappa$ satisfies $||T_{\kappa}||\leq 1$, i.e., $\kappa$ is (weakly) subcritical. From the results in , almost all vertices of $G_{1/n}(n,\kappa)$ are in small tree components: more precisely, given any $\varepsilon>0$, there is a $K$ such that, whp, all but at most $\varepsilon n$ vertices of $G_{1/n}(n,\kappa)$ are in tree components with size at most $K$. Furthermore, the asymptotic number of copies of a given tree $T$ in $G_{1/n}(n,\kappa)$ is determined by the probability of $T$ in the distribution $\pi_{\kappa}$. It follows that if $\kappa_{1}$ and $\kappa_{2}$ are subcritical kernels, then $G_{1/n}(n,\kappa_{1})$ and $G_{1/n}(n,\kappa_{2})$ are (whp) essentially the same if and only if $\pi_{\kappa_{1}}=\pi_{\kappa_{2}}$. Hence, in the subcritical case, the random graph $G_{1/n}(n,\kappa)$ depends only on the branching process ${\mathfrak{X}}_{\kappa}$. Of course, this rather trivial observation does not extend to the supercritical case.

Given two real numbers $a,b\geq 0$, let $\kappa_{a,b}$ denote the $2$-by-$2$ ‘chessboard’ kernel defined as follows:

To form the random graph $G_{p}(n,\kappa_{a,b})$, we partition the vertex set randomly into two parts, and then take each cross-edge to be present with probability $bp$, and each other edge with probability $ap$. Note that $\kappa_{a,b}$ is homogeneous with constant $(a+b)/2$. Also, if $a=b$, then $\kappa_{a,b}$ is simply the constant kernel taking the value $a=b$.

For $p=1/n$, perhaps the simplest example of two sequences of essentially different graphs not distinguished by their tree counts is given by the random graphs $G_{1/n}(n,\kappa_{2,2})$ and $G_{1/n}(n,\kappa_{4,0})$, i.e., the usual Erdős–Rényi random graph $G(n,2/n)$ and (essentially) the random bipartite graph $G(n/2,n/2;4/n)$. How do we know that these graphs are different? For the obvious reason that one is bipartite, with almost equal vertex classes, while the other is not. Indeed, the smallest balanced cut in $G(n,2/n)$ has size of order $\Theta(n)$: this follows, for example, from the result of Luczak and McDiarmid that removing $o(n)$ edges from the giant component of $G(n,c/n)$, $c>1$, leaves a connected component with only $o(n)$ fewer vertices than the original giant. Note that one has to be a little careful here: writing $\rho(c)$ for the largest solution to $\rho=1-e^{-c\rho}$, so $\rho(c)n$ is the typical size of the giant component in $G(n,c/n)$, we need $\rho(c)>1/2$; otherwise, it is easy to construct a balanced cut with $o(n)$ edges across it. Note that both $G(n,2/n)$ and $G(n/2,n/2;4/n)$ have balanced cuts with a range of sizes: the difference between the two graphs can be seen in the difference between these ranges.

Fix throughout a normalizing function $p=p(n)$ and a constant $C>0$; we shall only consider graphs $G_{n}$ with $n$ vertices and at most $Cpn^{2}/2$ edges.

where $\Pi$ runs over all balanced partitions of $V(G_{n})$ into $k$ parts, i.e., all partitions $(P_{1},\ldots,P_{k})$ with $|P_{i}|-|P_{j}|\leq 1$.

Recall that $e(G_{n})\leq Cpn^{2}/2$, so $e(U,W)\leq e(V(G_{n}),V(G_{n}))=2e(G_{n})\leq Cpn^{2}$. Since each part of a balanced partition has size at least $n/(2k)$, the entries of any $M_{\Pi}(G_{n})\in\mathcal{M}_{k}(G_{n})$ are thus bounded by $C_{k}=(2k)^{2}C$, and $\mathcal{M}_{k}(G_{n})$ is a subset of the compact space $B_{k}=[0,C_{k}]^{k(k+1)/2}$.

Finally, let $\mathcal{C}=\prod_{k\geq 2}\mathcal{C}(B_{k})$, and let $\mathcal{M}:\mathcal{F}\mapsto\mathcal{C}$ be the map defined by

where $d$ is any metric on $\mathcal{C}$ giving rise to the product topology.

The definitions above may appear rather unnatural: the set $\mathcal{M}_{k}(G_{n})$ of possible density matrices is perhaps more naturally seen as a multiset, with one element for each of the $N_{n,k}$ balanced partitions of $[n]$ into $k$ (ordered) parts; the Hausdorff metric ignores the multiplicities of the points of these sets. For multisets $S$, $S^{\prime}$ in a metric space $(X,d)$ with $|S|=|S^{\prime}|=N$, (a version of) their matching distance is given by