Theorem 2 — α-expanders have Ω(α³/log(1/α))n cycle lengths
ProvedCycleLengthsExp.ManyLengths.theorem_2There is an absolute constant such that, for every , all sufficiently large , and every -expander on vertices,
Here is the set of lengths of simple cycles of , so the inequality counts distinct lengths rather than cycles.
The theorem gives a polynomial dependence on the expansion parameter for the number of available cycle lengths. Theorem 1 of the paper gives a weaker dependence through its spacing guarantee.
Formalization Note The paper writes . One positive constant is fixed before , and is the disclosed endpoint-safe reading of its logarithm. The source does not state an threshold, but is an -expander with no cycle, so the necessary is allowed to depend on and precedes the choice of .
import Mathlib import Definitions.Def_CycleLengthsExp_ManyLengths_Setting
namespace CycleLengthsExp.ManyLengths
/-- Friedman–Krivelevich, Theorem 2, p. 3 (restated p. 13). -/
theorem theorem_2 :
∃ c : ℝ, 0 < c ∧ ∀ α : ℝ, 0 < α → α ≤ 1 →
∃ n₀ : ℕ, ∀ n ≥ n₀, ∀ G : SimpleGraph (Fin n), CycleLengthsExp.WellSpread.IsAlphaExpander α G →
c * (α ^ 3 / Real.logb 2 (2 / α)) * (n : ℝ) ≤
((CycleLengthsExp.WellSpread.cycleLengths G).ncard : ℝ) := by sorry
end CycleLengthsExp.ManyLengths
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.