Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.1 — Simultaneous undominated vertices and vanishing error

Open
LocalProbeMIS871.Greedy.Supplement.lemma_4_1

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

local-computationmaximal-independent-setp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1probability

Let D0D_0D0​ be the graph experiment of §4.1, with degree parameter Δ\DeltaΔ, admissible clique count mmm, hidden independent set AAA of size NNN, and BBB partitioned into prescribed cliques CjC_jCj​ of size kkk. There is an absolute c∗>0c_*>0c∗​>0 such that for every sufficiently large Δ\DeltaΔ and then every sufficiently large admissible mmm,

Pr⁡D0[∀S⊆B, (∀j, ∣S∩Cj∣≤1)⟹∣A∖NG(S)∣≥N/4]≥1−ηc∗(Δ,m),\Pr_{D_0}\left[\forall S\subseteq B,\ \bigl(\forall j,\ |S\cap C_j|\le1\bigr)\Longrightarrow |A\setminus N_G(S)|\ge N/4\right]\ge1-\eta_{c_*}(\Delta,m),D0​Pr​[∀S⊆B, (∀j, ∣S∩Cj​∣≤1)⟹∣A∖NG​(S)∣≥N/4]≥1−ηc∗​​(Δ,m),

where NG(S)N_G(S)NG​(S) is the union of open neighborhoods and ηc∗(Δ,m)=exp⁡(mln⁡(k+1)−c∗N)\eta_{c_*}(\Delta,m)=\exp(m\ln(k+1)-c_*N)ηc∗​​(Δ,m)=exp(mln(k+1)−c∗​N). For each sufficiently large fixed Δ\DeltaΔ, this same error tends to zero as m→∞m\to\inftym→∞ through every admissible choice. The threshold for mmm may depend on Δ\DeltaΔ; the positive constant and degree threshold precede both inputs.

The event is simultaneous over selections made after the graph has been sampled. It supplies the structural separation used by the companion lower bound.

Formalization Note The existential witness is explicitly selected as 1/23041/23041/2304 using Eq. (40), not printed as a numerical constant in the lemma. The convergence clause is written in its equivalent epsilon-and-integer-threshold form along all admissible mmm.

Differences from the source:

  • encoding: vertices labeled in [n] → vertices represented by Fin n; reason: adding one to each label is a bijection and preserves all graph and oracle information
  • encoding: the finite distributions D₀ and D₁ of §4.1 → uniform counting on finite permutation seeds followed by the specified graph, list and query maps; reason: all fibers have constant multiplicity, so these are exactly the source laws, with no conditioning
  • encoding: an unspecified positive absolute c_* in η → the existential witness c_*=1/2304 from Eq. (40), shared by both lemmas; reason: h≤2N makes (N/12)^2/(8h)≥N/2304; this selects a witness without dropping any instance
  • encoding: η tends to zero along admissible m → for every ε>0, eventually |η|<ε for every admissible integer m; reason: this is precisely convergence on the source index domain
Preamble
import Definitions.Def_LocalProbeMIS871_Greedy_Supplement_Observation

open MeasureTheory
open scoped BigOperators Classical
noncomputable section
set_option autoImplicit false
Formal statement
namespace LocalProbeMIS871.Greedy.Supplement

/-- Lemma 4.1, printed p.25 / PDF27, including convergence along all admissible m.
The equality selects the source-derived witness from Eq.(40), not a changed bound. -/
theorem lemma_4_1 :
    ∃ c : ℝ, 0 < c ∧ c = cStar ∧ ∃ Δ₀ : ℕ, 2 ≤ Δ₀ ∧ ∀ Δ : ℕ, Δ₀ ≤ Δ →
      (∃ M : ℕ, ∀ m : ℕ, M ≤ m → Admissible Δ m →
        1 - eta c Δ m ≤ finiteProb (fun s : Seed Δ m => selectionGood s)) ∧
      (∀ ε : ℝ, 0 < ε → ∃ M : ℕ, ∀ m : ℕ, M ≤ m → Admissible Δ m →
        |eta c Δ m| < ε) := by sorry

end LocalProbeMIS871.Greedy.Supplement
Source
Peter Kiss, Yuichi Yoshida, The Local Probe Complexity of Maximal Independent Set, STOC 2027 submission #871 (October 2026), p. 25, PDF p. 27, Lemma 4.1

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