Corollary 4.15, p. 12 — sk(π_y(B)) is a subgraph of sk(B) for integral B; isomorphic for affine B
ProvedBinaryExtForm.HypercubeRank.corollary_4_15binarizationp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polytopesskeleton
Let be a binarization and let be its projection onto the -space.
- If is integral, then is a subgraph of on the same vertex set: maps the vertices of bijectively onto the vertices of , and whenever are adjacent in , the vertices are adjacent in .
- If is affine, then and are isomorphic: is a bijection between the vertex sets and are adjacent in if and only if are adjacent in .
This is what lets the paper compare the skeleton of a hypercube binarization with the hypercube graph .
Formalization Note. "On the same vertex set" and "isomorphic" are made concrete through the map itself (Set.BijOn yproj on the vertex sets, plus the adjacency implication or equivalence). Adjacency is Hirsch.Adj.
Preamble
import Mathlib import Definitions.Def_BinaryExtForm_HypercubeRank_Model
Formal statement
namespace BinaryExtForm.HypercubeRank
theorem corollary_4_15 {d k : ℕ} (B : Set (Fin (d + 1) → ℝ)) (hB : IsBinarization d k B) :
(IsIntegral B →
Set.BijOn yproj (Set.extremePoints ℝ B) (Set.extremePoints ℝ (yproj '' B)) ∧
∀ u ∈ Set.extremePoints ℝ B, ∀ v ∈ Set.extremePoints ℝ B,
Hirsch.Adj (yproj '' B) (yproj u) (yproj v) → Hirsch.Adj B u v) ∧
(IsAffineBin B →
Set.BijOn yproj (Set.extremePoints ℝ B) (Set.extremePoints ℝ (yproj '' B)) ∧
∀ u ∈ Set.extremePoints ℝ B, ∀ v ∈ Set.extremePoints ℝ B,
(Hirsch.Adj (yproj '' B) (yproj u) (yproj v) ↔ Hirsch.Adj B u v)) := by sorry
end BinaryExtForm.HypercubeRank
Source
Aprile, Conforti, Di Summa, Binary extended formulations and sequential convexification, arXiv:2106.00354v1, p. 12, Corollary 4.15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.