Convergence of graphons through homomorphism densities #
A sequence in the cut-distance quotient of graphons on a fixed probability carrier converges
exactly when the homomorphism density of every finite simple graph converges to that of the limit
(tendsto_graphonSpace_iff_forall_homDensity), and it is Cauchy exactly when every homomorphism
density is Cauchy (cauchySeq_graphonSpace_iff_forall_homDensity_cauchySeq). Thus finite-graph
densities give all the coordinates needed to test convergence of dense graph limits. Whenever the
graphon space is complete -- on the unit interval, or on any atomless standard Borel carrier -- a
sequence has a limit in graphon space as soon as all its homomorphism densities converge
(exists_tendsto_graphonSpace_iff_forall_homDensity_cauchySeq).
The carriers need not be fixed. For graphons Wₙ on arbitrary, possibly different, probability
carriers, δ□(Wₙ, W) → 0 exactly when t(F, Wₙ) → t(F, W) for every F
(tendsto_cutDist_iff_forall_homDensity_tendsto), and δ□(Wⱼ, Wₖ) → 0 as j, k → ∞ exactly
when every t(F, Wₖ) is Cauchy (tendsto_cutDist_prod_iff_forall_homDensity_cauchySeq). The
sequence converges in cut distance to some graphon on a given atomless standard Borel carrier,
such as the unit interval, exactly when all its homomorphism densities converge
(exists_graphon_tendsto_cutDist_iff_forall_homDensity_cauchySeq), that is, exactly when it is
Cauchy in cut distance (exists_graphon_tendsto_cutDist_iff_tendsto_cutDist_prod). Read on the
step graphons of finite graphs, this is the theory of convergent graph sequences: a sequence of
finite graphs converges to a graphon W in the cut distance of step graphons exactly when all its
finite homomorphism densities converge to those of W
(tendsto_cutDist_finiteGraphGraphon_iff_forall_homDensityFin_tendsto), it is Cauchy in cut
distance exactly when all its finite homomorphism densities are Cauchy
(tendsto_cutDist_finiteGraphGraphon_prod_iff_forall_homDensityFin_cauchySeq), and it has a
limit graphon on any given atomless standard Borel carrier exactly when all its finite
homomorphism densities converge
(exists_graphon_tendsto_cutDist_finiteGraphGraphon_iff_forall_homDensityFin_cauchySeq).
The compactness argument runs on the canonical carrier (I, volume), where the joint
homomorphism-density map homDensityCoords is a closed embedding of the compact space
GraphonSpaceI into a product of lines (isClosedEmbedding_homDensityCoords). The isometric
embedding of every fixed-carrier graphon space into the unit-interval one (toGraphonSpaceI) and
the unit-interval representative of every graphon (Graphon.unitIntervalRepr) carry the
equivalences to arbitrary carriers, and the representation of every graphon on an atomless
standard Borel carrier (exists_graphon_cutDist_eq_zero) places the limits there.
References #
- L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), Theorem 11.5 and Chapter 11.
- L. Lovász and B. Szegedy, Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), 933–957: every convergent graph sequence has a limit graphon.
- C. Borgs, J. Chayes, L. Lovász, V. Sós, K. Vesztergombi, Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), 1801–1851, Theorem 3.8.
Convergence in graphon space is convergence of all homomorphism densities. A sequence in the graphon space over any probability carrier converges in cut distance if and only if the homomorphism density of every finite simple graph converges to that of the limit.
Cauchy sequences in graphon space are those with Cauchy homomorphism densities. A sequence in the graphon space over any probability carrier is Cauchy in cut distance if and only if the homomorphism density of every finite simple graph is a Cauchy sequence.
A sequence of graphons with convergent homomorphism densities converges. Over a carrier whose graphon space is complete -- the unit interval, or any atomless standard Borel carrier -- a sequence in graphon space has a limit if and only if the homomorphism density of every finite simple graph is a Cauchy, hence convergent, sequence.
Cut-distance convergence is convergence of all homomorphism densities, for graphons on
arbitrary, possibly different, probability carriers: δ□(Wₙ, W) → 0 if and only if
t(F, Wₙ) → t(F, W) for every finite simple graph F.
Cut-distance Cauchy sequences are those with Cauchy homomorphism densities, for graphons
on arbitrary, possibly different, probability carriers: δ□(Wⱼ, Wₖ) → 0 as j, k → ∞ if and
only if the homomorphism density t(F, Wₖ) of every finite simple graph F is a Cauchy
sequence.
A sequence of graphons with convergent homomorphism densities has a limit graphon, on every
atomless standard Borel carrier (Ω', μ'), such as the unit interval: a sequence of graphons on
arbitrary, possibly different, probability carriers converges in cut distance to some graphon on
(Ω', μ') if and only if the homomorphism density of every finite simple graph is a Cauchy, hence
convergent, sequence.
Cut distance is complete across carriers. A sequence of graphons on arbitrary, possibly
different, probability carriers converges in cut distance to some graphon on a given atomless
standard Borel carrier (Ω', μ') if and only if it is Cauchy in cut distance.
Convergence of a graph sequence to a graphon. A sequence of finite graphs Gₙ on nonempty
vertex sets converges to a graphon W, on any probability carrier, in the cut distance of their
step graphons if and only if every finite homomorphism density t(F, Gₙ) converges to
t(F, W).
Cut-distance Cauchy graph sequences are those with Cauchy homomorphism densities. A
sequence of finite graphs Gₙ on nonempty vertex sets is Cauchy in the cut distance of their step
graphons if and only if every finite homomorphism density t(F, Gₙ) is a Cauchy sequence.
Every convergent graph sequence has a limit graphon (Lovász--Szegedy), on every atomless
standard Borel carrier (Ω, μ), such as the unit interval. A sequence of finite graphs on nonempty
vertex sets converges in the cut distance of step graphons to some graphon on (Ω, μ) if and only
if every finite homomorphism density t(F, Gₙ) is a Cauchy, hence convergent, sequence.