Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Sub-balanced H-polyhedra inherit diameter from equality sections

Proved
Hirsch.diamLE_le_section_diamLE_of_n_lt_two_d

by jjosh · Sep 11, 2026 · Mathlib c5ea003 (Lean v4.30.0)

graph-diameterhirschpolytope

Let P⊆RdP\subseteq\mathbb R^dP⊆Rd be an H-polyhedron defined by nnn inequalities, with n<2dn<2dn<2d. Then any two vertices share a tight inequality: an extreme point is tight on at least ddd rows (otherwise a line through it stays feasible), so two tight-row sets of size at least ddd in a universe of size n<2dn<2dn<2d cannot be disjoint. This is the complement of the spindle constraint n≥2dn\ge 2dn≥2d for complementary tight sets.

Consequently, if every equality section P∩{⟨ai,x⟩=bi}P\cap\{\langle a_i,x\rangle=b_i\}P∩{⟨ai​,x⟩=bi​} has padded diameter at most BBB, then so does PPP:

DiamLE⁡(P,B).\operatorname{DiamLE}(P,B).DiamLE(P,B).

The walk between two vertices may be taken inside their shared equality section, whose edges remain edges of PPP. This reduces the sub-balanced regime n<2dn<2dn<2d to diameter bounds on facets. It does not treat the critical balanced case n=2dn=2dn=2d, and it does not prove a uniform polynomial in (n+d)(n+d)(n+d).

Formalization Note Boundedness and simplicity are not assumed. Tight-row cardinality at least ddd holds for every extreme point of a finite H-presentation in Rd\mathbb R^dRd.

Preamble
import Definitions.Def_Hirsch_model
set_option autoImplicit false
open scoped RealInnerProductSpace
open Set Hirsch
Formal statement
namespace Hirsch

theorem diamLE_le_section_diamLE_of_n_lt_two_d
    {d n B : ℕ} (hn : n < 2 * d)
    (a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
    (hF : ∀ i : Fin n,
      DiamLE (Hpoly a b ∩ {x | ⟪a i, x⟫ = b i}) B) :
    DiamLE (Hpoly a b) B := by sorry

end Hirsch
Source
Complement of the spindle row-count n≥2dn\ge 2dn≥2d (Prove2Me Hirsch.spindle_n_ge_two_d). Classical observation that ddd-subsets of a set of size <2d<2d<2d intersect; used in Klee--Walkup reductions below the ddd-step equator n=2dn=2dn=2d.

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, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me