Lemma 7.1 — UnbiasedSample: uniform vertex samples hit every set of size w.p.
ProvedIncApproxVC.Oblivious.lemma_7_1p2o-gran-per-chapterp2o-plan-paperp2o-v1samplingvertex-connectivity
Let be a finite set of vertices and fix a size parameter . Sample
vertices of independently and uniformly at random, with replacement, and let be the set of samples. Then for every with ,
Algorithm 3 uses it to find a vertex on the right side of a vertex cut whose right side is large.
Formalization Note. The probability is the fraction of sequences that contain a vertex of ; logarithms are base 2 (p. 2).
Differences from the source:
- encoding: Pr over N vertices sampled uniformly with replacement → the fraction of sequences σ : Fin N → V containing a vertex of A; reason: uniform sampling with replacement is the uniform law on V^N
- encoding: size parameter k ≥ 1 → k : ℝ with 1 ≤ k; reason: the paper calls it with non-integer k = n − (1+ε)κ (Algorithm 3, line 9); integers are a special case
Preamble
import Mathlib
Formal statement
namespace IncApproxVC.Oblivious
/-- **Lemma 7.1** (`UnbiasedSample(G, k)`), p. 23. Fix a size parameter `k ≥ 1`. Sampling
`⌈10 (n/k) log₂ n⌉` vertices of `V` independently and uniformly at random with replacement gives a
set `T` with `Pr[T ∩ A ≠ ∅] ≥ 1 − n^{−10}` for every `A ⊆ V` with `|A| ≥ k`. The probability is the
fraction of sequences `σ : Fin N → V` that contain a vertex of `A`. -/
theorem lemma_7_1 {V : Type*} [Fintype V] [DecidableEq V] (k : ℝ) (hk : 1 ≤ k)
(A : Finset V) (hA : k ≤ (A.card : ℝ)) :
((Finset.univ.filter (fun σ : Fin ⌈10 * ((Fintype.card V : ℝ) / k) *
Real.logb 2 (Fintype.card V)⌉₊ → V => ∃ j, σ j ∈ A)).card : ℝ) /
(Fintype.card (Fin ⌈10 * ((Fintype.card V : ℝ) / k) *
Real.logb 2 (Fintype.card V)⌉₊ → V) : ℝ) ≥
1 - (Fintype.card V : ℝ) ^ (-10 : ℝ) := by sorry
end IncApproxVC.Oblivious
Source
Adena, Henzinger, Rutschmann, Incremental Approximate Vertex Connectivity via Almost-Linear Time Local Cut Algorithms, STOC 2027 submission (manuscript sha256 d6baac6b…), p. 23, Lemma 7.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.