Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.2 — the vertex cover graph G^S_P equals the graph of incomparable pairs G_P

Proved
SingleMachinePrec.Framework.prop_3_2

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

dimension-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1posetsvertex-cover

Let PPP be a partial order on a finite set NNN of jobs. Let GPSG^S_PGPS​ 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 GPG_PGP​ 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 PPP reverses entirely). Then

GPS=GP.G^S_P = G_P.GPS​=GP​.

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 PPP. It is what lets colorings and fractional colorings coming from realizers of PPP be used for vertex cover in GPSG^S_PGPS​.

Formalization Note The two graphs are stated equal as SimpleGraphs on the common vertex type of incomparable pairs. The paper introduces GPG_PGP​ 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).

Preamble
import Mathlib
import Definitions.Def_SingleMachinePrec_Framework_VertexCoverGraph
Formal statement
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
Source
Ambühl, Mastrolilli, Mutsanas, Svensson, On the Approximability of Single-Machine Scheduling with Precedence Constraints, Math. Oper. Res. 36(4) (2011), p. 657, Proposition 3.2
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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