Theorem 7.1 — the odd-cycle LP and its dual have zero–one optima on series-parallel networks
ProvedChvatalPolytopes.SeriesParallel.odd_cycle_lp_zero_one_optimaLet be a finite series-parallel network, i.e. a graph containing no homeomorph of . Consider the linear program
where (7.1) is (), (), and for every vertex set inducing an odd circuit in . Then both this problem and its linear programming dual have zero–one optimal solutions:
- there is a zero–one vector satisfying (7.1) with for every real satisfying (7.1);
- there is a zero–one dual feasible point whose dual objective is at most that of every real dual feasible point.
In particular the maximum of the relaxation equals the stability number , attained at a stable set, and a zero–one dual optimum certifies it by covering the vertices with vertices, edges and induced odd circuits.
Formalization Note The dual is the one fixed in the OddCycleLP definition file: as sign constraints, dual variables on vertices, on edges and on , and the covering constraint . Optimality is against all real feasible points of the respective program, not only zero–one ones. The theorem does not assume nonempty; for the empty graph both programs are trivial.
import Mathlib import Definitions.Def_ChvatalPolytopes_SeriesParallel_IsSeriesParallel import Definitions.Def_ChvatalPolytopes_SeriesParallel_OddCycleLP
namespace ChvatalPolytopes.SeriesParallel
/-- **Theorem 7.1** (Chvátal 1975, p. 151). Let `G = (V, E)` be a series-parallel network. Then
both the problem of maximizing `∑ (x_u : u ∈ V)` subject to (7.1) and its linear programming dual
have zero–one optimal solutions.
(a) Some zero–one vector `x` satisfying (7.1) has `∑ x_u ≥ ∑ x'_u` for every *real* `x'`
satisfying (7.1).
(b) Some zero–one dual feasible `(y, z, w)` has dual objective at most that of every real dual
feasible point. The dual is the one of `DualFeasible`/`dualValue` (`0 ≤ x_u` as sign
constraints). -/
theorem odd_cycle_lp_zero_one_optima {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] (hG : IsSeriesParallel G) :
(∃ x : V → ℝ, (∀ u, x u = 0 ∨ x u = 1) ∧ OddCycleFeasible G x ∧
∀ x' : V → ℝ, OddCycleFeasible G x' → primalValue x' ≤ primalValue x) ∧
(∃ (y : V → ℝ) (z : G.edgeSet → ℝ) (w : {C : Finset V // C ∈ oddCircuits G} → ℝ),
(∀ u, y u = 0 ∨ y u = 1) ∧ (∀ e, z e = 0 ∨ z e = 1) ∧ (∀ C, w C = 0 ∨ w C = 1) ∧
DualFeasible G y z w ∧
∀ (y' : V → ℝ) (z' : G.edgeSet → ℝ) (w' : {C : Finset V // C ∈ oddCircuits G} → ℝ),
DualFeasible G y' z' w' → dualValue G y z w ≤ dualValue G y' z' w') := by sorry
end ChvatalPolytopes.SeriesParallel
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be any finite type of vertices with decidable equality; it may be empty. Let be a simple graph on with a decidable adjacency relation. The one hypothesis is that satisfies the predicate . This predicate comes from an imported definition that is not shown here, so what it requires cannot be stated from this code. The statement also uses five other imported, undisplayed notions:
- : a property of a real vector that depends on .
- : a real number computed from alone. It does not take as an argument.
- : a collection of finite vertex subsets . Let be the set of its members.
- : a property of a triple , (one real per edge of ), (one real per member of ).
- : a real number computed from the same triple.
None of these is unfolded here. Their meaning, including whether they encode an "odd cycle" linear program and its dual, rests entirely on their definitions. The theorem's doc comment describes them, but the read-back does not rely on that description.
Under this hypothesis, the theorem asserts the conjunction of two statements.
(a) Primal part. There exists a vector such that:
- every coordinate satisfies ;
- holds;
- for every real vector with ,
So some – feasible vector attains the maximum of over all real feasible vectors. In particular, that maximum exists.
(b) Dual part. There exist , and such that:
- every entry of , and lies in ;
- holds;
- for every real triple of the same shapes with ,
So some – dual-feasible triple attains the minimum of over all real dual-feasible triples.
The two parts are independent existence claims. The statement does not assert that the optimal primal value equals the optimal dual value, and it does not relate to in any way.
Degenerate cases. Both parts are existence claims, so the theorem asserts that each feasible set is nonempty and contains a – point. It also asserts that is bounded above and is bounded below on those sets. It is never true merely because a feasible set is empty; the only route to vacuity is the hypothesis.
- Empty : , and are the unique empty functions, and the – conditions on them hold trivially. Whether the theorem holds then depends only on the imported definitions: whether accepts the empty graph, whether the empty vector is feasible, and what the value functions return.
- No edges: ranges over the single empty function.
- empty: ranges over the single empty function.
- The hypothesis: whether holds for no graph or for only trivial ones, which would make the theorem vacuous or nearly so, cannot be determined from this code.
- Default values of total functions: none appear in the statement itself. Any divisions, natural-number subtractions or other default-valued operations would sit inside the undisplayed definitions.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.