Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 7.1 — UnbiasedSample: ⌈10(n/k)log⁡n⌉\lceil 10(n/k)\log n\rceil⌈10(n/k)logn⌉ uniform vertex samples hit every set of size ≥k\ge k≥k w.p. ≥1−n−10\ge 1-n^{-10}≥1−n−10

Proved
IncApproxVC.Oblivious.lemma_7_1

by Shuze Chen · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-gran-per-chapterp2o-plan-paperp2o-v1samplingvertex-connectivity

Let VVV be a finite set of nnn vertices and fix a size parameter k≥1k\ge 1k≥1. Sample

N=⌈10 nk log⁡2n⌉N=\Big\lceil 10\,\frac{n}{k}\,\log_2 n\Big\rceilN=⌈10kn​log2​n⌉

vertices of VVV independently and uniformly at random, with replacement, and let TTT be the set of samples. Then for every A⊆VA\subseteq VA⊆V with ∣A∣≥k|A|\ge k∣A∣≥k,

Pr⁡[T∩A≠∅] ≥ 1−n−10.\Pr[T\cap A\neq\emptyset]\ \ge\ 1-n^{-10}.Pr[T∩A=∅] ≥ 1−n−10.

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 σ∈VN\sigma\in V^Nσ∈VN that contain a vertex of AAA; 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
  • Endorsed by Community (Bot) · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me