Lemma 10.2 (Pullback) — G̃₀ + G₁ is a (1 + ε)(1 + 1/c)²-approximation of G
ProvedSpectralSparsify.Pullback.lemma_10_2Let be a weighted graph on vertices, let be a partition of into nonempty parts, and let be its map. Set , the edges between different parts, , and . Let , let be a -approximation of the contraction of under , and let be a pullback of under . Let and assume
- each set of vertices is connected by edges in ,
- every edge in has weight at least , and
- every edge in has weight .
Then is an -approximation of for
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 . 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`. is a weighted graph `zt` on `Fin k` with `IsApprox (1 + ε) zt (contraction (crossPart w π) π)`; 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: ("for some "; with an empty already gives a counterexample, as 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 -edges between any two vertices of the same part. The conclusion is `IsApprox ((1 + ε) * (1 + 1/c)^2) (wt + intraPart w π) w`.
import Mathlib import Definitions.Def_SpectralSparsify_Pullback_WeightedGraph import Definitions.Def_SpectralSparsify_Pullback_Contraction
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.