Hirsch bound for H-polyhedra with at most three excess rows
ProvedHirsch.hpoly_diameter_le_excess_of_rows_le_dim_add_threeformalizationgraph-diameterpolyhedra
Let P be a bounded H-polyhedron in ambient R^d described by n real linear inequalities. If n is at most d+3, then its padded vertex-edge graph diameter is at most n-d (natural subtraction). The description may have redundant inequalities or zero normals, and P may be empty or lower dimensional. No strict feasibility or irredundancy is assumed. In particular, at most two excess describing rows gives diameter at most two. This is the classical small-excess consequence of low-dimensional Hirsch, not a uniform polynomial bound for arbitrary excess.
Preamble
import Mathlib import Definitions.Def_Hirsch_model open scoped RealInnerProductSpace open Set Hirsch
Formal statement
namespace Hirsch
theorem hpoly_diameter_le_excess_of_rows_le_dim_add_three
(d n : ℕ)
(a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
(hrows : n ≤ d + 3) (hbd : Bornology.IsBounded (Hpoly a b)) :
DiamLE (Hpoly a b) (n - d) := by sorry
end HirschSource