I am aiming to write a short post about each lecture in my ongoing course on *Random Graphs*. Details and logistics for the course can be found here.

By this point of the course, we’ve studied several aspects of the Erdos-Renyi random graph, especially in the sparse setting . We’ve also taken a lengthy detour to revise Galton-Watson trees, with a particular focus on the case of Poisson offspring distribution.

This is deliberate. Note that a given vertex v of has some number of neighbours distributed as , and the same approximation remains valid as we explore the graph (for example in a breadth-first fashion) either until we have seen a large number of vertices, or unless some ultra-pathological event happens, such as a vertex having degree n/3.

In any case, we are motivated by the notion that the local structure of is well-approximated by the Galton-Watson tree with offspring, and in this lecture and the next we try to make this notion precise, and discuss some consequences when we can show that this form of convergence occurs.

**Deterministic graphs**

Throughout, we will be interested in *rooted *graphs, since by definition we have to choose a root vertex whose local neighbourhood is to be studied. Usually, we will study a sequence of rooted graphs , where the vertex set of is [n], or certainly increasing in n (as in the first example).

For some rooted graph , we say such a sequence *converges to locally* if for all radii , we have . In words, the neighbourhood around in is the same up to radius r as the neighbourhood around in , so long as n is large enough (for given r).

This is best illustrated by an example, such as , the binary tree to depth n.

If we take to be the usual root, then the trees are nested, and converge locally to the infinite binary tree . Slightly less obviously, if we take to be one of the leaves, then the trees are still nested (up to labelling – ie in the sense of isomorphisms of rooted trees), and converge locally to the *canopy tree*, defined by a copy of with nearest-neighbour edges, and where each vertex is connected to the root of a disjoint copy of , as shown below:

Things get more interesting when the root is chosen randomly, for example, uniformly at random, as this encodes more global information about the graphs . In the case where the are vertex-transitive, then if we only care about rooted graphs up to isomorphism, then it doesn’t matter how we choose the root.

Otherwise, we say that converges in the *local weak sense* to if, for all and for all rooted graphs ,

as .

Alternatively, one can phrase this as a result about convergence of rooted-graph-valued distributions.

A simple non-transitive example is , the path of length n. Then, the r-neighbourhood of a vertex is isomorphic to , *unless* that vertex is within graph-distance (r-1) of one of the leaves of . As , the proportion of such vertices vanishes, and so, , from which we conclude the unsurprising result that converges in the local weak sense to . (Which is vertex-transitive, so it doesn’t matter where we select the root.)

The binary trees offer a slightly richer perspective. Let be the set of leaves of , and we claim that when is chosen uniformly from the vertices of , then converges in distribution. Indeed, , whenever , and so the given distance converges in distribution to the Geometric distribution with parameter 1/2 supported on {0,1,2,…}.

This induces a random local weak limit, namely the canopy tree, rooted at one of the vertices we denoted by , with the choice of this vertex given by Geometric(1/2). Continue reading