The cut metric, random graphs, and branching processes

Introduction and results

Throughout this paper we consider random graphs with independence between the edges. The distribution of a random $n$-vertex graph with this property is of course specified by the matrix of edge probabilities; here we are interested in the asymptotic behaviour of the component structure as $n\to\infty$, so we shall consider a sequence of such matrices. Our main focus is to determine when there is whp a giant component, i.e., a component containing $\Theta(n)$ vertices. Here, as usual, an event holds with high probability, or whp, if it holds with probability $1-o(1)$ as $n\to\infty$. When there is a giant component, we shall also find its asymptotic size.

For these questions it is natural to focus on (extremely) sparse graphs, with $\Theta(n)$ edges, so we shall normalize by considering matrices $A_{n}$ whose entries are $n$ times the corresponding edge probabilities. Thus the case in which each $A_{n}$ has all (off-diagonal) entries equal to some $c>0$ corresponds to the classical sparse model $G(n,c/n)$. Without some further assumptions, it seems difficult to prove asymptotic results, although Alon did so for some questions concerning connectedness. As in previous work, the natural additional assumption turns out to be convergence to a suitable limiting object, namely a kernel, i.e., a symmetric non-negative function on $^{2}$. Our aim is to relate the asymptotic size of the giant component to a suitable function of this kernel.

The aim described above was also one of the aims of , and of Bollobás, Borgs, Chayes and Riordan . We shall prove a common generalization of the corresponding results from these papers by weakening the assumptions: we shall work with convergence in the cut metric (defined below) as in , while allowing unbounded matrices and kernels, as in . It turns out that these very weak, natural assumptions suffice to allow us to relate the giant component of the random graph to the kernel.

To state our results we shall need a few definitions. By a kernel on $$we simply mean an integrable, symmetric function$\kappa:^{2}\to[0,\infty)$. We regard kernels as elements of$L^{1}$, so two kernels that are equal almost everywhere are considered to be the same.

Throughout, $A_{n}$ will denote a symmetric $n$-by-$n$ matrix with non-negative entries. If $A_{n}=(a_{ij})$ is such a matrix, then there is a piecewise constant kernel $\kappa_{A_{n}}$ naturally associated to $A_{n}$: this takes the value $a_{ij}$ on the square $((i-1)/n,i/n]\times((j-1)/n,j/n]$. We call $\kappa$ an $n$-by-$n$ kernel if it is of the form $\kappa_{A_{n}}$ for some $A_{n}$.

Having described the limit object (a kernel), and the random graph, it remains to describe the notion of convergence. In doing so it is convenient to consider somewhat more general kernels.

Let $({\mathcal{S}},\mu)$ be a probability space; most of the time we shall take ${\mathcal{S}}$ to be $$(or$(0,1]$) with$\mu$Lebesgue measure. A kernel on${\mathcal{S}}$is an integrable, symmetric function$\kappa:{\mathcal{S}}^{2}\to[0,\infty)$. Following Frieze and Kannan , for$W\in L^{1}({\mathcal{S}}^{2})$we define the cut norm$\|W\|_{\square}$of$W$ by

where the supremum is taken over all pairs of measurable subsets of ${\mathcal{S}}$. Alternatively, one can take

In taking the supremum in (4) one can restrict to functions $f$ and $g$ taking only the values $\pm 1$; it follows that

Thus the two norms $\|\cdot\|_{\square,1}$ and $\|\cdot\|_{\square,2}$ are equivalent, and it will almost never matter which one we use. We shall write $\|\cdot\|_{\square}$ for either norm, commenting in the few cases where the choice matters. (There are further, equivalent versions of the cut-norm; see Borgs, Chayes, Lovász, Sós and Vesztergombi .)

Note that for either definition of the cut norm we have

The definition (4) is natural for a functional analyst: this norm is the dual of the projective tensor product norm in $L^{\infty}\hat{\otimes}L^{\infty}$, and is thus the injective tensor product norm in $L^{1}\check{\otimes}L^{1}$; equivalently, it is equal to the operator norm of the corresponding integral operator $L^{\infty}\to L^{1}$. One advantage of this version is the simple “Banach module” property we shall note later in (23). On the other hand, (3) is probably more familiar in combinatorics, and (surprisingly) occasionally has a tiny advantage; see Section 3.

Given a kernel $\kappa$ and a measure-preserving bijection $\tau:{\mathcal{S}}\to{\mathcal{S}}$, let $\kappa^{(\tau)}$ be the kernel defined by

we call $\kappa^{(\tau)}$ a rearrangement of $\kappa$. We write $\kappa\sim\kappa^{\prime}$ if $\kappa^{\prime}$ is a rearrangement of $\kappa$. Given two kernels $\kappa$, $\kappa^{\prime}$ on $$, the cut metric of Borgs, Chayes, Lovász, Sós and Vesztergombi is defined by

If we wish to specify which version of the cut norm is involved, we write ${\delta_{\square,1}}$ or ${\delta_{\square,2}}$. Usually, this is irrelevant.

As in , one can also define ${\delta_{\square}}$ using couplings between different kernels, rather than rearrangements. In this case it is irrelevant that the kernels are on the same probability space. In particular, we may regard a matrix $A_{n}$ as a kernel on the discrete space with $n$ equiprobable elements. Then (by an obvious coupling) ${\delta_{\square}}(A_{n},\kappa_{A_{n}})=0$, where $\kappa_{A_{n}}$ is the $n$-by-$n$ kernel on $$corresponding to$A_{n}$. Thus${\delta_{\square}}(A_{n},\kappa)={\delta_{\square}}(\kappa_{A_{n}},\kappa)$for any kernel$\kappa$on any probability space$({\mathcal{S}},\mu)$. In the light of this we shall often identify a matrix with the corresponding kernel on$$.

Throughout this paper, we shall consider sequences $(A_{n})$ of matrices such that for some kernel $\kappa$ we have ${\delta_{\square}}(A_{n},\kappa)\to 0$. It follows from the results of that for any kernel $\kappa$ on a probability space $({\mathcal{S}},\mu)$, there exists a kernel $\kappa^{\prime}$ on $$with${\delta_{\square}}(\kappa,\kappa^{\prime})=0$. Hence we lose no generality by taking$({\mathcal{S}},\mu)$to be the standard ground space in which${\mathcal{S}}=$(or$(0,1])$and$\mu$is Lebesgue measure. In this case it is natural to identify$A_{n}$with$\kappa_{A_{n}}$as above, and we may use the more down-to-earth formula (5) as the definition of${\delta_{\square}}$.

To state our results we need two further definitions, from . Given a kernel $\kappa$ on a probability space $({\mathcal{S}},\mu)$, let ${\mathfrak{X}}_{\kappa}$ be the multi-type Galton–Watson branching process defined as follows. We start with a single particle in generation $0$, whose type has the distribution $\mu$. A particle in generation $t$ of type $x$ gives rise to children in generation $t+1$ whose types form a Poisson process on ${\mathcal{S}}$ with intensity $\kappa(x,y)\,d\mu(y)$. The children of different particles are independent, and independent of the history.

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

Let $\rho(\kappa)$ denote the survival probability of ${\mathfrak{X}}_{\kappa}$, i.e., the probability that all generations are non-empty. It is easily seen that this is the same as the probability that the total number $|{\mathfrak{X}}_{\kappa}|$ of particles in ${\mathfrak{X}}_{\kappa}$ is infinite. For basic results about $\rho(\kappa)$, we refer the reader to .

Finally, as in , a kernel $\kappa$ is reducible if there exists $A\subset{\mathcal{S}}$ with $0<\mu(A)<1$ such that $\kappa$ is zero almost everywhere on $A\times({\mathcal{S}}\setminus A)$. Otherwise, $\kappa$ is irreducible.

In this subsection we state our main results; we shall give corresponding results for hypergraphs in Section 3. Recall that any matrix denoted by $A_{n}$ is assumed to be a symmetric $n$-by-$n$ matrix with non-negative entries. Given a graph $G$ and an $i\geq 1$, we write $C_{i}(G)$ for the number of vertices in the $i$th largest component of $G$, with $C_{i}(G)=0$ if $G$ has fewer then $i$ components. We shall see later that our results imply corresponding results for the Poisson variants of $G(A_{n})$; for simplicity we state them only in the original formulation, where the edge probabilities are $\min\{a_{ij}/n,1\}$. The theorems are valid for a kernel $\kappa$ on any probability space $({\mathcal{S}},\mu)$, but as noted above we may assume without loss of generality that ${\mathcal{S}}=$, and we shall do so in the proofs for convenience.

Of course, as usual we do not require $A_{n}$ to be defined for every $n$, only for a subsequence.

Let $\rho_{\kappa}(x)$ denote the survival probability of the process ${\mathfrak{X}}_{\kappa}(x)$ started with a particle of type $x$. Let $T_{\kappa}$ be the integral operator on ${\mathcal{S}}$ with kernel $\kappa$, defined by

for any (measurable) function $f$ such that this integral is defined (finite or $+\infty$) for a.e. $x$. Note that this class of functions includes every (measurable) function $f\geq 0$. Also, let

clearly if $\|T_{\kappa}\|<\infty$, then $\|T_{\kappa}\|$ is simply the norm of $T_{\kappa}$ as an operator on $L^{2}({\mathcal{S}},\mu)$.

Recall from [4, Theorem 6.2] that $\rho(\kappa)>0$ if and only if $\|T_{\kappa}\|>1$, and that if $\|T_{\kappa}\|>1$, then $\rho_{\kappa}$ is the unique non-zero solution $f\geq 0$ to the functional equation

Using Theorem 1.1, we shall deduce the following slight extension, describing the ‘critical’ value of $c$ above which a giant component appears in $G(cA_{n})$.

Let $\kappa$ be a kernel, $(A_{n})$ a sequence of symmetric non-negative $n$-by-$n$ matrices such that ${\delta_{\square}}(A_{n},\kappa)\to 0$, and $c>0$ a constant, and set $G_{n}=G(cA_{n})$.

If $c>\|T_{\kappa}\|^{-1}$, then $C_{1}(G_{n})=\Theta(n)$ whp. Furthermore, if $\kappa$ is bounded, then for any constant $\alpha<(c\|T_{\kappa}\|-1)/(c\sup\kappa)$ we have $C_{1}(G_{n})\geq\alpha n$ whp.

This clearly generalizes the main result, Theorem 1, of Bollobás, Borgs, Chayes and Riordan , which is simply the special case in which $\kappa$ and the entries of the matrices $A_{n}$ are uniformly bounded. As we shall see in the next subsection, Theorem 1.2 also generalizes Theorem 3.1 of . Note, however, that to prove this requires various results from .

Returning to the irreducible case, we shall also prove a ‘stability’ result analogous to Theorem 3.9 of .

Let $\kappa$ be an irreducible kernel and $(A_{n})$ a sequence of non-negative symmetric $n$-by-$n$ matrices such that ${\delta_{\square}}(A_{n},\kappa)\to 0$. For every $\varepsilon>0$ there is a $\delta=\delta(\kappa,\varepsilon)>0$ such that, whp,

for every graph $G_{n}^{\prime}$ that may be obtained from $G_{n}=G(A_{n})$ by deleting at most $\delta n$ vertices and their incident edges, and then adding or deleting at most $\delta n$ edges.

As we shall show in Subsection 2.6, using this result it is not hard to deduce exponential tail bounds on the size of the giant component.

Let $\kappa$ be an irreducible kernel and $\varepsilon>0$ a real number. There is a $\gamma=\gamma(\kappa,\varepsilon)>0$ such that whenever $(A_{n})$ is sequence of non-negative symmetric $n$-by-$n$ matrices with ${\delta_{\square}}(A_{n},\kappa)\to 0$, then setting $G_{n}=G(A_{n})$ we have

For the very special case of $G(n,p)$, $p=c/n$, much stronger results are known, establishing the correct dependence of $\gamma$ on $\varepsilon$ in the upper and lower bounds. Indeed, such a ‘large deviation principle’ for $C_{1}(G(n,c/n))$ was obtained by O’Connell , and Biskup, Chayes and Smith proved a corresponding result for the number of vertices in ‘large’ components. One might ask whether these results can be generalized to $G(A_{n})$; this is likely to be rather hard. Indeed, it is not even clear whether they extend to $G(A_{n})$ with $A_{n}$ converging to a constant kernel $\kappa$.

The rest of the paper is organized as follows. In the next few subsections we discuss various applications and consequences of the results above. In Section 2 we prove Theorems 1.1–1.4: as the proofs are somewhat lengthy we shall break this section into subsections. Finally, in Section 3 we present extensions of our main results to the hyperkernels and corresponding random (hyper)graphs considered in .

2 Relationship to the sparse inhomogeneous model

In this subsection we shall prove a simple lemma which, together with Theorem 1.2, implies Theorem 3.1 of . This latter result states that (essentially) the conclusions of Theorems 1.1 and 1.2 (with $c=1$) hold when the random graph $G_{n}$ is an instance of the general sparse inhomogeneous model $G^{\mathcal{V}}(n,\kappa_{n})$ of . Since the full definitions of are rather cumbersome, for this subsection only we assume a certain familiarity with the terminology of .

We say that a kernel $\kappa$ on $({\mathcal{S}},\mu)$ is of finite type if there is a finite partition $(S_{1},\ldots,S_{r})$ of ${\mathcal{S}}$ into measurable sets such that $\kappa$ is constant on each of the sets $S_{i}\times S_{j}$. A key strategy we used in was to reduce results about the general case to the finite-type case; we shall use the same approach in this subsection. In the rest of this paper we follow a different strategy, using cut convergence to directly prove results about the general case.

The sparse inhomogeneous model $G^{\mathcal{V}}(n,\kappa_{n})$ is defined in terms of a ground space ${\mathcal{V}}=({\mathcal{S}},\mu,({\bf x}_{n}))$, and a sequence $(\kappa_{n})$ of kernels on $({\mathcal{S}},\mu)$. Here $({\mathcal{S}},\mu)$ is a probability space (satisfying some additional assumptions) and each ${\bf x}_{n}$ is a (deterministic or) random sequence of $n$ points of ${\mathcal{S}}$, satisfying certain technical assumptions. The sequence $(\kappa_{n})$ is assumed to converge to a kernel $\kappa$ in a certain sense, and must also satisfy a certain ‘graphicality’ assumption that involves the sequences ${\bf x}_{n}$. For the full technical details, which will not be relevant here, see .

As noted in [4, Remark 8.8], in proving results about this model one may always assume that the vertex types are deterministic. In this case $G^{\mathcal{V}}(n,\kappa_{n})$ has the distribution of $G(A_{n})$, where $A_{n}$ is the matrix obtained by sampling the kernel according to the vertex types: $A_{n}$ has entries $a_{ij}=a_{ij}^{(n)}$ given by $a_{ij}=\kappa_{n}(x_{i}^{(n)},x_{j}^{(n)})\wedge n$ for $i\neq j$ and $a_{ii}=0$, where $x\wedge y=\min\{x,y\}$. We refer the reader to for the formal definition of $G^{\mathcal{V}}(n,\kappa_{n})$, and in particular for the precise definitions of a (generalized) vertex space and a graphical (sequence of) kernel(s).

The next lemma shows that the matrices $A_{n}$ associated to $G^{\mathcal{V}}(n,\kappa_{n})$ do converge in probability to the limit kernel $\kappa$ in the cut metric. Although our main interest is in the cut distance, we in fact obtain a result for the $L^{1}$ norm, modulo rearrangements. Given two kernels $\kappa$, $\kappa^{\prime}$ on the standard ground space, let

in analogy with (5). More generally, for two kernels on arbitrary (not necessarily equal) probability spaces, we may define $\delta_{1}(\kappa,\kappa^{\prime})$ as a certain infimum over couplings of these probability spaces; we omit the details.

Since $\|\kappa^{\prime}\|_{\square}\leq\|\kappa^{\prime}\|_{L^{1}}$ for any $\kappa^{\prime}$, we have ${\delta_{\square}}(\kappa_{1},\kappa_{2})\leq\delta_{1}(\kappa_{1},\kappa_{2})$ for any two kernels, so it suffices to prove the first statement.

Conditioning on the vertex types, we may and shall assume that the vertex types are deterministic. For convenience we assume that ${\mathcal{S}}$ is the standard ground space $$. (The general case requires couplings of$\kappa$and$A_{n}$, but is otherwise the same.)

Suppose first that $\kappa$ is regular finitary; roughly speaking, this means that $\kappa$ is of finite type. (More precisely, $\kappa$ must be of finite type and must satisfy an additional technical condition; see .) Suppose also that $\kappa_{n}=\kappa$ for every $n$. In this case the result is essentially trivial: we may assume that there is a partition of ${\mathcal{S}}$ into sets $S_{1},\ldots,S_{k}$ such that $\kappa$ is constant on each set $S_{r}\times S_{s}$. The definition of a vertex space ensures that for each $r$ there are $\mu(S_{r})n+o(n)$ vertices $i$ such that $x_{i}\in S_{r}$. Rearranging (or coupling) appropriately, we may assume that each $S_{r}$ is an interval $I_{r}\subseteq{\mathcal{S}}=$. We may then order the vertices so that for all but $o(n)$ vertices $i$ the interval $(i-1/n,i/n]$ lies entirely inside the interval $I_{r}$ containing $x_{i}$. After doing so, $\kappa$ and $\kappa_{A_{n}}$ differ on a set of measure $o(1)$. Since both are bounded by $\sup\kappa<\infty$, it follows that $\kappa_{A_{n}}\to\kappa$ in $L^{1}$ and hence in ${\delta_{\square}}$.

To treat the general case, we approximate by finite-type kernels, as so often in . Indeed, by Lemma 7.3 of there is a sequence of regular finitary kernels $\kappa_{m}^{-}$ such that $\kappa_{m}^{-}\leq\kappa_{n}$ for all $n\geq m$ and $\kappa_{m}^{-}(x,y)\nearrow\kappa(x,y)$ for a.e. $(x,y)\in{\mathcal{S}}^{2}$. By monotone convergence, we have $\int\kappa_{m}^{-}\to\int\kappa$ as $m\to\infty$. Fix $\varepsilon>0$. Then there is some $m$ such that $\kappa^{-}=\kappa_{m}^{-}$ satisfies $\kappa^{-}\leq\kappa$ and $\int(\kappa-\kappa^{-})\leq\varepsilon$.

Let $A_{n}^{-}$ be the matrix with entries $a_{ij}^{-}=\kappa^{-}(x_{i}^{(n)},x_{j}^{(n)})\wedge n$, $i\neq j$, and $a_{ii}^{-}=0$. Considering from now on only $n\geq m$, we then have $a_{ij}^{-}\leq a_{ij}$ and thus $\kappa_{A_{n}^{-}}\leq\kappa_{A_{n}}$ pointwise. After conditioning on the vertex types, the expected number of edges in $G^{\mathcal{V}}(n,\kappa_{n})$ is exactly

using $a_{ii}=0$ for the first equality. Thus, by Lemma 8.7 of , $\int\kappa_{A_{n}}\to\int\kappa$. Similarly (since a finite-type kernel is always graphical), $\int\kappa_{A_{n}^{-}}\to\int\kappa^{-}$. Hence,

By the finite-type case above, we have $\delta_{1}(\kappa_{A_{n}^{-}},\kappa^{-})\to 0$. Since $\|\kappa-\kappa^{-}\|_{L^{1}}\leq\varepsilon$ it follows that $\limsup\delta_{1}(\kappa_{A_{n}},\kappa)\leq 2\varepsilon$. Recalling that $\varepsilon>0$ was arbitrary, the result follows. ∎

Recall that Theorem 3.1 of states (essentially) that the random graphs $G_{n}=G^{\mathcal{V}}(n,\kappa_{n})$ satisfy the conclusions of Theorems 1.1 and 1.2. Using Lemma 1.6, by Remark 1.5 the vertex space case of this result follows immediately from Theorems 1.1 and 1.2. As noted in [4, Section 8.1], the apparent extra generality of generalized vertex spaces makes no essential difference, so Theorem 3.1 of then follows. In other words, we have shown that Theorem 3.1 of may be deduced from our present Theorems 1.1 and 1.2, using various results from mentioned above. Let us remark that in practice, the conditions of Theorem 3.1 of will often be easier to verify than those of Theorems 1.1 and 1.2.

3 Further applications

As noted in , the definitions in exclude one simple case to which the results clearly extend, namely the case of an arbitrary integrable kernel $\kappa$, and i.i.d. vertex types: given a kernel $\kappa$, one may define the random graph $G(n,\kappa)=G_{1/n}(n,\kappa)$ on $[n]$ by taking $x_{1},\ldots,x_{n}$ to be independent and uniformly distributed on $$, and given these ‘vertex types’, joining each pair$\{i,j\}$of vertices with probability$\min\{\kappa(x_{i},x_{j})/n,1\}$, independently of all other pairs. With$\kappa$ bounded, a corresponding dense random graph was studied by Lovász and Szegedy .

Our next lemma shows that Theorems 1.1–1.3 apply (unsurprisingly) to the graphs $G(n,\kappa)$, since the (random) matrices of edge probabilities associated to $G(n,\kappa)$ converge to $\kappa$ in probability in ${\delta_{\square}}$.

As before, we have ${\delta_{\square}}\leq\delta_{1}$, so it suffices to prove the first statement. Fix $\varepsilon>0$. By standard results there is a finite-type kernel $\kappa^{\prime}$ such that $\|\kappa-\kappa^{\prime}\|_{L^{1}}\leq\varepsilon^{2}$. Indeed, this follows by the construction of the product measure, since the rectangular sets $A\times B$ generate an algebra $\mathcal{F}_{0}$ that generates the product $\sigma$-field, and it is easily seen that finite linear combinations of indicator functions of sets in $\mathcal{F}_{0}$ are dense in $L^{1}({\mathcal{S}}^{2})$.

Let $A_{n}^{\prime}$ be the matrix with entries $a_{ij}^{\prime}=\kappa^{\prime}(x_{i},x_{j})$, $i\neq j$, and $a_{ii}^{\prime}=0$. Then

so with probability at least $1-\varepsilon$ we have

So far we have shown that the results in Subsection 1.1 imply many existing results about the giant component in various sparse random graphs. We now turn to a new application, giving an example that we believe is not covered by known results.

Let $p=p(n)$ be some normalizing function, with $0<p\leq 1$ and $p(n)\to 0$. Let $G_{n}$ be a sequence of graphs in which $G_{n}$ has $n$ vertices and $\Theta(pn^{2})$ edges, and let $\kappa$ be a kernel. Following the terminology of , we say that ${\delta_{\square}}(G_{n},\kappa)\to 0$ if ${\delta_{\square}}(A_{n},\kappa)\to 0$, where $A_{n}$ is $1/p$ times the adjacency matrix of $G_{n}$. A sequence $(G_{n})$ satisfying this condition may be thought of as a sequence of inhomogeneous sparse quasi-random graphs. For graphs which are dense and homogeneous, there are many equivalent definitions of quasi-randomness, or pseudo-randomness; see Thomason or Chung, Graham and Wilson , for example. In the sparse case these notions are no longer equivalent, as discussed by Chung and Graham in the homogeneous case, and Bollobás and Riordan in general; when $\kappa$ is constant, normalizing so that $\kappa=1$, we have ${\delta_{\square}}(G_{n},\kappa)\to 0$ if and only if

this condition is called DISC in . Other, stronger conditions have also been considered, in particular by Thomason . Our next result establishes the threshold for percolation on an arbitrary sequence of inhomogeneous sparse quasi-random graphs.

As above, let $A_{n}$ be $1/p$ times the adjacency matrix of $G_{n}$. Then, by assumption, ${\delta_{\square}}(A_{n},\kappa)\to 0$, so ${\delta_{\square}}(cA_{n},c\kappa)\to 0$. The random subgraph $G_{n}^{\prime}$ is exactly $G(cA_{n})$, so the result follows from Theorem 1.1. ∎

As noted in , one way to construct inhomogeneous sparse quasi-random graphs is to consider appropriate random graphs, but this is not so interesting in the present context: the random subgraphs of such graphs end up being the graphs $G(n,\kappa)$ considered at the start of the subsection. A more interesting application of Theorem 1.8 is to deterministic quasi-random graphs. In the homogeneous case, where $\kappa=1$ is constant, many such sequences are known. One example is given by the ‘polarity graphs’ of Erdős and Rényi , defined (for suitable $n$) by taking as vertices the points of the projective plane over $GF(q)$, $q$ a prime power, and joining $x=(x_{0},x_{1},x_{2})$ and $y=(y_{0},y_{1},y_{2})$ if and only if $x_{0}y_{0}+x_{1}y_{1}+x_{2}y_{2}=0$ in $GF(q)$. Here $n=q^{2}+q+1$ and $p=(q+1)/n=\Theta(n^{-1/2})$. Other examples are the coset graphs of Chung and the Ramanujan graphs of Lubotzky, Phillips and Sarnak . In all these examples the limiting kernel is constant, so Theorem 1.8 says that on any of these graphs, the threshold for percolation is when the average degree of the random subgraph is equal to $1$.

Note that in the examples above, the matrices $(A_{n})$ to which Theorem 1.1 or Theorem 1.2 is applied are very far from satisfying the uniform boundedness condition assumed in Bollobás, Borgs, Chayes and Riordan . Indeed, each $A_{n}$ has all entries either $0$ or $1/p$, where $p=p(n)\to 0$. This also implies that the corresponding kernels $\kappa_{A_{n}}$, which do converge to $\kappa=1$ in the cut norm, do not converge in various natural stronger senses, such as pointwise or in $L^{1}$.

In general, it is very hard to compute the cut distance between two kernels. Indeed, if $A_{1}$ and $A_{2}$ are the adjacency matrices of two graphs, then the general problem of computing ${\delta_{\square}}(\kappa_{A_{1}},\kappa_{A_{2}})$ includes as a special case deciding whether $G_{1}$ and $G_{2}$ are isomorphic. Thus applications of Theorems 1.1 and 1.2 are likely to involve special cases where cut convergence is guaranteed for some simple reason, such as the example in the previous subsection.

4 Consequences for branching processes

Theorem 1.1 has an interesting consequence purely concerning branching processes. Recall that if $\kappa$ is a kernel, then $\rho(\kappa)$ denotes the survival probability of the multi-type Poisson Galton–Watson process ${\mathfrak{X}}_{\kappa}$.

Let $\kappa_{m}$, $m\geq 1$, and $\kappa$ be kernels with ${\delta_{\square}}(\kappa_{m},\kappa)\to 0$ as ${m\to\infty}$. Then $\rho(\kappa_{m})\to\rho(\kappa)$.

Let us first note that the result is not really a statement about the cut metric ${\delta_{\square}}$, but rather about the cut norm $\|\cdot\|_{\square}$. Indeed, by definition of ${\delta_{\square}}$ there are rearrangements $\kappa_{m}^{\prime}$ of $\kappa_{m}$ with $\|\kappa_{m}^{\prime}-\kappa\|_{\square}\leq{\delta_{\square}}(\kappa_{m},\kappa)+1/m$, say, and hence $\|\kappa_{m}^{\prime}-\kappa\|_{\square}\to 0$. Since $\rho(\kappa_{m}^{\prime})=\rho(\kappa_{m})$, in proving the result we may assume if we like that $\|\kappa_{m}-\kappa\|_{\square}\to 0$.

We shall prove the result in three steps.

Step 1: suppose that all $\kappa_{m}$ are irreducible; this case is the heart of the proof. For each $m$ we may find a sequence $A_{n}^{(m)}$ of symmetric $n$-by-$n$ matrices with ${\delta_{\square}}(A_{n}^{(m)},\kappa_{m})\to 0$ as ${n\to\infty}$. Indeed, this is an immediate consequence of Lemma 1.7. By Theorem 1.1, if $n$ is large enough, then

say. Pick $n(m)$ such that (10) holds and ${\delta_{\square}}(A_{n(m)}^{(m)},\kappa_{m})\leq 1/m$, and let $A_{m}=A_{n(m)}^{(m)}$. By (10), with probability $1$ we have

Step 2: we now consider the general case, where some of $\kappa$ and the $\kappa_{m}$ may be reducible. By Theorem 6.4(i) of , given a kernel $\kappa^{\prime}$ and a sequence $\kappa_{n}^{\prime}$ tending pointwise down to $\kappa^{\prime}$, we have $\rho(\kappa_{n}^{\prime})\to\rho(\kappa^{\prime})$. Applying this with $\kappa^{\prime}=\kappa_{m}$ and $\kappa_{n}^{\prime}=\kappa_{m}+1/n$, say, we see that for each $m$ there is an $\varepsilon_{m}<1/m$ such that $|\rho(\kappa_{m}^{\prime})-\rho(\kappa_{m})|\leq 1/m$, where $\kappa_{m}^{\prime}=\kappa_{m}+\varepsilon_{m}$. Now $\kappa_{m}^{\prime}$ is irreducible, and $\|\kappa_{m}^{\prime}-\kappa_{m}\|_{\square}\leq 1/m\to 0$, so ${\delta_{\square}}(\kappa_{m}^{\prime},\kappa)\to 0$, and the results of Step 1 apply. In particular, the upper bound (12) holds, and if $\kappa$ is irreducible, then $\rho(\kappa_{m})\to\rho(\kappa)$, as required.

Step 3: in the case where $\kappa$ is reducible, it remains to prove the lower bound corresponding to (12). For this we decompose $\kappa$ into irreducible kernels as in . As shown there (in Lemma 5.17), given any $\kappa$ there is a finite or countable partition $(S_{i})_{i=0}^{N}$, $N\leq\infty$, of ${\mathcal{S}}$ into measurable sets such that $\kappa=\sum_{i\geq 1}\kappa^{(i)}$ holds a.e., where each $\kappa^{(i)}$ is zero off ${\mathcal{S}}_{i}\times{\mathcal{S}}_{i}$ and irreducible when restricted to ${\mathcal{S}}_{i}\times{\mathcal{S}}_{i}$. Fix $\varepsilon>0$. Since $\rho(\kappa)=\sum\rho(\kappa^{(i)})$, there is some $k<\infty$ such that $\sum_{i=1}^{k}\rho(\kappa^{(i)})\geq\rho(\kappa)-\varepsilon$. Define $\kappa_{m}^{(i)}$ to be the kernel that is equal to $\kappa_{m}$ on ${\mathcal{S}}_{i}\times{\mathcal{S}}_{i}$ and zero off this set, and let $\kappa_{m}^{\prime}=\sum_{i=1}^{k}\kappa_{m}^{(i)}$. Then $\kappa_{m}\geq\kappa_{m}^{\prime}$, so $\rho(\kappa_{m})\geq\rho(\kappa_{m}^{\prime})=\sum_{i=1}^{k}\rho(\kappa_{m}^{(i)})$. Since $\|\kappa_{m}-\kappa\|_{\square}\geq\|\kappa_{m}^{(i)}-\kappa^{(i)}\|_{\square}$ for each $i$, we have $\|\kappa_{m}^{(i)}-\kappa^{(i)}\|_{\square}\to 0$ for each $i$. Since $\kappa^{(i)}$ is irreducible, by the result of Step 2 we have $\rho(\kappa_{m}^{(i)})\to\rho(\kappa^{(i)})$. Summing over $i$ from $1$ to $k$ it follows that

Since $\varepsilon>0$ was arbitrary we thus have $\liminf_{m\to\infty}\rho(\kappa_{m})\geq\rho(\kappa)$. Together with (12), this completes the proof. ∎

Note that Theorem 1.9 is a purely analytic statement about branching processes and the cut metric (or cut norm – rearrangements change nothing here). However, the only proof we know is that above, which goes via graphs! Corresponding results with much stronger assumptions (monotone convergence, either upwards or downwards) were proved in ; these weaker results were all that was needed there.

We close this section by giving a direct proof of a weaker form of Theorem 1.9, assuming $L^{1}$ convergence. As above, rearrangement is irrelevant, so it makes no difference whether we suppose that $\delta_{1}(\kappa_{n},\kappa)\to 0$ or $\|\kappa_{n}-\kappa\|_{L^{1}}\to 0$.

Let $\kappa_{n}$, $n\geq 1$, and $\kappa$ be kernels on a probability space $({\mathcal{S}},\mu)$, with $\|\kappa_{n}-\kappa\|_{L^{1}}\to 0$ as ${n\to\infty}$. Then $\rho(\kappa_{n})\to\rho(\kappa)$.

Note first that by the uniform boundedness principle we have $C=\sup\|f_{n}\|_{\infty}<\infty$. (In fact, in the application, each $f_{n}$ is bounded by $1$.)

Let $\varepsilon>0$. As in the proof of Lemma 1.7, there is a finite-type kernel $\kappa^{\prime}$ such that $\|\kappa-\kappa^{\prime}\|_{L^{1}}<\varepsilon$. We may express $\kappa^{\prime}$ as $\kappa^{\prime}(x,y)=\sum_{i=1}^{N}\varphi_{i}(x)\psi_{i}(y)$ for $\varphi_{i}$, $\psi_{i}\in L^{1}$. (In fact, we may take each $\varphi_{i}$ or $\psi_{i}$ to be a constant times a characteristic function.) Now

The first term above is at most $\|\kappa-\kappa^{\prime}\|_{L^{1}}\|f_{n}\|_{\infty}\leq\varepsilon C$. The second term is exactly

Each integral tends to zero by the definition (13) of the weak-$*$ topology, so it follows that $\limsup\|h_{n}\|_{L^{1}}\leq\varepsilon C$. Since $\varepsilon>0$ was arbitrary, the result follows. ∎

With this preparation behind us, we turn to the proof of Theorem 1.10.

We may assume without loss of generality that the $\sigma$-field $\mathcal{F}$ on ${\mathcal{S}}$ where $\mu$ is defined is countably generated, and thus $L^{1}({\mathcal{S}},\mu)$ is separable. One way to see this is to note that otherwise we can replace $\mathcal{F}$ by a countably generated sub-$\sigma$-field $\mathcal{F}_{0}$ such that each $\kappa_{n}$ is $\mathcal{F}_{0}\times\mathcal{F}_{0}$-measurable; alternatively, by the results of we may assume without loss of generality that ${\mathcal{S}}=$, with $\mu$ Lebesgue measure.

Suppose for simplicity that $\kappa$ is irreducible; arguing as in the proof of Theorem 1.9, it is not hard to reduce the general case to this case.

Suppose for a contradiction that $\|\kappa_{n}-\kappa\|_{L^{1}}\to 0$ but $\rho(\kappa_{n})\not\to\rho(\kappa)$. Passing to a subsequence, we may assume that $|\rho(\kappa_{n})-\rho(\kappa)|$ is bounded away from zero. To obtain a contradiction it then suffices to show that for some subsequence $(\kappa_{n_{i}})$ of $(\kappa_{n})$ we have $\rho(\kappa_{n_{i}})\to\rho(\kappa)$.

Let $\rho_{n}(x)=\rho_{\kappa_{n}}(x)$ be the survival probability of the branching process ${\mathfrak{X}}_{\kappa_{n}}(x)$, started with a single particle of type $x$. As shown in , the function $\rho_{n}$ satisfies

It is well known that the unit ball of $L^{\infty}({\mathcal{S}},\mu)$ is sequentially compact in the weak-$*$ topology when $L^{1}({\mathcal{S}},\mu)$ is separable. (The unit ball of $L^{\infty}$ is always compact, but not necessarily sequentially compact otherwise.) For the special case ${\mathcal{S}}=$, let $(f_{n})$ be a sequence in the unit ball of $L^{\infty}()$. This sequence has a subsequence $(f_{n_{k}})$ such that $\int_{I}f_{n_{k}}$ converges for each of the countably many intervals $I$ with rational endpoints. Since the $f_{n_{k}}$ are uniformly bounded, this is enough to ensure weak-$*$ convergence.

Also, by Lemma 1.11, $\|T_{\kappa}\rho_{n}-T_{\kappa}{\rho^{*}}\|_{L^{1}}\to 0$. Hence $T_{\kappa_{n}}\rho_{n}\to T_{\kappa}{\rho^{*}}$ in $L^{1}$. Passing to a subsequence, we may assume that $T_{\kappa_{n}}\rho_{n}\to T_{\kappa}{\rho^{*}}$ a.e. But then, using (14),

From (13) and dominated convergence, it follows that

Let $\rho(x)$ denote the survival probability of ${\mathfrak{X}}_{\kappa}(x)$. Since $\kappa$ is irreducible, by [4, Theorem 6.2], either ${\rho^{*}}=\rho$ a.e. or ${\rho^{*}}=0$ a.e. In the first case,

as desired. In the second case, we have $\rho(\kappa_{n})\to 0$ similarly.

All that remains is to rule out the possibility that $\rho(\kappa_{n})\to 0<\rho(\kappa)$. This is not hard using the results in . For $M>0$, let $\kappa^{M}$ denote the pointwise minimum of $\kappa$ and $M$, and define $\kappa_{n}^{M}$ similarly. Suppose that $\rho(\kappa)>0$. Then $\|T_{\kappa}\|>1$. As shown in the proof of [4, Lemma 5.16], we have $\|T_{\kappa^{M}}\|\nearrow\|T_{\kappa}\|$ as $M\to\infty$, so there is some $M$ with $c=\|T_{\kappa^{M}}\|>1$. Fix such an $M$. Since

and the kernels $\kappa_{n}^{M}$ and $\kappa^{M}$ are uniformly bounded, we have $\|T_{\kappa_{n}^{M}}\|\to\|T_{\kappa^{M}}\|=c>1$. In particular, for all large enough $n$ we have $\|T_{\kappa_{n}^{M}}\|>(c+1)/2>1$. Finally, it follows from [4, Remark 5.14] that we have

Since $\rho(\kappa_{n})\geq\rho(\kappa_{n}^{M})$ it follows that $\rho(\kappa_{n})\not\to 0$, and the proof is complete. ∎

If we assume cut convergence instead of $L^{1}$ convergence, then using the fact that

in place of the corresponding observation for the $L^{1}$ norm, the first part of the proof above goes through unchanged, showing that ${\rho^{*}}\to\rho$ a.e. or ${\rho^{*}}\to 0$. Unfortunately, we do not know how to exclude the possibility that $\rho(\kappa_{n})\to 0<\rho(\kappa)$, except by appealing to Theorem 1.1, i.e., working with graphs. The problem is that the relation equivalent to (15) for the cut norm rather than the $L^{1}$ norm does not hold in general. Of course, given that Theorem 1.9 is true, it is almost guaranteed that it has a direct analytic proof.

As discussed in [6, Section 2], until recently there was another example of an analytic fact about kernels whose only known proof involved graphs (and the cut metric), namely that two bounded kernels may be coupled to agree a.e. if and only if their ‘graphical moments’ (or subgraph counts) are equal. This follows from the results of Borgs, Chayes, Lovász, Sós and Vesztergombi concerning metrics for graphs (see ). However, by now there are analytic proofs: Janson and Diaconis showed that it also follows from results of Hoover and Kallenberg on exchangeable arrays. A direct (and far from simple) proof has recently been given by Borgs, Chayes and Lovász .

Proofs of Theorems 1.1–1.4

In this section we shall prove our main results; the strategy of the proof of Theorem 1.1 is as follows. First, in Subsection 2.1, we shall show that if each $\kappa_{n}$ is an $n$-by-$n$ kernel and ${\delta_{\square}}(\kappa_{n},\kappa)\to 0$, then almost all of the weight of $\kappa_{n}$ comes from values that are $o(n)$. This will allow us to assume that all edge probabilities in $G(A_{n})$ are $o(1)$. It then follows that the expected number of small tree components in $G(A_{n})$ is close to what it ‘should be’, i.e., $n$ times a certain function of the kernel $\kappa_{A_{n}}$. In Subsection 2.2 we show that this function is continuous with respect to the cut metric. This then tells us that we have almost the ‘right’ number of vertices in small components; the details are given in Subsection 2.3. Finally, in Subsection 2.4 we complete the proof of Theorem 1.1 by showing that in the irreducible case, almost all vertices in large components are in a single component, using a method from Bollobás, Borgs, Chayes and Riordan . In Subsection 2.5 we treat the reducible case, proving Theorem 1.2. Finally, in Subsection 2.6 we prove our stability and concentration results, Theorems 1.3 and 1.4.

For convenience, in this section we assume, as we may, that all kernels are on $$, unless explicitly stated otherwise.

In Theorem 2.1 of it was shown that if $(G_{n})$ is a sequence of graphs in which $G_{n}$ has $n$ vertices and $O(n)$ edges, $A_{n}$ is the adjacency matrix of $G_{n}$, $\kappa$ is a kernel and ${\delta_{\square}}(nA_{n},\kappa)\to 0$, then $\kappa=0$ a.e. and $e(G_{n})=o(n)$. A simple modification of the proof gives the following lemma. Recall that a matrix denoted $A_{n}$ is assumed to be $n$-by-$n$.

Suppose that $\kappa$ is a kernel and $(A_{n})$ a sequence of non-negative matrices such that ${\delta_{\square}}(A_{n},\kappa)\to 0$. Then there is some function $M(n)$ with $M(n)=o(n)$ such that only $o(n)$ entries of $A_{n}$ exceed $M(n)$, and the sum of these entries is $o(n^{2})$.

A consequence of this is that if $A_{n}^{\prime}$ is obtained from $A_{n}$ by taking the pointwise minimum with $M(n)$, then ${\delta_{\square}}(A_{n}^{\prime},\kappa)\to 0$.

Although the details are almost exactly the same as in , we spell them out. We write $\kappa_{n}$ for $\kappa_{A_{n}}$.

Since ${\delta_{\square}}(\kappa_{n},\kappa)\to 0$, we may choose rearrangements ${\kappa^{(\tau_{n})}}$ of $\kappa$ such that

It suffices to show that for any $c>0$, the sum of the entries of $A_{n}$ exceeding $cn$ is at most $c^{2}n^{2}$ for $n$ large enough. This implies that there are at most $cn$ such entries, and the result then follows by letting $c$ tend to $0$.

Suppose for a contradiction that there is some $c>0$ such that, for infinitely many $n$, the sum of the entries of $A_{n}$ exceeding $cn$ is at least $c^{2}n^{2}$; from now on we fix such a $c$ and restrict our attention to the corresponding values of $n$. Let $G_{n}$ be the graph whose edges correspond to those entries of $A_{n}$ which exceed $cn$. Let $M_{n}$ be a largest matching in $G_{n}$.

Suppose first that $|V(M_{n})|/n\to 0$. Let $S_{n}$ be the subset of $$corresponding to the vertex set of$M_{n}$, so$\mu(S_{n})=|V(M_{n})|/n\to 0$. Every edge of weight at least$cn$meets a vertex of$M_{n}$, so

where the factor 2 accounts for the double counting of edges within $V(M_{n})$.

From (16), writing $S_{n}^{\prime}$ for $\tau_{n}(S_{n})$, we have

so $\int_{S_{n}^{\prime}\times}\kappa\not\to 0$. Since $\mu(S_{n}^{\prime}\times)=\mu(S_{n}^{\prime})=\mu(S_{n})\to 0$, this contradicts integrability of $\kappa$.

Passing to a subsequence, we may thus assume that for some $a>0$, every maximal matching $M_{n}$ meets at least $an$ vertices.

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 of the event that $\kappa(x,y)>C$. In particular, there is a $C<\infty$ with $\int\kappa 1_{\{\kappa>C\}}\leq ac/4$. Fix an $n$ with $n>4C/(ac)$, noting that if $S\subset^{2}$ satisfies $\mu(S)\leq 1/n$, then

Choosing $n$ large enough, we may assume from (16) that there is a $\kappa^{\prime}={\kappa^{(\tau_{n})}}\sim\kappa$ with