Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Distances from a base vertex along a facet form an interval

Proved
Hirsch.tight_row_interval

by WillR · Sep 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-diameterhirsch-conjecturepolytopes

Let P={x∈Rd:⟨ai,x⟩≤bi, i<n}P=\{x\in\mathbb{R}^d:\langle a_i,x\rangle\le b_i,\ i<n\}P={x∈Rd:⟨ai​,x⟩≤bi​, i<n} be a bounded H-polytope, fix a base vertex uuu, and write gdistP(u,⋅)\mathrm{gdist}_P(u,\cdot)gdistP​(u,⋅) for the graph distance from uuu (definition Hirsch_walk). Let sss be a row index and let p,qp,qp,q be vertices of PPP at which the sss-th inequality is tight. Then for every integer ttt with

gdistP(u,p) ≤ t ≤ gdistP(u,q)\mathrm{gdist}_P(u,p)\ \le\ t\ \le\ \mathrm{gdist}_P(u,q)gdistP​(u,p) ≤ t ≤ gdistP​(u,q)

there is a vertex www of PPP with ⟨as,w⟩=bs\langle a_s,w\rangle=b_s⟨as​,w⟩=bs​ and gdistP(u,w)=t\mathrm{gdist}_P(u,w)=tgdistP​(u,w)=t.

So the set of distances from uuu 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: ppp and qqq are joined by a walk along which the sss-th inequality stays tight) and the fact that the distance to uuu changes by at most one along each step of a walk.

Formalization Note The vertices are the extreme points of PPP; boundedness guarantees that all graph distances are attained by walks (Hirsch.gdist_reach).

Preamble
import Mathlib
import Definitions.Def_Hirsch_model
import Definitions.Def_Hirsch_walk

open scoped RealInnerProductSpace
Formal statement
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
Source
F. Eisenbrand, N. Hähnle, A. Razborov, T. Rothvoß, Diameter of polyhedra: limits of abstraction, Math. Oper. Res. 35 (2010) 786-794, Section 2 (connected layer families, property that a facet meets consecutive layers); E. D. Kim, F. Santos, arXiv:0912.4235, proof of Theorem 2.5 ('each facet is active only in V_i's with consecutive values of i'). Platform ingredient: Hirsch.face_connected (ca7052f3-8364-4864-857f-55df4f138c51).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me