Lemma 2.4, p. 6 — contracting parts of size ≤ C gives a (k/C, α/C)-expander on r ≥ n/C vertices
ProvedCycleLengthsExp.WellSpread.lemma_2_4expander-graphsgraph-contractionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , , and let be a -expander on vertices. Let be disjoint non-empty vertex sets, each of size at most , with . Let be the graph on obtained by contracting each to a vertex: are adjacent when some edge of joins and . Then
In the proof of Theorem 1 it turns subtrees of bounded size into single vertices, so that a long path can be found in the contracted graph.
Formalization Note. The partition is a surjection with ; surjectivity is the non-emptiness of the parts. The contracted graph has no loops.
Preamble
import Mathlib import Definitions.Def_CycleLengthsExp_WellSpread_Setting
Formal statement
namespace CycleLengthsExp.WellSpread
theorem lemma_2_4 (n r : ℕ) (G : SimpleGraph (Fin n)) (k α C : ℝ)
(hk : 0 < k) (hα : 0 < α) (hC : 0 < C) (hG : IsKAlphaExpander k α G)
(f : Fin n → Fin r) (hf : Function.Surjective f)
(hfib : ∀ i : Fin r, ((f ⁻¹' {i}).ncard : ℝ) ≤ C) :
(n : ℝ) / C ≤ r ∧ IsKAlphaExpander (k / C) (α / C) (contract G f) := by sorry
end CycleLengthsExp.WellSpread
Source
Friedman and Krivelevich, Cycle lengths in expanding graphs, arXiv:1912.11011v2, p. 6, Lemma 2.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.