Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sorted adjacency eigenvalues and computable graph families

Definition
MTWalkSAT3CNF_TwoOcc_Supplement_Graph

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-algorithmssatisfiability

A finite simple graph is represented by Mathlib's graph on Fin⁡N\operatorname{Fin}NFinN. Its real adjacency matrix has eigenvalues λ1≥⋯≥λN\lambda_1\ge\cdots\ge\lambda_Nλ1​≥⋯≥λN​, listed with multiplicity. The graph conditions used in §6 are

N>0,G connected and 102-regular,λ1=102,∣λi∣<21 (2≤i≤N).N>0,\quad G\text{ connected and }102\text{-regular},\quad\lambda_1=102,\quad|\lambda_i|<21\ (2\le i\le N).N>0,G connected and 102-regular,λ1​=102,∣λi​∣<21 (2≤i≤N).

A finite adjacency matrix is encoded by a pair of natural numbers: its order and its row-major adjacency bits. Decoding symmetrizes the relation and removes the diagonal, so every code yields a simple graph and every finite simple graph can be encoded. An explicit expander family is a computable function from natural indices to these pairs whose decoded graphs satisfy the displayed conditions and whose vertex counts tend to infinity. This retains an actual algorithmic enumeration, without imposing an efficiency bound.

Definition code
import Mathlib

set_option autoImplicit false

namespace MTWalkSAT3CNF.TwoOcc.Supplement

/-- Eigenvalues of the real adjacency matrix, decreasingly, including multiplicity. -/
noncomputable def adjacencyEigenvalues {N : ℕ} (G : SimpleGraph (Fin N)) : Fin N → ℝ := by
  classical
  have h : (G.adjMatrix ℝ).IsHermitian := by
    ext i j
    simp [Matrix.conjTranspose_apply, SimpleGraph.adj_comm]
  exact fun i => h.eigenvalues₀ ⟨i.val, by simp⟩

/-- Precisely the graph conditions used in §6; no runtime condition is bundled here. -/
def GoodGraph {N : ℕ} (G : SimpleGraph (Fin N)) : Prop :=
  0 < N ∧ G.Connected ∧
  (∀ v, (Set.ncard (G.neighborSet v)) = 102) ∧
  (∀ i : Fin N, i.val = 0 → adjacencyEigenvalues G i = 102) ∧
  (∀ i : Fin N, 0 < i.val → |adjacencyEigenvalues G i| < 21)

/-- Finite simple graph decoded from (vertex count, row-major adjacency bits).
Symmetrization and removal of the diagonal make every code a simple graph. -/
def graphOfCode (c : ℕ × ℕ) : SimpleGraph (Fin c.1) where
  Adj u v := u ≠ v ∧ (c.2.testBit (u.val*c.1+v.val) = true ∨
    c.2.testBit (v.val*c.1+u.val) = true)
  symm := ⟨fun _ _ h => ⟨Ne.symm h.1, h.2.symm⟩⟩
  loopless := ⟨fun _ h => h.1 rfl⟩

/-- A computable output code gives a finite adjacency matrix, with no efficiency requirement. -/
def ExplicitExpanderFamily (f : ℕ → ℕ × ℕ) : Prop :=
  Computable f ∧ (∀ j, GoodGraph (graphOfCode (f j))) ∧
  Filter.Tendsto (fun j => (f j).1) Filter.atTop Filter.atTop

end MTWalkSAT3CNF.TwoOcc.Supplement
Source
Minbo Gao, Kun He, Tao Jiang, STOC 2027 submission #914 (October 2026), §6.1, Lemma 6.2 and its proof, p. 35; https://github.com/sigact-stoc/stoc2027/releases/download/papers-2/914.pdf

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