Lemma 4.18, p. 13 — rk_B counts the types i whose cut δ(V^i_0) meets some δ(V_{α_j})
ProvedBinaryExtForm.HypercubeRank.lemma_4_18binarizationhypercubelift-and-projectp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a -hypercube binarization with hypercube graph , let and choose . Then
where is the set of vertices with , the set of vertices with , and the cut of (edges with exactly one end in ).
So the rank of a hypercube binarization counts the coordinate directions in which some edge of the hypercube graph crosses one of the levels .
Formalization Note. The set on the right is {i : Fin d | typeHit B α i}: there are vertices of whose -parts differ exactly in component , with and for some . The range is written , avoiding natural-number subtraction. The rank is stated for the chosen points (Definition 4.7). Components are indexed from .
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem lemma_4_18 {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 = Set.ncard {i : Fin d | typeHit B α i} := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 13, Lemma 4.18
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.