Proof of Lemma 2.1, p. 4 — in a (k,α)-expander,
ProvedCycleLengthsExp.WellSpread.ball_growthexpander-graphsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vertex-expansion
Let and be reals and let be a finite -expander. Then for every vertex and every integer the ball of radius around satisfies
Balls grow geometrically until they reach size . This is the fact behind the diameter bound of Lemma 2.1, and behind the logarithmic depth of the breadth-first trees in Lemma 2.7 and Theorem 1.
Formalization Note. is the set of vertices reachable from by a walk with at most edges. The vertex type is any finite type.
Preamble
import Mathlib import Definitions.Def_CycleLengthsExp_WellSpread_Setting
Formal statement
namespace CycleLengthsExp.WellSpread
theorem ball_growth {V : Type*} [Fintype V] (G : SimpleGraph V) (k α : ℝ)
(hk : 0 < k) (hα : 0 < α) (hG : IsKAlphaExpander k α G) (v : V) (r : ℕ) :
min k ((1 + α) ^ r) ≤ ((ball G v r).ncard : ℝ) := by sorry
end CycleLengthsExp.WellSpread
Source
Friedman and Krivelevich, Cycle lengths in expanding graphs, arXiv:1912.11011v2, p. 4, proof of Lemma 2.1, first sentence (cited there from Proposition 3.1 of [21])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.