Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

p. 3 — the Kalai–Kleitman bound n^(1+log₂ d) holds in the base abstraction

Proved
EHRR10.KalaiKleitman.diameter_le_kalai_kleitman

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatorial-abstractionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1polytope-diameterupper-bound

Let d≥1d\ge 1d≥1 and n≥0n\ge 0n≥0. Let G=(V,E)G=(V,E)G=(V,E) belong to the base abstraction Bd,n\mathcal B_{d,n}Bd,n​: VVV is a nonempty family of ddd-element subsets of [n][n][n], and for every u,v∈Vu,v\in Vu,v∈V there is a connecting path whose intermediate vertices contain u∩vu\cap vu∩v. Then, for every u,v∈Vu,v\in Vu,v∈V, there is a path ppp from uuu to vvv such that

∣p∣≤n1+log⁡2d,|p|\le n^{1+\log_2 d},∣p∣≤n1+log2​d,

where ∣p∣|p|∣p∣ is the number of edges of ppp. Thus the maximum diameter D(d,n)D(d,n)D(d,n) of a graph in Bd,n\mathcal B_{d,n}Bd,n​ 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 Δu(d,n)≤n1+log⁡d\Delta_u(d,n)\le n^{1+\log d}Δu​(d,n)≤n1+logd and says this bound continues to hold in the base abstraction. The theorem makes that statement explicit for every graph in Bd,n\mathcal B_{d,n}Bd,n​ 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 R\mathbb RR before comparison. The positive-dimension assumption excludes d=0d=0d=0, where the logarithm has no intended mathematical meaning. A walk witnesses the bound; erasing cycles gives a path of no greater length.

Preamble
import Mathlib
import Definitions.Def_EHRR10_LowerBound_BaseAbstraction
Formal statement
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
Source
Eisenbrand, Hähnle, Razborov, Rothvoß, Diameter of Polyhedra: Limits of Abstraction, Dagstuhl Seminar Proceedings 10211 (2010), http://drops.dagstuhl.de/opus/volltexte/2010/2724, p. 3, sentence beginning "At the same time the bound of Kalai and Kleitman [13]"
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me