Distances from a base vertex along a facet form an interval
ProvedHirsch.tight_row_intervalLet be a bounded H-polytope, fix a base vertex , and write for the graph distance from (definition Hirsch_walk). Let be a row index and let be vertices of at which the -th inequality is tight. Then for every integer with
there is a vertex of with and .
So the set of distances from realised on the face cut out by a given inequality is an interval of integers. This is the "connected layer family" property of polytope graphs isolated by Eisenbrand, Hähnle, Razborov and Rothvoß, in the form in which Larman's induction uses it: a facet active in two distance layers is active in every layer in between. It follows from connectivity of the graph of each face (Hirsch.face_connected: and are joined by a walk along which the -th inequality stays tight) and the fact that the distance to changes by at most one along each step of a walk.
Formalization Note The vertices are the extreme points of ; boundedness guarantees that all graph distances are attained by walks (Hirsch.gdist_reach).
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_Hirsch_walk open scoped RealInnerProductSpace
namespace Hirsch
theorem tight_row_interval (d n : ℕ)
(a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
(hbd : Bornology.IsBounded (Hpoly a b))
(u : EuclideanSpace ℝ (Fin d)) (hu : u ∈ Set.extremePoints ℝ (Hpoly a b))
(s : Fin n) (p q : EuclideanSpace ℝ (Fin d))
(hp : p ∈ Set.extremePoints ℝ (Hpoly a b)) (hq : q ∈ Set.extremePoints ℝ (Hpoly a b))
(hps : ⟪a s, p⟫ = b s) (hqs : ⟪a s, q⟫ = b s)
(t : ℕ) (hpt : gdist (Hpoly a b) u p ≤ t) (htq : t ≤ gdist (Hpoly a b) u q) :
∃ w ∈ Set.extremePoints ℝ (Hpoly a b), ⟪a s, w⟫ = b s ∧ gdist (Hpoly a b) u w = t := by sorry
end Hirsch