Theorem 3.4 — a -regular bipartite graph is a strong expander iff is bounded away from
ProvedAlonExpanders.Core.theorem_3_4Let be a -regular bipartite graph with , and let be the second-smallest eigenvalue of its Laplacian , counted with multiplicity.
- If , and is a strong -expander, then
i.e. is a -enlarger. 2. If and , i.e. is a -enlarger, then is a strong -expander with
Here a strong -expander is a bipartite graph with and degrees at most in which every satisfies .
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 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. in (1): for the graph is empty, by convention, and the expander condition holds vacuously. in (1): a perfect matching on vertices is a strong -expander with . in (2): for and , for every , yet the edgeless graph is no strong expander. The closing sentence of the theorem ("Thus … one can prove efficiently … ") is an algorithmic remark and is not formalized. is the published AlonMilman.Diameter.lambda1, the published AKSSorting.Core.neighbours.
import Mathlib import Definitions.Def_AlonMilman_Diameter_lambda1 import Definitions.Def_AlonExpanders_Core_IsIOBipartite import Definitions.Def_AlonExpanders_Core_IsStrongExpander
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.