Benjamini-Schramm local weak convergence

Benjamini-Schramm convergence is the right notion of a limit for a sequence of large sparse graphs: instead of asking what the whole graph looks like, you ask what a small neighbourhood around a typical (randomly chosen) vertex looks like. It captures the local geometry — the view from a random vertex — and makes precise the idea, already used in the branching heuristic, that 'G(n, c/n) looks locally like a Poisson(c) Galton-Watson tree'. The question it answers is: in what sense does a sequence of finite graphs of growing size have a limiting local structure?

Formally, a finite graph G_n is turned into a probability measure on the space of rooted graphs by picking a uniformly random vertex to be the root and recording the isomorphism type of the ball of each radius around it. The sequence G_n converges in the Benjamini-Schramm sense to a (random) rooted graph (U, o) if, for every fixed radius r and every finite rooted graph H, the probability that the r-ball around the random root of G_n is isomorphic to H converges to the corresponding probability for (U, o). This is exactly weak convergence of measures on the (Polish) space of rooted locally-finite graphs, where the topology is generated by these finite-radius neighbourhood events — hence 'local weak convergence'. The limit object is a unimodular random rooted graph (the analogue of a stationary measure, satisfying a mass-transport / reversibility condition). The classic examples: G(n, c/n) converges to the Poisson(c) Galton-Watson tree rooted at its origin; the random d-regular graph converges to the infinite d-regular tree; a configuration model converges to a Galton-Watson tree with size-biased offspring. The 'objective method' (Aldous-Steele) uses such a limit as the object on which one computes limiting averages of additive graph parameters.

This viewpoint matters because many global quantities are continuous with respect to local convergence and can therefore be computed on the limit tree, which is usually far simpler than the finite graph: the limiting fraction of vertices in components of each size, the matching number, the size of the giant via the survival probability, spectral measures, and (a deep theorem) the limiting number of spanning trees and the entropy of various combinatorial structures. It also underlies the modern theory of graph limits for sparse graphs (the sparse counterpart of graphons). The honest caveats: local weak convergence sees ONLY the local structure, so it is blind to genuinely global features — it cannot detect whether the graph is connected, what its diameter is, or its chromatic number, because these are not local; two graphs with the same local limit can differ globally. And the limit being a single rooted tree relies on the graphs being sparse and locally tree-like; for dense graphs this notion is trivial (every neighbourhood is huge) and one needs the graphon limit instead.