Theorem 1 — Sparsify with is a spectral sparsifier with probability
ProvedEffResSparsify.Sampling.theorem_1There are an absolute constant and a threshold such that the following holds for every . Let be a connected weighted graph on vertices with positive edge weights and Laplacian , and let . Let
and let , with Laplacian : edges are drawn independently with replacement, edge with probability proportional to (its weight times its effective resistance), and each draw of adds weight to in . Then with probability at least ,
This is the main theorem of the paper: every weighted graph has a spectral sparsifier with edges, obtained by independent sampling according to effective resistances.
Formalization Note The paper's " is the constant in Lemma 5" and " sufficiently large" are quantified as , before the graph, the edge type and , so both are uniform over all graphs and all admissible . The printed is not an integer and is rounded up. is natural. Vertices are Fin n; the edge set is any finite type with an arbitrary orientation and no loops (parallel edges allowed). Probability is the finite sum over the outcomes of times the indicator of the event.
import Mathlib import Definitions.Def_EffResSparsify_Sampling_Defs
namespace EffResSparsify.Sampling
open Matrix
/-- Theorem 1, p. 2: there are an absolute constant `C > 0` and a threshold `N₀` such that for
every `n ≥ N₀`, every connected weighted graph `G` on `n` vertices and every
`1/√n < ε ≤ 1`, with `q = ⌈9 C² n log n / ε²⌉`, the graph `H = Sparsify(G, q)` satisfies
`(1 − ε) xᵀ L x ≤ xᵀ L̃ x ≤ (1 + ε) xᵀ L x` for all `x ∈ ℝⁿ` with probability at least `1/2`. -/
theorem theorem_1 :
∃ C : ℝ, 0 < C ∧ ∃ N₀ : ℕ, ∀ n : ℕ, N₀ ≤ n →
∀ (E : Type) [Fintype E] [DecidableEq E] (G : WGraph (Fin n) E), G.IsConnected →
∀ ε : ℝ, 1 / Real.sqrt n < ε → ε ≤ 1 →
(1 / 2 : ℝ) ≤ G.sparsifyProb ⌈9 * C ^ 2 * n * Real.log n / ε ^ 2⌉₊
(fun s => ∀ x : Fin n → ℝ,
(1 - ε) * (x ⬝ᵥ (G.laplacian *ᵥ x)) ≤
x ⬝ᵥ (G.sparsifiedLaplacian ⌈9 * C ^ 2 * n * Real.log n / ε ^ 2⌉₊ s *ᵥ x) ∧
x ⬝ᵥ (G.sparsifiedLaplacian ⌈9 * C ^ 2 * n * Real.log n / ε ^ 2⌉₊ s *ᵥ x) ≤
(1 + ε) * (x ⬝ᵥ (G.laplacian *ᵥ x))) := by sorry
end EffResSparsify.Sampling
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.