Lemma 3.11 — for adjacent vertices , , , the interval sets and are disjoint
ProvedFlowJobHardness.ColoringReduction.lemma_3_11Let be a simple graph on vertices with a proper colouring into classes , let be an integer, and let be the generalized flow shop instance of the colouring reduction. Fix a feasible schedule of all jobs and a threshold ; is the set of first halves of the good long-operations on machine of the jobs finishing within .
Let and be adjacent vertices with . Then for every group with , every interval of is disjoint from every interval of :
Thus at any moment, among the first halves of good long-operations in one machine group, adjacent vertices are never active simultaneously. This is what turns a point of heavy overlap into an independent set.
Formalization Note. , with is the hypothesis on the frequencies . The paper states the lemma for "a schedule" in the context of Lemma 3.9; it is stated here for every feasible schedule and every threshold . The bound makes the paper's inequality ("using ", p. 20:11, proof of Lemma 2.3) hold. The paper leaves it implicit, since it takes large.
import Mathlib import Definitions.Def_JobShopLTAS_Core_Instance import Definitions.Def_FlowJobHardness_ColoringReduction_Construction import Definitions.Def_FlowJobHardness_ColoringReduction_Schedule open JobShopLTAS.Core
namespace FlowJobHardness.ColoringReduction
/-- **Lemma 3.11** (Mastrolilli–Svensson 2011, p. 20:18). Let `r ≥ 2`, let `s` be a feasible
schedule of `S(r, d)`, and let `u ∈ I_k`, `v ∈ I_l` be adjacent vertices with `k > l`. Then for
every group `g` (and every threshold `L` defining which jobs are kept), every interval of
`T_{g,u}` is disjoint from every interval of `T_{g,v}`. -/
theorem lemma_3_11 {n d : ℕ} (G : SimpleGraph (Fin n)) (c : G.Coloring (Fin d)) (r : ℕ)
(hr : 2 ≤ r) (s : (inst G c r).Op → ℝ)
(hs : (inst G c r).IsFeasibleSchedule Finset.univ s)
(u v : Fin n) (huv : G.Adj u v) (hfreq : freq c v < freq c u)
(L : ℝ) (g : ℕ) (hg1 : 1 ≤ g) (hg2 : g ≤ R r d) :
∀ I ∈ T G c r s L g u, ∀ J ∈ T G c r s L g v, Disjoint I J := by sorry
end FlowJobHardness.ColoringReduction
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.