Lemma 6.2 (used in the proof of Theorem 1.2) — external neighborhood classes
OpenIntervalMaxCutEPTAS.Scheme.Supplement.lemma_6_2complexity-theorygraph-theorymax-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
In the same good-shift hierarchy with and , every nonroot cell satisfies
Here counts distinct actual external neighbor sets of vertices in and is zero for an empty . Both inequalities and the separate root bound are included. The lemma supplies the class bound used for the width construction.
Differences from the source:
- encoding: the structure fixed in Proposition 4.10 with b ≥ 4 and its good shift → the published Setup, valid heap cell indices, group representative ids and GoodShift; reason: these are the same constructed objects and standing assumptions; no geometric or density condition is added
- encoding: K(C) counts distinct external neighbor sets → the finite image of actual neighbor sets, with cardinality zero on empty VC; reason: all source instances and the root case are retained
Preamble
import Mathlib import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Supplement_Endpoints set_option autoImplicit false
Formal statement
namespace IntervalMaxCutEPTAS.Scheme.Supplement
/-- Lemma 6.2, PDF 23 (printed 22), including both inequalities and the root. -/
theorem lemma_6_2 {n : ℕ} (P : Setup n) (hb : 4 ≤ P.b)
(hθ : P.θ < 2 * bigM n) (hshift : GoodShift P) :
(∀ C, IsCell n C → C ≠ 1 →
neighborhoodCount P C ≤ (2 * (ancestralPositions P C).card + 1) ^ 2 ∧
(((2 * (ancestralPositions P C).card + 1) ^ 2 : ℕ) : ℝ) ≤
(20 * P.b / sigma P.b + 1) ^ 2) ∧
neighborhoodCount P 1 ≤ 1 := by sorry
end IntervalMaxCutEPTAS.Scheme.Supplement
Source
Morteza Alimi, Hani Ahmadzadeh, STOC 2027 submission #636 (October 2026), Lemma 6.2, PDF p. 23 (printed p. 22)