Bernoulli edge rounding of a sampled graph

The W-random graph G(n, W) is produced in two stages. First n independent positions y i are drawn from the carrier of the graphon; then every pair {i, j} becomes an edge independently, with probability W (y i) (y j). Between the two stages the sample is the weighted graph H(y, W) on n equally weighted vertices with edge weights W (y i) (y j), which is the pullback W.comap y of W to the uniform carrier on Fin n. The second stage rounds every weight to an edge or a non-edge by an independent coin, and this file shows that the rounding moves the sample only a little in cut distance: for the padded exposure of G(n, W), whose first coordinates are the positions,

P(ε ≤ δ□(G(n, W), H(y, W))) ≤ 2 · 4ⁿ · exp (-(εn - 1)² / 2) whenever 1 ≤ εn.

The right-hand side tends to zero as n → ∞ for every fixed ε > 0. It is the rounding half of the second sampling lemma δ□(G(n, W), W) → 0; the other half compares H(y, W) with W and involves the positions only.

The proof fixes the positions and a rectangle S × T of vertices. The number of edges of the sample inside S × T is then a function of the independent uniform coins of the exposure, and changing one coin changes it by at most 2, since a coin decides one pair {i, j} and S × T contains at most two orderings of that pair. McDiarmid's inequality makes the count sub-Gaussian around its mean, the total weight of the off-diagonal pairs of S × T. On a finite carrier the cut norm is attained at a rectangle, so a large cut distance forces a large deviation at one of the 4ⁿ rectangles, and a union bound concludes. The diagonal, where the sample has no loops while H(y, W) carries the weights W (y i) (y i), contributes at most 1 / n: that is the -1 in the exponent.

Main result

• TauCeti.DenseGraphLimits.exposedSample_cutDist_comap_concentration — the rounding estimate above.

References

• L. Lovász, Large Networks and Graph Limits, AMS Colloquium Publications 60 (2012), Chapter 10: the W-random graphs H(n, W) and G(n, W), and the second sampling lemma (Lemma 10.16), whose proof passes from H(n, W) to G(n, W) by this rounding.
• C. McDiarmid, On the method of bounded differences, Surveys in Combinatorics 141 (1989), 148–188.

theorem TauCeti.DenseGraphLimits.exposedSample_cutDist_comap_concentration {Ω : Type u_1} [MeasurableSpace Ω] {μ : MeasureTheory.Measure Ω} [MeasureTheory.IsProbabilityMeasure μ] {n : ℕ} [NeZero n] (W : Graphon Ω μ) {ε : ℝ} (hε : 1 ≤ ε * ↑n) : (exposureMeasure μ n).real {x : Fin n → Ω × (Fin n → ℝ) | ε ≤ cutDist (finiteGraphGraphon (exposedSample W x)) (W.comap (fun (i : Fin n) => (x i).1) ⋯ (ProbabilityTheory.uniformOn Set.univ))} ≤ 2 * 4 ^ n * Real.exp (-(ε * ↑n - 1) ^ 2 / 2)

Bernoulli edge rounding. Sample G(n, W) through its padded exposure x, whose first coordinates (x i).1 are the positions of the vertices. The sampled graph is at cut distance at least ε from the weighted graph H(y, W) — the pullback of W along the positions to the uniform carrier on Fin n — with probability at most 2 · 4ⁿ · exp (-(εn - 1)² / 2), as soon as 1 ≤ εn.