Cut-norm limits of graphon sequences

On a countably generated probability carrier, a sequence of graphons that is Cauchy in the cut norm converges in the cut norm to a graphon: the space of graphons on a fixed such carrier is complete for the cut norm.

The limit is built from block averages. Along the canonical refining finite partitions of the carrier, the block averages of a cut-norm Cauchy sequence converge blockwise, because each block average is a cut-norm Lipschitz function of the graphon. The limiting block values define a sequence of step graphons which is a bounded martingale for the square filtration of the canonical partitions, hence converges almost everywhere and in L¹; its limit, symmetrised and clamped, is the limiting graphon. The cut-norm convergence of the original sequence then follows from the cut-norm contraction of block averaging, which makes the block approximation uniform along the Cauchy sequence.

This is the analytic input to the compactness of the space of graphons: after the terms of a Cauchy sequence in cut distance have been realised on one carrier, this theorem supplies the limit.

Main result

• TauCeti.DenseGraphLimits.exists_graphon_tendsto_cutNorm_of_cauchy_cutNorm -- a cut-norm Cauchy sequence of graphons converges in cut norm to a graphon.

References

• L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), §9.3.
• L. Lovász and B. Szegedy, Szemerédi's Lemma for the Analyst, GAFA 17 (2007), §5.

theorem TauCeti.DenseGraphLimits.exists_graphon_tendsto_cutNorm_of_cauchy_cutNorm {Ω : Type u_1} [MeasurableSpace Ω] [MeasurableSpace.CountablyGenerated Ω] {μ : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure μ] (V : ℕ → Graphon Ω μ) (hV : ∀ ε > 0, ∃ (N : ℕ), ∀ m ≥ N, ∀ n ≥ N, cutNorm μ ((V m).toSymmKernel - (V n).toSymmKernel) < ε) : ∃ (U : Graphon Ω μ), Filter.Tendsto (fun (n : ℕ) => cutNorm μ ((V n).toSymmKernel - U.toSymmKernel)) Filter.atTop (nhds 0)

Cut-norm Cauchy sequences of graphons converge in cut norm. On a countably generated probability carrier, a sequence of graphons that is Cauchy for the cut norm has a graphon limit in the cut norm. Together with the realisation of cut-distance Cauchy sequences on one carrier, this is the analytic input to the compactness of the space of graphons.