Larman's bound 2^(d−1)·n in the base abstraction
ProvedEHRR10.Larman.diameter_le_larmanLet and be natural numbers, and let be any graph in the base abstraction . Thus its vertices are distinct -subsets of an -element label set, and every pair is joined through vertices containing their common labels. Every pair of vertices can be joined by a path of at most edges. Equivalently, the diameter of every graph in obeys
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 , then says that it continues to hold in the base abstraction. The Lean statement spells this out for every and every pair of its vertices. The explicit condition makes the exponent 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.
import Mathlib import Definitions.Def_EHRR10_LowerBound_BaseAbstraction
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.