Lemma 6.3 (used in the proof of Theorem 1.2) — polynomial expression construction
OpenIntervalMaxCutEPTAS.Scheme.Supplement.lemma_6_3complexity-theorygraph-theorymax-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is one deterministic program, with absolute polynomial constants fixed before all instances, that takes a supplied structure of Proposition 4.10 and nonnegative integers bounding every valid cell by and . The graph has an expression using exactly the available label palette
The program outputs an adjacency bitmap and a valid expression for this same , with an explicit leaf bijection, in time and space at most for absolute constants. The input is followed by the published structure serialization. The word capacity may depend on , while the time polynomial does not. This is the constructive palette lemma for Theorem 1.2.
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: a clique-width expression, without excluding the empty graph → the published positive expressions plus an empty expression evaluated only on Empty; reason: this covers n = 0; identity relabeling allowed by the published language changes no graph or width
- reading: word-RAM operations on words of Θ(log n) bits, including accuracy and output addresses → charged Light operations with polynomial word capacity in the numeric input parameters and addresses; reason: the construction manipulates the accuracy and its polynomial-size output; this is the same transdichotomous word convention as the immutable base mission
- encoding: compute the graph and a width expression → the fixed prefix packet of width, adjacency matrix, expression and explicit leaf names; reason: the executable parser and published expression evaluation fix the meaning of every output word independently of the theorem
- encoding: polynomial time in n,K,J → uniform Light execution bounded by C(n+K+J+1)^d, with space bounded by the same polynomial; reason: all operations are charged and a polynomial-time execution touches at most polynomially many cells
Preamble
import Mathlib import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Supplement_WidthMachine set_option autoImplicit false
Formal statement
namespace IntervalMaxCutEPTAS.Scheme.Supplement
/-- Lemma 6.3, PDF 24 (printed 23). The supplied structure is input, the program is uniform,
and b affects word capacity but not the polynomial time bound in n,K,J. -/
theorem lemma_6_3 :
∃ (Prog : Light.Program) (C d c : ℕ), 0 < C ∧ 1 ≤ d ∧ 1 ≤ c ∧
∀ (n K J : ℕ) (P : Setup n), 4 ≤ P.b → P.θ < 2 * bigM n → GoodShift P →
(∀ a, IsCell n a → neighborhoodCount P a ≤ K ∧ (own P a).card ≤ J) →
HasExpression (H P) (3 * K + J + 1) ∧
∃ T S : ℕ, T ≤ C * (n + K + J + 1) ^ d ∧ S ≤ C * (n + K + J + 1) ^ d ∧
Light.Ends ⟨((n + P.b + K + J + 2) ^ c : ℕ), S, T⟩ Prog 0 entry
(start (encodeExpression P K J)) T
(ReportsExpression (H P) (3 * K + J + 1) S) := by sorry
end IntervalMaxCutEPTAS.Scheme.Supplement
Source
Morteza Alimi, Hani Ahmadzadeh, STOC 2027 submission #636 (October 2026), Lemma 6.3, PDF p. 24 (printed p. 23)