Lemma 3 — bounded-degree ⟨k, ε⟩ bipartite expanders exist
ProvedAKSSorting.Core.expander_existsFor all real and there is a positive integer such that for all disjoint finite sets , with
there is a expander on .
The degree bound depends only on and , not on the sizes of and . 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 is quantified before the vertex type and the sets. The ratio condition is written as and ; for nonempty sets this is the paper's condition, and it additionally admits , 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).
import Mathlib import Definitions.Def_AKSSorting_Core_IsExpander
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.