Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 10.2 (Pullback) — G̃₀ + G₁ is a (1 + ε)(1 + 1/c)²-approximation of G

Proved
SpectralSparsify.Pullback.lemma_10_2

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

graph-contractionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1spectral-graph-theoryspectral-sparsification

Let G=(V,E,w)G=(V,E,w)G=(V,E,w) be a weighted graph on n=∣V∣n=|V|n=∣V∣ vertices, let V1,…,VkV_1,\dots,V_kV1​,…,Vk​ be a partition of VVV into nonempty parts, and let π\piπ be its map. Set E0=∂(V1,…,Vk)E_0=\partial(V_1,\dots,V_k)E0​=∂(V1​,…,Vk​), the edges between different parts, G0=(V,E0,w)G_0=(V,E_0,w)G0​=(V,E0​,w), E1=E−E0E_1=E-E_0E1​=E−E0​ and G1=(V,E1,w)G_1=(V,E_1,w)G1​=(V,E1​,w). Let 0≤ϵ<1/20\le\epsilon<1/20≤ϵ<1/2, let H~\widetilde HH be a (1+ϵ)(1+\epsilon)(1+ϵ)-approximation of the contraction of G0G_0G0​ under π\piπ, and let G~0\widetilde G_0G0​ be a pullback of H~\widetilde HH under π\piπ. Let c≥3c\ge 3c≥3 and assume

  1. each set of vertices ViV_iVi​ is connected by edges in E1E_1E1​,
  2. every edge in E1E_1E1​ has weight at least c2n3c^2n^3c2n3, and
  3. every edge in E0E_0E0​ has weight 111.

Then G~0+G1\widetilde G_0+G_1G0​+G1​ is an α\alphaα-approximation of GGG for

α=(1+ϵ)(1+1c)2.\alpha=(1+\epsilon)\Big(1+\frac1c\Big)^2 .α=(1+ϵ)(1+c1​)2.

The lemma says that, when the parts are held together by much heavier edges, a sparsifier of the light edges between them can be built on the contracted graph, with one vertex per part, and pulled back to VVV. It is how Spielman and Teng pass from graphs with bounded weight ratio to arbitrarily weighted graphs (algorithm Sparsify, §10.2).

Formalization Note The partition map is a surjective `π : V → Fin k`. H~\widetilde HH is a weighted graph `zt` on `Fin k` with `IsApprox (1 + ε) zt (contraction (crossPart w π) π)`; G~0\widetilde G_0G0​ is a weighted graph `wt` with `IsPullback wt zt π`. Two hypotheses the paper leaves implicit are explicit here, and each is needed for the statement to hold: ϵ≥0\epsilon\ge 0ϵ≥0 ("for some ϵ<1/2\epsilon<1/2ϵ<1/2"; with ϵ<0\epsilon<0ϵ<0 an empty E0E_0E0​ already gives a counterexample, as α<1\alpha<1α<1 is possible), and that every edge of the pullback joins two different parts (part of `IsPullback`; contraction cannot see an edge inside a part). Hypothesis 1 is reachability in the graph of E1E_1E1​-edges between any two vertices of the same part. The conclusion is `IsApprox ((1 + ε) * (1 + 1/c)^2) (wt + intraPart w π) w`.

Preamble
import Mathlib
import Definitions.Def_SpectralSparsify_Pullback_WeightedGraph
import Definitions.Def_SpectralSparsify_Pullback_Contraction
Formal statement
namespace SpectralSparsify.Pullback

/-- Lemma 10.2 (Pullback), arXiv:0808.4134v3, pp. 36–37. Let `G = (V, E, w)` be a weighted graph,
`V₁, …, V_k` a partition of `V` with map `π`, `G₀` the edges between parts and `G₁` the edges inside
parts. Let `0 ≤ ε < 1/2`, let `H̃` be a `(1 + ε)`-approximation of the contraction of `G₀` under `π`,
and let `G̃₀` be a pullback of `H̃` under `π`. Assume `c ≥ 3` and
1. each `Vᵢ` is connected by edges in `E₁`,
2. every edge in `E₁` has weight at least `c² n³` (`n = |V|`), and
3. every edge in `E₀` has weight `1`.
Then `G̃₀ + G₁` is an `α`-approximation of `G` for `α = (1 + ε)(1 + 1/c)²`. -/
theorem lemma_10_2 {V : Type*} [Fintype V] [DecidableEq V] {k : ℕ}
    (w : V → V → ℝ) (hw : SpectralSparsify.Sampling.IsWGraph w) (π : V → Fin k) (hπ : Function.Surjective π)
    (ε c : ℝ) (hε0 : 0 ≤ ε) (hε : ε < 1 / 2) (hc : 3 ≤ c)
    (zt : Fin k → Fin k → ℝ) (hzt : SpectralSparsify.Sampling.IsWGraph zt)
    (happrox : SpectralSparsify.Sampling.IsApprox (1 + ε) zt (contraction (crossPart w π) π))
    (wt : V → V → ℝ) (hwt : SpectralSparsify.Sampling.IsWGraph wt) (hpb : IsPullback wt zt π)
    (h1 : ∀ u v, π u = π v → (intraGraph w π).Reachable u v)
    (h2 : ∀ u v, π u = π v → w u v ≠ 0 → c ^ 2 * (Fintype.card V : ℝ) ^ 3 ≤ w u v)
    (h3 : ∀ u v, π u ≠ π v → w u v ≠ 0 → w u v = 1) :
    SpectralSparsify.Sampling.IsApprox ((1 + ε) * (1 + 1 / c) ^ 2) (wt + intraPart w π) w := by sorry

end SpectralSparsify.Pullback
Source
D. A. Spielman, S.-H. Teng, Spectral Sparsification of Graphs, arXiv:0808.4134v3, pp. 36–37, Lemma 10.2 (Pullback)
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