Observation 4.8, p. 11 — rk_B is the optimum of the set covering problem on the α_j-edges of sk(B)
ProvedBinaryExtForm.HypercubeRank.observation_4_8Let be a natural binarization of in the range , let and let for . Then is the optimum value of the set covering problem whose constraint rows are the indicator vectors of the -edges () of the skeleton :
The rank of a natural binarization therefore depends only on the edge structure of and on which edges cross the levels .
Formalization Note. Only the second sentence of Observation 4.8 is formalized. Its first sentence, identifying with the rank of a property of a binary extended formulation satisfying the hypotheses of Theorem 4.6, is not stated, since this mission does not formalize binary extended formulations or Theorem 4.6, and Theorem 4.23 does not use it. The indicator entry is encoded as "not ( or )". The rank is stated for the chosen points (Definition 4.7). The hypothesis is the paper's.
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
namespace BinaryExtForm.HypercubeRank
theorem observation_4_8 {d k ℓ : ℕ} (B : Set (Fin (d + 1) → ℝ)) (hB : IsBinarization d k B)
(hN : IsNatural B) (hBk : ∀ p ∈ B, 0 ≤ p 0 ∧ p 0 ≤ k) (α : Fin ℓ → ℕ) (hα : ∀ j, α j < k)
(xbar : Fin ℓ → ℝ) (hx : ∀ j, (α j : ℝ) < xbar j ∧ xbar j < α j + 1) :
rk B xbar = sInf {c : ℕ | ∃ Z : Finset (Fin d), Z.card = c ∧
∀ u v, (∃ j, IsAlphaEdge B (α j) u v) → ∃ i ∈ Z, indicator u v i} := by sorry
end BinaryExtForm.HypercubeRank
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.