Corollary 4.19, p. 13 — rk_B(α_1,…,α_ℓ) = d − f_B(α_1,…,α_ℓ)
ProvedBinaryExtForm.HypercubeRank.corollary_4_19binarizationhypercubelift-and-projectp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a -hypercube binarization with hypercube graph , let and choose . Then
where counts the coordinate directions in which no edge of crosses any of the levels .
This is the form of Lemma 4.18 used in the proof of Theorem 4.23: comparing ranks of hypercube binarizations reduces to comparing the numbers .
Formalization Note. The subtraction is in and is exact, since by construction (it counts a subset of components). The rank is stated for the chosen points ; encodes the range.
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem corollary_4_19 {d ℓ : ℕ} (B : Set (Fin (d + 1) → ℝ)) (hB : IsHypercubeBinarization d B)
(α : Fin ℓ → ℕ) (hα : ∀ j, α j + 2 ≤ 2 ^ d)
(xbar : Fin ℓ → ℝ) (hx : ∀ j, (α j : ℝ) < xbar j ∧ xbar j < α j + 1) :
rk B xbar = d - fB B α := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 13, Corollary 4.19 (f_B defined just before it on p. 13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.