Observation 2.2, p. 4 — the lift-and-project rank is the optimum of a set covering problem
ProvedBinaryExtForm.HypercubeRank.observation_2_2Let be a polytope whose coordinates in lie in . Let be the set of vertices of having at least one fractional coordinate (a value outside ) among the coordinates in , and let be the matrix whose rows are the incidence vectors of the fractional supports of the vertices . Then
Equivalently, is the minimum size of a set that contains, for every vertex of with a fractional coordinate in , at least one of its fractional coordinates.
This turns the convexification count into a purely combinatorial hitting-set problem on the vertex set of ; the rank of a binarization is analysed through it.
Formalization Note. is a subset and ; duplicate rows of do not change the problem, so it is stated vertex by vertex. is always feasible, so the sInf on the right is a true minimum. As in lpr, is any set of coordinates instead of the first .
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
namespace BinaryExtForm.HypercubeRank
theorem observation_2_2 {n : ℕ} (Q : Set (Fin n → ℝ)) (H : Finset (Fin n)) (hQ : IsPolytope Q)
(hQH : ∀ p ∈ Q, ∀ i ∈ H, 0 ≤ p i ∧ p i ≤ 1) :
lpr Q H = sInf {c : ℕ | ∃ Z : Finset (Fin n), Z ⊆ H ∧ Z.card = c ∧
∀ v ∈ Set.extremePoints ℝ Q, (∃ i ∈ H, v i ≠ 0 ∧ v i ≠ 1) →
∃ i ∈ Z, v i ≠ 0 ∧ v i ≠ 1} := by sorry
end BinaryExtForm.HypercubeRank
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.