Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 3 — bounded-degree ⟨k, ε⟩ bipartite expanders exist

Proved
AKSSorting.Core.expander_exists

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

expander-graphsp2o-batch-p200ap2o-gran-per-chapterp2o-plan-paperp2o-v1sorting-networks

For all real 0<ε<10<\varepsilon<10<ε<1 and c≥1c\ge 1c≥1 there is a positive integer k=k(ε,c)k=k(\varepsilon,c)k=k(ε,c) such that for all disjoint finite sets AAA, BBB with

1c≤∣A∣∣B∣≤c\frac1c\le\frac{|A|}{|B|}\le cc1​≤∣B∣∣A∣​≤c

there is a ⟨k,ε⟩\langle k,\varepsilon\rangle⟨k,ε⟩ expander on ⟨A,B⟩\langle A,B\rangle⟨A,B⟩.

The degree bound kkk depends only on ε\varepsilonε and ccc, not on the sizes of AAA and BBB. This is what keeps every parallel step of the AKS network of constant depth. The paper derives it from the results of Margulis and of Gabber and Galil.

Formalization Note The constant kkk is quantified before the vertex type and the sets. The ratio condition is written as ∣A∣≤c∣B∣|A|\le c|B|∣A∣≤c∣B∣ and ∣B∣≤c∣A∣|B|\le c|A|∣B∣≤c∣A∣; for nonempty sets this is the paper's condition, and it additionally admits A=B=∅A=B=\emptysetA=B=∅, where the empty graph is an expander. The expander notion is the one of Definition 2.2 with the expansion inequalities imposed on nonempty sets (as printed they fail for the empty set).

Preamble
import Mathlib
import Definitions.Def_AKSSorting_Core_IsExpander
Formal statement
namespace AKSSorting.Core

/-- Lemma 3 (Ajtai–Komlós–Szemerédi 1983, p. 6): for all `0 < ε < 1` and `c ≥ 1` there is a
positive integer `k = k(ε, c)` such that for all disjoint finite sets `A, B` with
`1/c ≤ |A|/|B| ≤ c` there is a `⟨k, ε⟩` expander on `⟨A, B⟩`. The ratio condition is written
multiplicatively, `|A| ≤ c|B|` and `|B| ≤ c|A|`. -/
theorem expander_exists (ε c : ℝ) (hε₀ : 0 < ε) (hε₁ : ε < 1) (hc : 1 ≤ c) :
    ∃ k : ℕ, 0 < k ∧ ∀ (V : Type) (A B : Finset V), Disjoint A B →
      (A.card : ℝ) ≤ c * B.card → (B.card : ℝ) ≤ c * A.card →
      ∃ G : SimpleGraph V, IsExpander G A B k ε := by sorry

end AKSSorting.Core
Source
Ajtai, Komlós, Szemerédi, Sorting in c log n parallel steps, Combinatorica 3 (1983), p. 6, Lemma 3
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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