Lemma 4.1 — Simultaneous undominated vertices and vanishing error
OpenLocalProbeMIS871.Greedy.Supplement.lemma_4_1Let be the graph experiment of §4.1, with degree parameter , admissible clique count , hidden independent set of size , and partitioned into prescribed cliques of size . There is an absolute such that for every sufficiently large and then every sufficiently large admissible ,
where is the union of open neighborhoods and . For each sufficiently large fixed , this same error tends to zero as through every admissible choice. The threshold for may depend on ; 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 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 .
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
import Definitions.Def_LocalProbeMIS871_Greedy_Supplement_Observation open MeasureTheory open scoped BigOperators Classical noncomputable section set_option autoImplicit false
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