Block averaging and the cut norm

Block averaging a graphon over a measurable finite partition interacts well with the cut norm. Each block average is a Lipschitz function of the graphon in cut norm, with constant the inverse measure of the block (abs_blockAverage_sub_blockAverage_le), and block averaging is a contraction: the cut norm of the difference of two block-average step graphons is at most the cut norm of the difference of the graphons (cutNorm_stepGraphonAvg_sub_stepGraphonAvg_le).

The contraction holds because the integral of a block-average step graphon over a measurable rectangle S ×ˢ T is the integral of the graphon against the two [0, 1]-valued test functions recording, on each part, the proportion of the part lying in S (respectively T); such test integrals are bounded by the cut norm.

Main results

• TauCeti.DenseGraphLimits.abs_blockAverage_sub_blockAverage_le -- block averages are cut-norm Lipschitz;
• TauCeti.DenseGraphLimits.cutNorm_stepGraphonAvg_sub_stepGraphonAvg_le -- block averaging is a cut-norm contraction.

References

• L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), §9.2.

theorem TauCeti.DenseGraphLimits.abs_blockAverage_sub_blockAverage_le {Ω : Type u_1} [MeasurableSpace Ω] {μ : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure μ] (P : Finpartition Set.univ) (hP : ∀ p ∈ P.parts, MeasurableSet p) (W W' : Graphon Ω μ) (p q : ↥P.parts) : |↑(blockAverage P W p q) - ↑(blockAverage P W' p q)| ≤ (μ.real ↑p * μ.real ↑q)⁻¹ * cutNorm μ (W.toSymmKernel - W'.toSymmKernel)

A block average is a Lipschitz function of the graphon in cut norm, with constant the inverse measure of the block. On a null block both averages are zero and the constant is zero.

theorem TauCeti.DenseGraphLimits.cutNorm_stepGraphonAvg_sub_stepGraphonAvg_le {Ω : Type u_1} [MeasurableSpace Ω] {μ : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure μ] (P : Finpartition Set.univ) (hP : ∀ p ∈ P.parts, MeasurableSet p) (W W' : Graphon Ω μ) : cutNorm μ ((stepGraphonAvg P hP W).toSymmKernel - (stepGraphonAvg P hP W').toSymmKernel) ≤ cutNorm μ (W.toSymmKernel - W'.toSymmKernel)

Block averaging is a cut-norm contraction.