Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3.4 — a ddd-regular bipartite graph is a strong expander iff λ(G)\lambda(G)λ(G) is bounded away from 000

Proved
AlonExpanders.Core.theorem_3_4

by mikedeng1 · 1 vote · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

cheeger-inequalityexpander-graphsp2o-batch-pfp1bp2o-gran-per-chapterp2o-plan-paperp2o-v1spectral-graph-theory

Let G=(I,O;E)G = (I, O; E)G=(I,O;E) be a ddd-regular bipartite graph with ∣I∣=∣O∣=n|I| = |O| = n∣I∣=∣O∣=n, and let λ=λ(G)\lambda = \lambda(G)λ=λ(G) be the second-smallest eigenvalue of its Laplacian QG=dI−AGQ_G = dI - A_GQG​=dI−AG​, counted with multiplicity.

  1. If n≥1n \ge 1n≥1, c≥0c \ge 0c≥0 and GGG is a strong (n,d,c)(n, d, c)(n,d,c)-expander, then
λ  ≥  c21024+2c2,\lambda \;\ge\; \frac{c^2}{1024 + 2c^2},λ≥1024+2c2c2​,

i.e. GGG is a (2n,d,c2/(1024+2c2))(2n, d, c^2/(1024+2c^2))(2n,d,c2/(1024+2c2))-enlarger. 2. If ε>0\varepsilon > 0ε>0 and λ≥ε\lambda \ge \varepsilonλ≥ε, i.e. GGG is a (2n,d,ε)(2n, d, \varepsilon)(2n,d,ε)-enlarger, then GGG is a strong (n,d,c)(n, d, c)(n,d,c)-expander with

c=2dε−ε2d2.c = \frac{2d\varepsilon - \varepsilon^2}{d^2}.c=d22dε−ε2​.

Here a strong (n,d,c)(n, d, c)(n,d,c)-expander is a bipartite graph with ∣I∣=∣O∣=n|I| = |O| = n∣I∣=∣O∣=n and degrees at most ddd in which every X⊆IX \subseteq IX⊆I satisfies ∣N(X)∣≥(1+c(1−∣X∣/n))∣X∣|N(X)| \ge (1 + c(1 - |X|/n))|X|∣N(X)∣≥(1+c(1−∣X∣/n))∣X∣.

The theorem says that for regular bipartite graphs vertex expansion and the spectral gap of the Laplacian are equivalent, with explicit constants in both directions. Since λ(G)\lambda(G)λ(G) is computable in polynomial time, this gives an efficient certificate of expansion, whereas deciding expansion exactly is coNP-complete.

Formalization Note Three hypotheses absent from the page are added, each necessary. n≥1n \ge 1n≥1 in (1): for n=0n = 0n=0 the graph is empty, λ=0\lambda = 0λ=0 by convention, and the expander condition holds vacuously. c≥0c \ge 0c≥0 in (1): a perfect matching on 2+22 + 22+2 vertices is a strong (2,1,−1)(2, 1, -1)(2,1,−1)-expander with λ=0\lambda = 0λ=0. ε>0\varepsilon > 0ε>0 in (2): for d=0d = 0d=0 and n≥1n \ge 1n≥1, λ=0≥ε\lambda = 0 \ge \varepsilonλ=0≥ε for every ε≤0\varepsilon \le 0ε≤0, yet the edgeless graph is no strong expander. The closing sentence of the theorem ("Thus … one can prove efficiently … c′≥c2/(1032d)c' \ge c^2/(1032d)c′≥c2/(1032d)") is an algorithmic remark and is not formalized. λ(G)\lambda(G)λ(G) is the published AlonMilman.Diameter.lambda1, N(X)N(X)N(X) the published AKSSorting.Core.neighbours.

Preamble
import Mathlib
import Definitions.Def_AlonMilman_Diameter_lambda1
import Definitions.Def_AlonExpanders_Core_IsIOBipartite
import Definitions.Def_AlonExpanders_Core_IsStrongExpander
Formal statement
namespace AlonExpanders.Core

/-- Theorem 3.4 of Alon, *Eigenvalues and expanders*, Combinatorica 6 (1986), pp. 92–93. Let `G`
be a `d`-regular bipartite graph on `I ⊕ O` with `|I| = |O| = n` and `λ = λ(G)`.
(1) If `G` is a strong `(n, d, c)`-expander then `λ ≥ c²/(1024 + 2c²)`.
(2) If `λ ≥ ε` then `G` is a strong `(n, d, (2dε − ε²)/d²)`-expander.
Added hypotheses: `1 ≤ n` and `0 ≤ c` in (1), `0 < ε` in (2); each is necessary (empty graph at
`n = 0`; a perfect matching is a strong `(2, 1, −1)`-expander with `λ = 0`; the empty graph with
`d = 0` has `λ = 0 ≥ ε` for `ε ≤ 0` and is no strong expander). -/
theorem theorem_3_4 {I O : Type} [Fintype I] [Fintype O] [DecidableEq I] [DecidableEq O]
    (G : SimpleGraph (I ⊕ O)) [DecidableRel G.Adj] (n d : ℕ)
    (hI : Fintype.card I = n) (hO : Fintype.card O = n)
    (hbip : IsIOBipartite G) (hreg : G.IsRegularOfDegree d) :
    (∀ c : ℝ, 0 ≤ c → 1 ≤ n → IsStrongExpander G n d c →
        c ^ 2 / (1024 + 2 * c ^ 2) ≤ AlonMilman.Diameter.lambda1 G) ∧
    (∀ ε : ℝ, 0 < ε → ε ≤ AlonMilman.Diameter.lambda1 G →
        IsStrongExpander G n d ((2 * (d : ℝ) * ε - ε ^ 2) / (d : ℝ) ^ 2)) := by sorry

end AlonExpanders.Core
Source
Alon, Eigenvalues and expanders, Combinatorica 6 (1986), pp. 92–93, Theorem 3.4 (1) and (2)
Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 4, 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