Ancestral endpoints and external neighborhoods
DefinitionIntervalMaxCutEPTAS_Scheme_Supplement_Endpointscomplexity-theorygraph-theorymax-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Fix the rank representation, dyadic hierarchy and good shift of §4. For a nonroot open cell , is the finite set of distinct integer endpoints of rounded groups anchored at proper ancestors of that lie strictly inside . Multiplicities are discarded. Define
In particular if is empty. The parameter is exactly . These statistics are shared by Lemmas 6.1–6.3; they count actual neighbor sets, rather than groups or labels.
Definition code
import Mathlib
import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Hierarchy
set_option autoImplicit false
namespace IntervalMaxCutEPTAS.Scheme.Supplement
open Classical
/-- §6.1: distinct ancestral integer endpoint positions in the open cell. -/
noncomputable def ancestralPositions {n : ℕ} (P : Setup n) (C : ℕ) : Finset ℤ :=
(((groups P).filter (fun g => IsProperAncestor (anchor P g) C)).biUnion
(fun g => {A P g, B P g})).filter (fun ξ => cellLo n C < ξ ∧ ξ < cellHi n C)
/-- Distance to the nearer boundary; used only for points inside a valid cell. -/
def boundaryDistance (n C : ℕ) (ξ : ℤ) : ℝ :=
min ((ξ : ℝ) - cellLo n C) ((cellHi n C : ℝ) - ξ)
/-- The actual external neighbors in H, on the original vertex set. -/
noncomputable def externalNeighbors {n : ℕ} (P : Setup n) (C : ℕ)
(v : Fin n) : Finset (Fin n) :=
Finset.univ.filter (fun u => u ∉ VC P C ∧ (H P).Adj v u)
/-- Number of distinct neighbor sets, zero when VC is empty. -/
noncomputable def neighborhoodCount {n : ℕ} (P : Setup n) (C : ℕ) : ℕ :=
((VC P C).image (externalNeighbors P C)).card
/-- The section's exact dyadic accuracy. -/
noncomputable def sigma (b : ℕ) : ℝ := (2 : ℝ) ^ (-(b : ℤ))
end IntervalMaxCutEPTAS.Scheme.Supplement
Source
Morteza Alimi, Hani Ahmadzadeh, STOC 2027 submission #636 (October 2026), §6–§6.1, PDF p. 23 (printed p. 22)