§7.1 — adjacency walk sum bounded by spectral radius
ProvedEvenCycleTuran.PathCount.rayleigh_stepadjacency-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1spectral-graph-theorywalks
Let have vertices, real adjacency matrix , and spectral radius . For every ,
This bounds the total walk count by a graph-wide spectral quantity and is the matrix inequality used in both path-count upper bounds of the paper.
Formalization Note The spectral radius is the maximum of the absolute values of the real eigenvalues. The finite index set gives zero for the empty graph.
Preamble
import Mathlib import Definitions.Def_EvenCycleTuran_PathCount_Setting
Formal statement
namespace EvenCycleTuran.PathCount
/-- The Rayleigh quotient bounds the all-ones quadratic form of a power of the
adjacency matrix by the graph's spectral radius. -/
theorem rayleigh_step (n l : ℕ) (hl : 1 ≤ l) (G : SimpleGraph (Fin n))
[DecidableRel G.Adj] :
(∑ i : Fin n, ∑ j : Fin n, ((G.adjMatrix ℝ) ^ (l - 1)) i j) ≤
(n : ℝ) * specRad G ^ (l - 1) := by sorry
end EvenCycleTuran.PathCount
Source
Gerbner, Győri, Methuku and Vizer, Generalized Turán problems for even cycles, arXiv:1712.07079v3, p. 30, §7.1, paragraph following equation (7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.