Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 6.1 (Sampling High-Conductance Graphs) — with probability ≥ 1 − p, G̃ = (V, F̃ ∪ H) is a (1+ε)-approximation of G and |F̃| ≤ 288k²/(ελ)²·|S|

Proved
SpectralSparsify.Sampling.theorem_6_1

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

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1random-samplingspectral-graph-theoryspectral-sparsification

Let ϵ,p∈(0,1/2)\epsilon,p\in(0,1/2)ϵ,p∈(0,1/2) and let G=(V,E)G=(V,E)G=(V,E) be an unweighted graph without isolated vertices whose smallest non-zero normalized Laplacian eigenvalue is at least λ>0\lambda>0λ>0. Let S⊆VS\subseteq VS⊆V, let FFF be the edges of the induced subgraph G(S)G(S)G(S) and H=E−FH=E-FH=E−F the rest of the edges. Let kkk be an even integer with

k≥log⁡2(3/p)andk≥log⁡2∣S∣,k\ge\log_2(3/p)\quad\text{and}\quad k\ge\log_2|S|,k≥log2​(3/p)andk≥log2​∣S∣,

and let (S,F~)=Sample((S,F),ϵ,p,λ)(S,\widetilde F)=\mathtt{Sample}((S,F),\epsilon,p,\lambda)(S,F)=Sample((S,F),ϵ,p,λ) with this kkk: with Υ=(12k/(ϵλ))2\Upsilon=(12k/(\epsilon\lambda))^2Υ=(12k/(ϵλ))2 and did_idi​ the degree of iii in G(S)G(S)G(S), each edge (i,j)∈F(i,j)\in F(i,j)∈F is kept independently with probability 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​)) and then has weight 1/pi,j1/p_{i,j}1/pi,j​. Let G~=(V,F~∪H)\widetilde G=(V,\widetilde F\cup H)G=(V,F∪H), the edges of HHH keeping weight 111. Then, with probability at least 1−p1-p1−p, both

  1. (S.1) G~\widetilde GG is a (1+ϵ)(1+\epsilon)(1+ϵ)-approximation of GGG, and
  2. (S.2) the number of edges in F~\widetilde FF is at most
288 k2(ϵλ)2 ∣S∣.\frac{288\,k^2}{(\epsilon\lambda)^2}\,|S|.(ϵλ)2288k2​∣S∣.

This is the sampling theorem of the paper: in a graph of high conductance (large λ\lambdaλ), keeping each edge with probability inversely proportional to the smaller endpoint degree yields a spectral approximation with O(∣S∣log⁡2(⋅)/(ϵλ)2)O(|S|\log^2(\cdot)/(\epsilon\lambda)^2)O(∣S∣log2(⋅)/(ϵλ)2) edges. It is the step that the paper combines with graph decompositions to sparsify arbitrary graphs.

Formalization Note The paper sets k=max⁡(log⁡2(3/p),log⁡2n)k=\max(\log_2(3/p),\log_2 n)k=max(log2​(3/p),log2​n) in Sample\mathtt{Sample}Sample, but its proof applies Lemma 6.3, which holds for even integers kkk, with this kkk; for a real kkk the proof does not go through, and rounding breaks its constants. The statement therefore takes any even natural number kkk above both logarithms; the printed theorem is the case where the maximum is itself an even integer. nnn in Sample\mathtt{Sample}Sample is the number of vertices of its input (S,F)(S,F)(S,F), i.e. ∣S∣|S|∣S∣. Implicit hypotheses made explicit: every vertex of GGG has degree at least 111 (LG\mathcal L_GLG​ requires D−1/2D^{-1/2}D−1/2) and λ>0\lambda>0λ>0. GGG is not assumed connected. The two conclusions hold simultaneously on one event of probability at least 1−p1-p1−p; probability is over the independent sampling of the edges of FFF (finite sum over the outcomes T⊆FT\subseteq FT⊆F, with F~=T\widetilde F=TF=T).

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

/-- Theorem 6.1 (Sampling High-Conductance Graphs; Spielman–Teng, arXiv:0808.4134v3, p. 8). Let
`ε, p ∈ (0, 1/2)` and let `G = (V, E)` be an unweighted graph with no isolated vertex whose smallest
nonzero normalized Laplacian eigenvalue is at least `λ > 0`. Let `S ⊆ V`, let `F` be the edges of
`G(S)` and `H = E - F`. Run `Sample((S, F), ε, p, λ)` with an even integer `k ≥ log₂(3/p)`,
`k ≥ log₂ |S|`: each edge `{i, j} ∈ F` is kept independently with probability
`p_{i,j} = min(1, Υ / min(d_i, d_j))`, `Υ = (12k/(ελ))²`, `d_i` the degree in `G(S)`, and gets weight
`1/p_{i,j}`; `G̃ = (V, F̃ ∪ H)` with weight `1` on `H`. Then with probability at least `1 - p`,
(S.1) `G̃` is a `(1+ε)`-approximation of `G`, and (S.2) `|F̃| ≤ 288 k² / (ελ)² · |S|`.
The paper sets `k = max(log₂(3/p), log₂ n)`; its proof needs `k` to be an even integer, so `k` is a
parameter here (the printed statement is the case where that maximum is an even integer). -/
theorem theorem_6_1 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    [DecidableRel G.Adj] (hdeg : ∀ v, 0 < G.degree v)
    (ε p lam : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1 / 2) (hp0 : 0 < p) (hp1 : p < 1 / 2)
    (hlam : 0 < lam) (hspec : NonzeroEigGE (normLap G) lam)
    (S : Finset V) (k : ℕ) (hk : Even k)
    (hk1 : Real.logb 2 (3 / p) ≤ k) (hk2 : Real.logb 2 S.card ≤ k) :
    1 - p ≤ prob (inducedEdges G S) (sampleSubgraphProb G S k ε lam)
      (fun T =>
        IsApprox (1 + ε) (sparsifierWeight G S (sampleSubgraphProb G S k ε lam) T)
            (adjWeight G) ∧
          (T.card : ℝ) ≤ 288 * (k : ℝ) ^ 2 / (ε * lam) ^ 2 * S.card) := by sorry

end SpectralSparsify.Sampling
Source
D. A. Spielman, S.-H. Teng, Spectral Sparsification of Graphs, arXiv:0808.4134v3, p. 8, Theorem 6.1 and the procedure Sample (proof pp. 15–16)
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