Observation 2.3, p. 4 — binary points of a binarization are unique per y and are vertices
ProvedBinaryExtForm.HypercubeRank.observation_2_3binarizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polytopes
Let be a binarization of the variable in the range . Then for every :
- there is at most one with ;
- if such an exists, then and is a vertex of .
So every vector encodes at most one value of , that value lies in the range, and the corresponding binary point is a vertex of .
Formalization Note. Points are p : Fin (d+1) → ℝ with = p 0. Part 1 says: if , has binary -part and has the same -part, then and have the same .
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem observation_2_3 {d k : ℕ} (B : Set (Fin (d + 1) → ℝ)) (hB : IsBinarization d k B) :
(∀ p ∈ B, ∀ q ∈ B, IsBinaryY p → yproj q = yproj p → q 0 = p 0) ∧
(∀ p ∈ B, IsBinaryY p → (∃ m : ℕ, m ≤ k ∧ p 0 = m) ∧ p ∈ Set.extremePoints ℝ B) := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 4, Observation 2.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.