Dense graph limits and graphons

For a finite graph on n vertices, split the unit interval into n equal pieces and put its adjacency value on each corresponding rectangle. Diagonal vertex rectangles have value zero because there are no loops. Sampling independent uniform points then samples finite vertices with replacement, so collisions are possible. For a graphon W, the homomorphism density of a fixed simple graph F integrates a factor W for every edge of F over one variable per source vertex. There are no factors for nonedges.

For a constant graphon of value p, the factors are constant and its F-density is p raised to the number of F's edges. A balanced complete bipartite graphon instead has value one across its two half-intervals and zero within them. Both it and the constant one-half graphon have edge homomorphism density one half, but their triangle densities differ. Average edge density therefore cannot determine all higher pattern densities. The location of the mass in the kernel carries structural information.

To ask for a specified labeled induced pattern, multiply a W factor for each required edge and a one-minus-W factor for each required nonedge. For a constant graphon, a labeled three-vertex path has probability p squared times one minus p. The probability that the sampled unlabelled graph is some three-vertex path is three times larger, because there are three choices of the missing edge. Labels and isomorphism types therefore give different finite probabilities even when the same graph name is used.

For a finite graph, the homomorphism count and the injective embedding count differ by at most a constant times n to the v(F) minus one when F is fixed. Collisions thus disappear after dense normalization as n grows, but the exact finite normalizations remain different. In particular, triangle homomorphisms into a loopless graph must be injective, giving six times its unlabelled triangle count divided by n cubed. There is no automatic replacement of this denominator by the number of vertex triples.

The cut norm tests a kernel by integrating it over every measurable rectangle S times T. Cut distance permits measure-preserving relabelings of the unit interval before comparing kernels. Distinct coordinate representations can have distance zero and the same finite homomorphism densities. The quotient by this zero-distance relation is the useful graphon space; it is not a quotient group, nor must equivalence be witnessed by one pointwise bijective relabeling. Refining a block representation may change its written matrix without changing the underlying limit information.

A sequence is left-convergent when the homomorphism density of every fixed finite simple graph converges. The dense graph-limit theorem identifies such limits with graphons, unique up to cut-distance-zero equivalence. This theorem is stated here rather than proved; its compactness and counting arguments require measurable analysis. All graph sequences with uniformly bounded degrees and orders tending to infinity converge to the zero graphon in this normalization because their edge densities tend to zero, as do densities of patterns containing an edge. Distinguishing their local geometry therefore needs a different sparse or local limit framework.