Theorem 2 proof — at least α²n/12 reachable path vertices
ProvedCycleLengthsExp.ManyLengths.x0_largecycle-lengthsexpander-graphsgraph-pathsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , and let be an -expander on vertices. Take any set of vertices and any simple path in with edges. Let be the vertices of reachable from by a simple path of at most edges whose internal vertices avoid both and . If , then
This is the large starting set from which the proof extracts many distinct cycle lengths.
Formalization Note The source suppresses rounding in this estimate. The disclosed size condition rules out the case , where and the printed inequality fails. The source's is the vertex set of a breadth-first-search tree; the counting argument uses its size and disjointness from .
Preamble
import Mathlib import Definitions.Def_CycleLengthsExp_ManyLengths_Setting
Formal statement
namespace CycleLengthsExp.ManyLengths
/-- The lower bound on `|X₀|` in the proof of Theorem 2, p. 14. -/
theorem x0_large (n : ℕ) (α : ℝ) (hα : 0 < α) (hα1 : α ≤ 1)
(hn : 12 ≤ α * (n : ℝ)) (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) (hp : p.IsPath)
(hlen : p.length = Nat.ceil (α * (n : ℝ) / 4) - 1)
(hdisj : ∀ w ∈ p.support, w ∉ S) :
α ^ 2 * (n : ℝ) / 12 ≤ ((X0 α G S p).ncard : ℝ) := by sorry
end CycleLengthsExp.ManyLengths
Source
Friedman and Krivelevich, Cycle lengths in expanding graphs, arXiv:1912.11011v2, pp. 13–14, proof of Theorem 2, definition of X₀ and 'The set X₀ is of size at least α²n/12'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.