Lemma A.2 — each extends to a linear order
ProvedSingleMachinePrec.ConvexBipartite.lemma_A_2Let be a convex bipartite order whose plus jobs are numbered so that a smaller index never has a larger left end: for plus jobs , implies (the standing assumption of the Appendix, p. 667). Let for . Then each is an extension of in the sense used by the paper: it contains and it contains no cycle, so that it is contained in a linear order on . That is, for each there is a linear order on with
Since , every such is a linear extension of ; these are the three linear orders of the realizer in Lemma 4.1.
Formalization Note The paper calls "extensions of " and its proof shows that they "do not contain cycles"; the next paragraph takes "any linear extensions of ". The relation itself need not be transitive (with one plus job , : , , but ), so "is a partial order" would be false; the formal statement is the existence of a linear order containing , which is equivalent to acyclicity. The numbering assumption is the hypothesis Monotone C.l.
import Mathlib import Definitions.Def_SingleMachinePrec_ConvexBipartite_IncPartition
namespace SingleMachinePrec.ConvexBipartite
open ConvexBipartiteOrder
/-- Lemma A.2 (Ambühl et al. 2011, p. 668). Assume the plus jobs are numbered so that a smaller
plus index has a smaller or equal left end `l` (Appendix, p. 667). Then each of
`Ē₁ = E₁ ∪ P`, `Ē₂ = E₂ ∪ P`, `Ē₃ = E₃ ∪ P` is contained in a linear order on the jobs
("is an extension of P": it contains `P` and has no cycle), i.e. each has a linear extension. -/
theorem lemma_A_2 {a b : ℕ} (C : ConvexBipartiteOrder a b) (hnum : Monotone C.l) :
(∃ L : Job a b → Job a b → Prop, IsLinearExtension (C.Ebar C.E1) L) ∧
(∃ L : Job a b → Job a b → Prop, IsLinearExtension (C.Ebar C.E2) L) ∧
(∃ L : Job a b → Job a b → Prop, IsLinearExtension (C.Ebar C.E3) L) := by sorry
end SingleMachinePrec.ConvexBipartite
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.