Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3.11 — for adjacent vertices u∈Iku\in I_ku∈Ik​, v∈Ilv\in I_lv∈Il​, k>lk>lk>l, the interval sets Tg,uT_{g,u}Tg,u​ and Tg,vT_{g,v}Tg,v​ are disjoint

Proved
FlowJobHardness.ColoringReduction.lemma_3_11

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

flow-shopgraph-coloringjob-shoplower-boundp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1

Let GGG be a simple graph on nnn vertices with a proper colouring into ddd classes I1,…,IdI_1,\dots,I_dI1​,…,Id​, let r≥2r \ge 2r≥2 be an integer, and let S(r,d)S(r,d)S(r,d) be the generalized flow shop instance of the colouring reduction. Fix a feasible schedule of all jobs and a threshold LLL; Tg,wT_{g,w}Tg,w​ is the set of first halves of the good long-operations on machine mg,wm_{g,w}mg,w​ of the jobs finishing within L⋅r2dL\cdot r^{2d}L⋅r2d.

Let u∈Iku \in I_ku∈Ik​ and v∈Ilv \in I_lv∈Il​ be adjacent vertices with k>lk > lk>l. Then for every group ggg with 1≤g≤r2d1 \le g \le r^{2d}1≤g≤r2d, every interval of Tg,uT_{g,u}Tg,u​ is disjoint from every interval of Tg,vT_{g,v}Tg,v​:

∀ I∈Tg,u, ∀ J∈Tg,v:I∩J=∅.\forall\, I \in T_{g,u},\ \forall\, J \in T_{g,v}: \quad I \cap J = \emptyset .∀I∈Tg,u​, ∀J∈Tg,v​:I∩J=∅.

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. u∈Iku\in I_ku∈Ik​, v∈Ilv\in I_lv∈Il​ with k>lk>lk>l is the hypothesis f(v)<f(u)f(v) < f(u)f(v)<f(u) on the frequencies f=c+1f = c+1f=c+1. 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 LLL. The bound r≥2r \ge 2r≥2 makes the paper's inequality r2(d−l)/2−r2(d−k)>r24r2(d−k)r^{2(d-l)}/2 - r^{2(d-k)} > \tfrac{r^2}{4}r^{2(d-k)}r2(d−l)/2−r2(d−k)>4r2​r2(d−k) ("using k>lk>lk>l", p. 20:11, proof of Lemma 2.3) hold. The paper leaves it implicit, since it takes rrr large.

Preamble
import Mathlib
import Definitions.Def_JobShopLTAS_Core_Instance
import Definitions.Def_FlowJobHardness_ColoringReduction_Construction
import Definitions.Def_FlowJobHardness_ColoringReduction_Schedule

open JobShopLTAS.Core
Formal statement
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
Source
Mastrolilli, Svensson, Hardness of Approximating Flow and Job Shop Scheduling Problems, J. ACM 58(5) (2011), Article 20, p. 20:18, Lemma 3.11
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me