Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Larman's layer recursion: summing the layer steps along a facet decomposition

Proved
Hirsch.larman_layer_recursion

by elmismisimoxhunca · Sep 5, 2026 · Mathlib c5ea003 (Lean v4.30.0)

graph-diameterhirsch-conjecturepolytopes

Let P={x∈Rd:⟨ai,x⟩≤bi, i<n}P=\{x\in\mathbb{R}^d:\langle a_i,x\rangle\le b_i,\ i<n\}P={x∈Rd:⟨ai​,x⟩≤bi​, i<n} be a bounded H-polytope with all normals nonzero, in which every vertex has at least one tight inequality. Let β:N→N\beta:\mathbb{N}\to\mathbb{N}β:N→N and Bd∈NB_d\in\mathbb{N}Bd​∈N. Assume:

  1. (layer step) for every base vertex uuu, row rrr, set of rows T∋rT\ni rT∋r, and vertices y,zy,zy,z on the facet FrF_rFr​ with tight rows in TTT such that every vertex of FrF_rFr​ carrying a row outside TTT is strictly closer to uuu than yyy, one has gdist(u,z)≤gdist(u,y)+β(∣T∣)\mathrm{gdist}(u,z)\le\mathrm{gdist}(u,y)+\beta(|T|)gdist(u,z)≤gdist(u,y)+β(∣T∣) (this is Hirsch.larman_layer_step);
  2. (arithmetic) for every kkk and every family m1,…,mk≥1m_1,\dots,m_k\ge1m1​,…,mk​≥1 with ∑imi≤2n\sum_i m_i\le 2n∑i​mi​≤2n,
∑i=1kβ(mi)+k ≤ Bd+1.\sum_{i=1}^{k}\beta(m_i)+k\ \le\ B_d+1 .i=1∑k​β(mi​)+k ≤ Bd​+1.

Then DiamLE⁡(P,Bd)\operatorname{DiamLE}(P,B_d)DiamLE(P,Bd​): the combinatorial diameter of PPP is at most BdB_dBd​.

This is Larman's argument as presented by Kim--Santos. From a base vertex uuu, stratify the vertices by distance into layers V1,…,VkV_1,\dots,V_kV1​,…,Vk​ with Vi={v:δi−1<gdist(u,v)≤δi}V_i=\{v:\delta_{i-1}<\mathrm{gdist}(u,v)\le\delta_i\}Vi​={v:δi−1​<gdist(u,v)≤δi​}, δ0=−1\delta_0=-1δ0​=−1, where δi\delta_iδi​ is the largest distance of a vertex sharing a facet FiF_iFi​ with some vertex at distance δi−1+1\delta_{i-1}+1δi−1​+1. Let TiT_iTi​ be the rows tight at some vertex of ViV_iVi​ and mi=∣Ti∣m_i=|T_i|mi​=∣Ti​∣. Because a facet active in two layers is active in all layers between (Hirsch.tight_row_interval) and the choice of Fi+1F_{i+1}Fi+1​ is maximal, no row is active in three layers, so ∑imi≤2n\sum_i m_i\le2n∑i​mi​≤2n. The layer step applied to FiF_iFi​, TiT_iTi​, a vertex yi∈Fiy_i\in F_iyi​∈Fi​ at distance δi−1+1\delta_{i-1}+1δi−1​+1 and a vertex zi∈Fiz_i\in F_izi​∈Fi​ at distance δi\delta_iδi​ gives δi−δi−1−1≤β(mi)\delta_i-\delta_{i-1}-1\le\beta(m_i)δi​−δi−1​−1≤β(mi​), and summing over iii yields ecc(u)=δk≤∑iβ(mi)+k−1≤Bd\mathrm{ecc}(u)=\delta_k\le\sum_i\beta(m_i)+k-1\le B_decc(u)=δk​≤∑i​β(mi​)+k−1≤Bd​.

Formalization Note The hypothesis that every vertex has a tight row holds automatically when d≥1d\ge1d≥1 (the tight normals span, Hirsch.vertex_tight_rows_span), and is stated explicitly to keep the recursion dimension-free. The layer-step hypothesis is quantified over all base vertices uuu and all finsets TTT of rows.

Preamble
import Mathlib
import Definitions.Def_Hirsch_model
import Definitions.Def_Hirsch_walk

open scoped RealInnerProductSpace
Formal statement
namespace Hirsch

theorem larman_layer_recursion (d n : ℕ)
    (a : Fin n → EuclideanSpace ℝ (Fin d)) (b : Fin n → ℝ)
    (hane : ∀ j, a j ≠ 0) (hbd : Bornology.IsBounded (Hpoly a b))
    (htight : ∀ v ∈ Set.extremePoints ℝ (Hpoly a b), ∃ j, ⟪a j, v⟫ = b j)
    (β : ℕ → ℕ) (Bd : ℕ)
    (hstep : ∀ u ∈ Set.extremePoints ℝ (Hpoly a b), ∀ (r : Fin n) (T : Finset (Fin n)), r ∈ T →
      ∀ y ∈ Set.extremePoints ℝ (Hpoly a b), ∀ z ∈ Set.extremePoints ℝ (Hpoly a b),
      ⟪a r, y⟫ = b r → ⟪a r, z⟫ = b r →
      (∀ j, ⟪a j, y⟫ = b j → j ∈ T) → (∀ j, ⟪a j, z⟫ = b j → j ∈ T) →
      (∀ w ∈ Set.extremePoints ℝ (Hpoly a b), ⟪a r, w⟫ = b r →
        (∃ j, j ∉ T ∧ ⟪a j, w⟫ = b j) → gdist (Hpoly a b) u w + 1 ≤ gdist (Hpoly a b) u y) →
      gdist (Hpoly a b) u z ≤ gdist (Hpoly a b) u y + β T.card)
    (harith : ∀ (k : ℕ) (m : Fin k → ℕ), (∀ i, 1 ≤ m i) →
      ∑ i, m i ≤ 2 * n → ∑ i, β (m i) + k ≤ Bd + 1) :
    DiamLE (Hpoly a b) Bd := by sorry

end Hirsch
Source
D. G. Larman, Paths on polytopes, Proc. London Math. Soc. s3-20 (1970) 161-178, https://doi.org/10.1112/plms/s3-20.2.249; exposition followed: E. D. Kim, F. Santos, Companion to 'An update on the Hirsch conjecture', arXiv:0912.4235, Section 2.2, proof of Theorem 2.5 (layer decomposition, 'no facet is active in more than two V_i's', sum n_i <= 2n); F. Santos, TOP 21 (2013), arXiv:1307.5900, Lemma 3.13 and Theorem 3.14.

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.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me