Lemma 7.4 (used in the proof of Theorem 1.3) — attachment cut bound
OpenIntervalMaxCutEPTAS.Scheme.Supplement.lemma_7_4complexity-theorygraph-theorymax-cutp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a simple graph with at least one edge and let . For every target cut and every attachment , write for its number of cut edges and for the number of source neighbors whose same-copy cores lie across the cut from . Then
Equality holds whenever the middle lies on the side of its core and every private vertex of this attachment lies on the other side. This is a sufficient equality condition, with no uniqueness claim when . Core-core edges are not part of the attachment. The bound controls every target cut for the optimum and decoding lemma.
Differences from the source:
- encoding: finite vertices and one-based copy and repetition indices → Fin n, Fin 2, and Fin p; dependent private indices; reason: these are bijective renamings, with exactly the source number of vertices and no padding
- encoding: cut edges of attachment (i,v,j) → cutCount of the subgraph of actual target edges incident with that attachment; reason: the middle and its private vertices identify the attachment; this excludes core-core edges and counts each edge once
Preamble
import Mathlib import Definitions.Def_IntervalMaxCutEPTAS_Scheme_Supplement_Gadget set_option autoImplicit false
Formal statement
namespace IntervalMaxCutEPTAS.Scheme.Supplement
/-- Lemma 7.4, PDF 26 (printed 25): upper bound for every cut and the full sufficient
equality case, without a uniqueness assertion. -/
theorem lemma_7_4 {n : ℕ} (Q : SimpleGraph (Fin n)) [DecidableRel Q.Adj]
(p : ℕ) (hm : 1 ≤ Q.edgeFinset.card) (hp : 1 ≤ p)
(a : Attachment n p) (S : Finset (TargetVertex Q p)) :
attachmentCut Q p a S ≤ 2 * (Q.degree a.vertex + 1) + crossingDegree Q p a.copy a.vertex S ∧
(((middle Q p a ∈ S ↔ core Q p a.copy a.vertex ∈ S) ∧
∀ t : Fin (Q.degree a.vertex + 1),
(privateVertex Q p a t ∈ S ↔ core Q p a.copy a.vertex ∉ S)) →
attachmentCut Q p a S = 2 * (Q.degree a.vertex + 1) +
crossingDegree Q p a.copy a.vertex S) := by sorry
end IntervalMaxCutEPTAS.Scheme.Supplement
Source
Morteza Alimi, Hani Ahmadzadeh, STOC 2027 submission #636 (October 2026), Lemma 7.4, PDF p. 26 (printed p. 25)