Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Claim 6.5 — every entry of Δ = D^{-1}(Ã − A) has |Δ_{i,j}| ≤ 1/Υ

Proved
SpectralSparsify.Sampling.claim_6_5

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-matricesspectral-sparsification

Let GGG be an unweighted graph with degrees di≥1d_i\ge 1di​≥1, adjacency matrix AAA and degree matrix DDD. Sample its edges with the probabilities pi,j=min⁡(1,Υ/min⁡(di,dj))p_{i,j}=\min(1,\Upsilon/\min(d_i,d_j))pi,j​=min(1,Υ/min(di​,dj​)) of (4) for a parameter Υ>1\Upsilon>1Υ>1, giving the adjacency matrix A~\widetilde AA of the sampled graph, and let Δ=D−1(A~−A)\Delta=D^{-1}(\widetilde A-A)Δ=D−1(A−A). Then for every outcome of the sampling that has positive probability, and all i,ji,ji,j,

∣Δi,j∣≤1Υ,|\Delta_{i,j}|\le\frac1\Upsilon,∣Δi,j​∣≤Υ1​,

that is, the bound holds with probability one.

The claim is the uniform entry bound used to control the higher moments of Δ\DeltaΔ (Lemma 6.6).

Formalization Note The paper states the claim for the entries of Δ\DeltaΔ on edges; on non-edges and on the diagonal Δi,j=0\Delta_{i,j}=0Δi,j​=0, so the Lean statement quantifies over all i,ji,ji,j. An outcome is a set TTT of edges of GGG with positive probability ∏e∈Tpe∏e∈E∖T(1−pe)>0\prod_{e\in T}p_e\prod_{e\in E\setminus T}(1-p_e)>0∏e∈T​pe​∏e∈E∖T​(1−pe​)>0; this excludes exactly the outcomes that drop an edge with pi,j=1p_{i,j}=1pi,j​=1, on which Δi,j=−1/di\Delta_{i,j}=-1/d_iΔi,j​=−1/di​ can exceed 1/Υ1/\Upsilon1/Υ (the paper's "if pi,j=1p_{i,j}=1pi,j​=1, then Δi,j=0\Delta_{i,j}=0Δi,j​=0" is an almost-sure statement). The paper leaves implicit that every degree is positive (D−1D^{-1}D−1 requires it); the standing assumption Υ>1\Upsilon>1Υ>1 comes with (4).

Preamble
import Mathlib
import Definitions.Def_SpectralSparsify_Sampling_BernoulliSubset
import Definitions.Def_SpectralSparsify_Sampling_EdgeSampling
Formal statement
namespace SpectralSparsify.Sampling

/-- Claim 6.5 (Spielman–Teng, arXiv:0808.4134v3, p. 13). Let `G` be an unweighted graph with no
isolated vertex, sample its edges with the probabilities (4) for a parameter `Υ > 1`, and let
`Δ = D^{-1}(Ã - A)`. For every outcome `T ⊆ E` of positive probability and all `i, j`,
`|Δ_{i,j}| ≤ 1/Υ` (the bound holds with probability one: an edge with `p_{i,j} = 1` is always
kept, and the outcomes that drop it have probability `0`). -/
theorem claim_6_5 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (hdeg : ∀ v, 0 < G.degree v) (Υ : ℝ) (hΥ : 1 < Υ)
    (T : Finset (Sym2 V)) (hT : T ⊆ G.edgeFinset)
    (hTpos : 0 < outcomeProb G.edgeFinset (degSampleProb G Υ) T) (i j : V) :
    |deltaMat G (degSampleProb G Υ) T i j| ≤ 1 / Υ := by sorry

end SpectralSparsify.Sampling
Source
D. A. Spielman, S.-H. Teng, Spectral Sparsification of Graphs, arXiv:0808.4134v3, p. 13, Claim 6.5 (Δ defined on p. 10)
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

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