Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Larman's bound 2^(d−1)·n in the base abstraction

Proved
EHRR10.Larman.diameter_le_larman

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 nnn be natural numbers, and let GGG be any graph in the base abstraction Bd,n\mathcal B_{d,n}Bd,n​. Thus its vertices are distinct ddd-subsets of an nnn-element label set, and every pair is joined through vertices containing their common labels. Every pair of vertices u,vu,vu,v can be joined by a path of at most 2d−1n2^{d-1}n2d−1n edges. Equivalently, the diameter of every graph in Bd,n\mathcal B_{d,n}Bd,n​ obeys

diam⁡(G)≤2d−1n.\operatorname{diam}(G)\le 2^{d-1}n.diam(G)≤2d−1n.

This is the Larman upper bound that Eisenbrand, Hähnle, Razborov and Rothvoß announce for their combinatorial abstraction. For a fixed positive dimension, it is linear in the number of labels.

Formalization Note The paper writes the displayed bound using Δu(d,n)\Delta_u(d,n)Δu​(d,n), then says that it continues to hold in the base abstraction. The Lean statement spells this out for every G∈Bd,nG\in\mathcal B_{d,n}G∈Bd,n​ and every pair of its vertices. The explicit condition d≥1d\ge1d≥1 makes the exponent d−1d-1d−1 ordinary subtraction. An existential walk of bounded length expresses the distance bound without choosing a default value for the diameter of an empty or disconnected graph.

Preamble
import Mathlib
import Definitions.Def_EHRR10_LowerBound_BaseAbstraction
Formal statement
namespace EHRR10.Larman

/-- Larman's bound in the base abstraction (Dagstuhl 10211, 2010, p. 3): for `d ≥ 1`, any two
vertices of a graph in `𝓑_{d,n}` are joined by a walk with at most `2^(d-1) * n` edges,
i.e. `D(d, n) ≤ 2^(d-1) · n`. -/
theorem diameter_le_larman (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 ≤ 2 ^ (d - 1) * n := by sorry

end EHRR10.Larman
Source
Eisenbrand, Hähnle, Razborov, Rothvoß, Diameter of Polyhedra: Limits of Abstraction, Dagstuhl Seminar Proceedings 10211 (2010), p. 3, sentence beginning 'At the same time the bound of Kalai and Kleitman'; http://drops.dagstuhl.de/opus/volltexte/2010/2724
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