Lemma 6.1 (used in the proof of Theorem 1.2) — ancestral endpoint spacing
OpenIntervalMaxCutEPTAS.Scheme.Supplement.lemma_6_1complexity-theorygraph-theorymax-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix the rank representation and good-shift hierarchy of Proposition 4.10, with and . For every nonroot cell of length , every group anchored at a proper ancestor of , and every endpoint of its interval strictly inside ,
Independently of whether such a group exists, the distinct ancestral positions satisfy
This controls the number of boundary comparisons needed to determine an external neighborhood.
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: integer positions in an open real cell and h_g inequalities → finite sets of integer positions; distance and inequalities in ℝ; σ as an exact integer power; reason: distinct positions are counted once and all source inequalities are unchanged
Preamble
import Mathlib import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Supplement_Endpoints set_option autoImplicit false
Formal statement
namespace IntervalMaxCutEPTAS.Scheme.Supplement
/-- Lemma 6.1, PDF 23 (printed 22). The position bound does not require a group to exist. -/
theorem lemma_6_1 {n : ℕ} (P : Setup n) (hb : 4 ≤ P.b)
(hθ : P.θ < 2 * bigM n) (hshift : GoodShift P)
(C : ℕ) (hC : IsCell n C) (hroot : C ≠ 1) :
(∀ g ∈ groups P, IsProperAncestor (anchor P g) C →
∀ ξ ∈ ancestralPositions P C, (ξ = A P g ∨ ξ = B P g) →
(roundUnit P g : ℝ) ≥ max 1 (2 * sigma P.b ^ 2 * cellLen n C) ∧
(roundUnit P g : ℝ) > sigma P.b * boundaryDistance n C ξ / 2) ∧
((ancestralPositions P C).card : ℝ) ≤ 10 * P.b / sigma P.b := by sorry
end IntervalMaxCutEPTAS.Scheme.Supplement
Source
Morteza Alimi, Hani Ahmadzadeh, STOC 2027 submission #636 (October 2026), Lemma 6.1, PDF p. 23 (printed p. 22)