Proposition 3.2 — the vertex cover graph G^S_P equals the graph of incomparable pairs G_P
ProvedSingleMachinePrec.Framework.prop_3_2Let be a partial order on a finite set of jobs. Let be the vertex cover graph of Correa and Schulz (nodes: the incomparable pairs; adjacency: the symmetric closure of the three-case rule of §2.2) and the graph of incomparable pairs of dimension theory (nodes: the incomparable pairs; edges: the 2-element sets of incomparable pairs that are minimal among the sets no linear extension of reverses entirely). Then
The proposition identifies the scheduling-side graph, defined through the constraints of an integer program, with a graph defined purely through the linear extensions of . It is what lets colorings and fractional colorings coming from realizers of be used for vertex cover in .
Formalization Note The two graphs are stated equal as SimpleGraphs on the common vertex type of incomparable pairs. The paper introduces for a poset that is not a linear order; the statement is made for every partial order (for a linear order both graphs have no vertices).
import Mathlib import Definitions.Def_SingleMachinePrec_Framework_VertexCoverGraph
namespace SingleMachinePrec.Framework
/-- **Proposition 3.2** (p. 657). For every finite poset `P`, the vertex cover graph `G^S_P` of
`1|prec|∑ w_j C_j` and the graph of incomparable pairs `G_P` coincide. -/
theorem prop_3_2 {N : Type*} [Fintype N] (P : N → N → Prop) [IsPartialOrder N P] :
vertexCoverGraph P = incPairsGraph P := by sorry
end SingleMachinePrec.Framework
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.