Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Adjacency eigenvalues below twelve give ordinary walk gap above one seventh

Proved
OPG37364.spectralGap_gt_one_seventh_of_adjacency_bound

by arexychen · Sep 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theorylinear-algebramarkov-chainsspectral-gap

Let GGG be a connected finite 141414-regular simple graph, and let AAA be its real adjacency matrix. Suppose every real eigenvalue μ\muμ of AAA whose value is not 141414 satisfies μ<12\mu<12μ<12.

Then the ordinary simple-random-walk matrix PGP_GPG​ satisfies

spectralGap⁡(PG)>17.\operatorname{spectralGap}(P_G)>\frac17.spectralGap(PG​)>71​.

The matrix is PG=A/14P_G=A/14PG​=A/14. The platform definition of the ordinary gap is 1−sup⁡{r:r is a real eigenvalue of PG, r≠1}1-\sup\{r: r\text{ is a real eigenvalue of }P_G,\ r\ne1\}1−sup{r:r is a real eigenvalue of PG​, r=1}. The adjacency hypothesis is expressed directly by Mathlib real matrix spectrum membership, with a strict one-sided bound. It permits the bipartite eigenvalue −14-14−14 and does not use the absolute spectral gap. No bipartiteness, girth, cut expansion, immunity or perfect-matching assumption is required.

Formalization Note. The direct value-based formulation avoids identifying an ordered second eigenvalue with a value-excluding supremum. Connectedness is an explicit hypothesis; no simplicity theorem for the top eigenvalue is an additional assumption.

Preamble
import Definitions.Def_opg37364_matching_cuts
import Definitions.Def_mm_spectral
import Mathlib.Combinatorics.SimpleGraph.AdjMatrix
import Mathlib.Analysis.Matrix.Spectrum

set_option autoImplicit false
open scoped Classical
Formal statement
namespace OPG37364

theorem spectralGap_gt_one_seventh_of_adjacency_bound
    {n : ℕ} (G : SimpleGraph (Fin n))
    (hconn : IsConnected G) (hreg : IsRegularOfDegree G 14)
    (hAdj : ∀ μ : ℝ, μ ∈ spectrum ℝ (G.adjMatrix ℝ) → μ ≠ 14 → μ < 12) :
    (1 : ℝ) / 7 < MarkovMixing.spectralGap (MarkovMixing.graphWalk G) := by sorry

end OPG37364
Source
Standard finite-dimensional matrix scaling and finite-spectrum argument, using Mathlib matrix spectrum and the exact MarkovMixing definitions. This supplies a sufficient normalization step for the proof route in Feghali--Lucke--Paulusma--Ries, Algorithmica 87 (2025), Lemma 5, https://link.springer.com/article/10.1007/s00453-025-01318-8. The threshold 12 is weaker than the LPS bound 2 sqrt(13); this theorem is not a graph-existence or LPS theorem.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me