Zero-one hulls have zero-one vertices and no rays
ProvedKarpPapadimitriou.SmallFacial.zero_one_verticesconvex-hulldiscrete-geometryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1zero-one-optimization
Let be a zero-one problem and let . Every vertex of is a zero-one vector, and this hull has no nonzero ray:
This supplies the bounded geometric case in the proof of Lemma 1, including an empty feasible set.
Formalization Note A ray means a nonzero rational direction and a base point in the hull with in the hull for every rational . A vertex is an extreme point. The hull is over , as in the paper's notation.
Preamble
import Mathlib import Definitions.Def_KarpPapadimitriou_SmallFacial_COP
Formal statement
namespace KarpPapadimitriou.SmallFacial
/-- p. 6, proof of Lemma 1: zero-one hulls have zero-one vertices and no rays. -/
theorem zero_one_vertices (C : COP) (hC : IsZeroOne C) (z : List Bool) (hz : z ∈ C.L) :
(∀ v, IsVertex (hull C z) v → ∀ i, v i = 0 ∨ v i = 1) ∧
¬ HasRay (hull C z) := by sorry
end KarpPapadimitriou.SmallFacial
Source
Karp & Papadimitriou, MIT/LCS/TM-154 (Feb. 1980), p. 6, proof of Lemma 1, zero-one case; https://dspace.mit.edu/server/api/core/bitstreams/eb122126-c312-4445-a8d2-153e3e7d285f/content
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.