Theorem 2 proof — a long path after deleting ⌊αn/4⌋ vertices
ProvedCycleLengthsExp.ManyLengths.path_after_deletioncycle-lengthsexpander-graphsgraph-pathsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and let be an -expander on vertices. If is any vertex set with , then has a simple path with exactly
edges. In other words, every vertex of the path lies outside .
The path supplies the large set of vertices along which the later cycle construction varies its length.
Formalization Note The page obtains as the vertices of a breadth-first-search tree, but its displayed expansion estimate uses only . This item states the resulting path claim for every set of that size. The additional makes a starting vertex available. The paper cites “Lemma 2.4” here; the long-path statement is Lemma 2.5.
Preamble
import Mathlib import Definitions.Def_CycleLengthsExp_ManyLengths_Setting
Formal statement
namespace CycleLengthsExp.ManyLengths
/-- The path in `G \ T` in the proof of Theorem 2, p. 13. -/
theorem path_after_deletion (n : ℕ) (hn : 0 < n) (α : ℝ)
(hα : 0 < α) (hα1 : α ≤ 1) (G : SimpleGraph (Fin n))
(hG : CycleLengthsExp.WellSpread.IsAlphaExpander α G) (S : Set (Fin n))
(hS : S.ncard = Nat.floor (α * (n : ℝ) / 4)) :
∃ (u v : Fin n) (p : G.Walk u v),
p.IsPath ∧ p.length = Nat.ceil (α * (n : ℝ) / 4) - 1 ∧
∀ w ∈ p.support, w ∉ S := by sorry
end CycleLengthsExp.ManyLengths
Source
Friedman and Krivelevich, Cycle lengths in expanding graphs, arXiv:1912.11011v2, p. 13, proof of Theorem 2, paragraph beginning 'Run the BFS algorithm'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.