Claim 6.5 — every entry of Δ = D^{-1}(Ã − A) has |Δ_{i,j}| ≤ 1/Υ
ProvedSpectralSparsify.Sampling.claim_6_5Let be an unweighted graph with degrees , adjacency matrix and degree matrix . Sample its edges with the probabilities of (4) for a parameter , giving the adjacency matrix of the sampled graph, and let . Then for every outcome of the sampling that has positive probability, and all ,
that is, the bound holds with probability one.
The claim is the uniform entry bound used to control the higher moments of (Lemma 6.6).
Formalization Note The paper states the claim for the entries of on edges; on non-edges and on the diagonal , so the Lean statement quantifies over all . An outcome is a set of edges of with positive probability ; this excludes exactly the outcomes that drop an edge with , on which can exceed (the paper's "if , then " is an almost-sure statement). The paper leaves implicit that every degree is positive ( requires it); the standing assumption comes with (4).
import Mathlib import Definitions.Def_SpectralSparsify_Sampling_BernoulliSubset import Definitions.Def_SpectralSparsify_Sampling_EdgeSampling
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.