The graph distance between two vertices of a bounded H-polytope is attained by a walk
ProvedHirsch.gdist_reachLet be a bounded H-polytope and let be vertices (extreme points) of . Write for the combinatorial distance in the vertex-edge graph of : the least such that there is a walk of exactly steps from to , each step stationary or along an edge (Reach, from the definition Hirsch_walk). Then this least length is attained:
The content is that the set of walk lengths is nonempty, i.e. that the graph of a bounded polytope is connected (Balinski; on the platform, Hirsch.face_connected or Hirsch.graph_connected_general), after which the infimum of a nonempty set of naturals is a member. This is the basic bridge between the distance function and explicit walks, used by every layer-by-distance argument.
Formalization Note gdist is defined as sInf of the set of walk lengths and takes the junk value when no walk exists; boundedness is what rules that case out here.
import Mathlib import Definitions.Def_Hirsch_model import Definitions.Def_Hirsch_walk open scoped RealInnerProductSpace
namespace Hirsch
theorem gdist_reach (d n : ℕ)
(a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
(hbd : Bornology.IsBounded (Hpoly a b))
(u v : EuclideanSpace ℝ (Fin d))
(hu : u ∈ Set.extremePoints ℝ (Hpoly a b)) (hv : v ∈ Set.extremePoints ℝ (Hpoly a b)) :
Reach (Hpoly a b) (gdist (Hpoly a b) u v) u v := by sorry
end Hirsch