The second sampling lemma

The W-random graph G(n, W) converges to W in cut distance in probability:

P(ε ≤ δ□(G(n, W), W)) → 0 as n → ∞, for every ε > 0,

where G(n, W) is read as a graphon on the unit interval through finiteGraphGraphon. The carrier of W is an arbitrary probability space.

The statement is about the finite sampling laws sampleGraph W n alone. It is proved through the padded exposure of G(n, W) (TauCeti.DenseGraphLimits.map_exposedSample), whose first coordinates are the sample points y, by passing through the weighted graph H(y, W), the pullback of W to the uniform carrier on Fin n:

• the edge coins move G(n, W) only a little away from H(y, W) (TauCeti.DenseGraphLimits.exposedSample_cutDist_comap_concentration, a union bound over cuts whose tail 2 · 4ⁿ · exp (-(εn/2 - 1)² / 2) vanishes);
• H(y, W) converges to W in probability (TauCeti.DenseGraphLimits.cutDist_comap_tendsto_inProbability).

Main result

• TauCeti.DenseGraphLimits.sampleGraph_cutDist_tendsto_inProbability — the second sampling lemma in probability.

References

• L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), Lemma 10.16.
• 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 TauCeti.DenseGraphLimits.sampleGraph_cutDist_tendsto_inProbability {Ω : Type u_1} [MeasurableSpace Ω] {μ : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure μ] (W : Graphon Ω μ) {ε : ℝ} (hε : 0 < ε) : Filter.Tendsto (fun (n : ℕ) => (sampleGraph W n).real {G : SimpleGraph (Fin n) | ε ≤ cutDist (finiteGraphGraphon G) W}) Filter.atTop (nhds 0)

The second sampling lemma, in probability. The W-random graph G(n, W), read as a graphon on the unit interval, is at cut distance at least ε from W with probability tending to zero as n → ∞, for every ε > 0. The carrier of W is an arbitrary probability space.