the graphon limit of dense graphs
/ GRAF-on; LOH-vahs /
A graphon is the limit object for sequences of DENSE graphs — graphs where the number of edges is of order n^2, so the edge density stays bounded away from 0. Where Benjamini-Schramm convergence is the right notion for sparse graphs (local view), graphons are the right notion for dense ones (global view), capturing the limiting density of edges between every pair of vertex 'regions'. The question they answer is: in what sense does a sequence of larger and larger dense graphs converge, and what is the limit?
A graphon is a symmetric measurable function W from [0,1] x [0,1] to [0,1]; think of [0,1] as a continuum of vertices and W(x,y) as the probability (or density) of an edge between vertex-types x and y. Every finite graph G is itself a graphon W_G (the 0/1 step function on a grid given by its adjacency matrix), and the theory of Lovasz and Szegedy says: a sequence of dense graphs G_n converges if and only if, for every fixed small graph F, the homomorphism density t(F, G_n) (the probability that a uniformly random map of F's vertices into G_n's is edge-preserving) converges. This 'left-convergence' is equivalent to convergence in the cut metric, a distance that measures the largest discrepancy of edge densities over all pairs of vertex subsets — and the space of graphons modulo measure-preserving relabellings is compact in the cut metric (the Lovasz-Szegedy compactness theorem, proved using Szemeredi's regularity lemma). The limit of the sequence is a graphon W, and conversely sampling from a graphon (place n random points x_1, ..., x_n in [0,1], join i and j independently with probability W(x_i, x_j)) generates a W-random graph whose limit is W. Erdos-Renyi G(n,p) is the W-random graph for the constant graphon W identically equal to p; the stochastic block model is the W-random graph for a step-function graphon.
Graphons matter because they turn extremal and statistical questions about large dense graphs into analysis on a function space: subgraph densities become integrals against W, the limit theory explains and unifies the regularity lemma, quasirandomness, and property testing, and graphons are the natural nonparametric model for estimating the structure of a single large network (network histograms, stochastic-block-model fitting). The honest caveats are essential. First, graphons describe DENSE graphs only: a sparse graph (o(n^2) edges) has homomorphism densities all tending to 0, so its graphon limit is the zero graphon, which throws away all information — sparse graphs need Benjamini-Schramm or the separate theory of sparse graph limits (L^p graphons, graphings). Second, the graphon is unique only up to measure-preserving transformations of [0,1] (relabelling the continuum of vertices), so 'the' limit is really an equivalence class. Third, convergence in the cut metric is a global, density-level notion; it is insensitive to features involving o(n^2) edges, so two dense graphs with the same graphon can still differ in everything that is 'low-order'.
The Erdos-Renyi sequence G(n, 1/2) converges to the constant graphon W(x,y) = 1/2: every subgraph density behaves as if each edge is an independent fair coin, e.g. the triangle density t(K_3, G_n) tends to (1/2)^3 = 1/8. A stochastic block model with two equal communities, within-density 0.9 and between-density 0.1, converges to a 2-by-2 step-function graphon — the discrete blocks become a piecewise-constant W on [0,1]^2.
A graphon W on [0,1]^2 is the dense-graph limit; G(n,p) gives W = p, the block model gives a step function.
Graphons describe DENSE graphs only — a sparse graph's graphon limit is the useless zero graphon, so use Benjamini-Schramm there instead. The limit is unique only up to measure-preserving relabelling of [0,1], so it is an equivalence class, not a single function.