Lemma 4.3, p. 9 — the vertices of a fractional slice B(f) lie on the α-edges of B
ProvedBinaryExtForm.HypercubeRank.lemma_4_3binarizationfacesp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polytopes
Let be a natural binarization of in the range , let and let . Write . Then the vertex set consists of exactly one point in the relative interior of each -dimensional face of whose endpoints and satisfy and :
and each such edge contains exactly one point with in its relative interior.
The lemma describes the fractional vertices whose removal the rank of a binarization measures.
Formalization Note. An edge is Hirsch.Adj B u v (the segment is an extreme subset of , ), and its relative interior is openSegment ℝ u v. The statement is the set equality together with the uniqueness of the point at height on each such edge.
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem lemma_4_3 {d k : ℕ} (B : Set (Fin (d + 1) → ℝ)) (hB : IsBinarization d k B)
(hN : IsNatural B) (α : ℕ) (hα : α < k) (f : ℝ) (hf₁ : (α : ℝ) < f) (hf₂ : f < α + 1) :
Set.extremePoints ℝ (slice B f) =
{p | ∃ u v, Hirsch.Adj B u v ∧ u 0 ≤ α ∧ (α : ℝ) + 1 ≤ v 0 ∧
p ∈ openSegment ℝ u v ∧ p 0 = f} ∧
∀ u v, Hirsch.Adj B u v → u 0 ≤ α → (α : ℝ) + 1 ≤ v 0 →
∃! p, p ∈ openSegment ℝ u v ∧ p 0 = f := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 9, Lemma 4.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.