p. 3 — the Kalai–Kleitman bound n^(1+log₂ d) holds in the base abstraction
ProvedEHRR10.KalaiKleitman.diameter_le_kalai_kleitmanLet and . Let belong to the base abstraction : is a nonempty family of -element subsets of , and for every there is a connecting path whose intermediate vertices contain . Then, for every , there is a path from to such that
where is the number of edges of . Thus the maximum diameter of a graph in obeys the same upper bound as the polyhedron diameter stated on page 3 of the paper.
The result shows that condition i), shared by polyhedron graphs and a larger combinatorial graph class, still controls diameter by a quasi-polynomial expression in the dimension and number of facets.
Formalization Note The page writes and says this bound continues to hold in the base abstraction. The theorem makes that statement explicit for every graph in and every pair of its vertices. The unlabelled logarithm is read as base 2, matching the cited Kalai–Kleitman convention; this base is not printed and remains a source interpretation. The power is a real power, and the path length is cast to before comparison. The positive-dimension assumption excludes , where the logarithm has no intended mathematical meaning. A walk witnesses the bound; erasing cycles gives a path of no greater length.
import Mathlib import Definitions.Def_EHRR10_LowerBound_BaseAbstraction
namespace EHRR10.KalaiKleitman
theorem diameter_le_kalai_kleitman
(d n : ℕ) (hd : 1 ≤ d)
(V : Finset (Finset (Fin n))) (G : SimpleGraph V)
(hG : EHRR10.LowerBound.InB d n V G) (u v : V) :
∃ p : G.Walk u v, (p.length : ℝ) ≤ (n : ℝ) ^ (1 + Real.logb 2 d) := by sorry
end EHRR10.KalaiKleitman
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.