Pushing one row inward toward a vertex induces a graph contraction
ProvedHirsch.spindle_inward_row_push_graphLet be bounded with , let be vertices, row tight at and slack at , and a direction with such that on the face one has with equality only at (an 'inward push toward '). Replace by for . Then for some : the perturbed polytope is bounded, and remain vertices, and there is a map from vertices of the perturbed polytope to vertices of fixing and that sends every perturbed edge to an edge of or collapses it to a point.
This is the primal form of Santos' Lemma 2.2 (pushing a vertex does not decrease dual distances). The proof classifies vertices of the perturbed polytope by their tight bases: bases invertible at give branches converging to old vertices, and bases that become invertible only for are constant branches lying on the old -face with , hence equal to . Edges are handled by the rank of their common tight rows, with an explicit finite-minor bound on .
import Mathlib import Definitions.Def_Hirsch_model open scoped RealInnerProductSpace open WithLp EuclideanSpace
namespace Hirsch
theorem spindle_inward_row_push_graph
(m N : ℕ) (A : Fin N → EuclideanSpace ℝ (Fin m))
(B : Fin N → ℝ) (r : Fin N)
(p q h : EuclideanSpace ℝ (Fin m))
(hB : ∀ i, 0 < B i)
(hbd : Bornology.IsBounded (Hpoly A B))
(hp : p ∈ Set.extremePoints ℝ (Hpoly A B))
(hq : q ∈ Set.extremePoints ℝ (Hpoly A B))
(hrp : ⟪A r, p⟫ = B r) (hrq : ⟪A r, q⟫ < B r)
(hhp : ⟪h, p⟫ = 0)
(hin : ∀ x ∈ Hpoly A B, ⟪A r, x⟫ = B r →
⟪h, x⟫ ≤ 0 ∧ (⟪h, x⟫ = 0 → x = p)) :
∃ η : ℝ, 0 < η ∧ ∀ s : ℝ, 0 < s → s < η →
let As := fun i => if i = r then A i + s • h else A i
Bornology.IsBounded (Hpoly As B) ∧
p ∈ Set.extremePoints ℝ (Hpoly As B) ∧
q ∈ Set.extremePoints ℝ (Hpoly As B) ∧
∃ φ : EuclideanSpace ℝ (Fin m) → EuclideanSpace ℝ (Fin m),
φ p = p ∧ φ q = q ∧
(∀ x ∈ Set.extremePoints ℝ (Hpoly As B),
φ x ∈ Set.extremePoints ℝ (Hpoly A B)) ∧
(∀ x y, Adj (Hpoly As B) x y →
φ x = φ y ∨ Adj (Hpoly A B) (φ x) (φ y)) := by sorry
end Hirsch