Theorem 7.1 — every graph with m edges has a (6 log_{4/3} 2m)⁻¹-decomposition with |∂(A₁, …, A_k)| ≤ |E|/2
ProvedSpectralSparsify.Decomp.theorem_7_1Let be a finite simple graph without isolated vertices and let . Then has a decomposition , that is, a partition of into nonempty sets, such that
- every part has conductance
where measures volumes with the degrees of ; and 2. the number of edges between different parts satisfies
Both conditions hold for the same partition: a partition into singletons has conductance everywhere but cuts every edge, and the trivial partition cuts nothing but may have small conductance. The theorem is the existence statement behind the paper's spectral sparsifiers: each high-conductance part can be sparsified by sampling, and the at most crossing edges are handled recursively.
Formalization Note The paper leaves implicit that has no isolated vertices; conductance is otherwise, and the hypothesis is the setting in which is defined. Under it, forces and the statement is trivially true (Lean's makes the bound ). The logarithm is Real.logb (4/3) applied to . The bound on the boundary is stated over as .
import Mathlib import Definitions.Def_SpectralSparsify_Decomp_cond import Definitions.Def_SpectralSparsify_Decomp_decompBoundary
namespace SpectralSparsify.Decomp
/-- Theorem 7.1 (arXiv:0808.4134v3, p. 17). Let `G = (V, E)` be a graph without isolated
vertices and `m = |E|`. Then `G` has a `(6 log_{4/3} 2m)⁻¹`-decomposition `(A₁, …, A_k)`,
i.e. a partition of `V` with `Φ^G_{Aᵢ} ≥ (6 log_{4/3} 2m)⁻¹` for all `i`, whose boundary
satisfies `|∂(A₁, …, A_k)| ≤ |E|/2`. -/
theorem theorem_7_1 {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
[DecidableRel G.Adj] (hdeg : ∀ v, 0 < G.degree v) :
∃ P : Finpartition (Finset.univ : Finset V),
(∀ A ∈ P.parts,
(6 * Real.logb (4 / 3) (2 * (G.edgeFinset.card : ℝ)))⁻¹ ≤ cond G A) ∧
((decompBoundary G P).card : ℝ) ≤ (G.edgeFinset.card : ℝ) / 2 := by sorry
end SpectralSparsify.Decomp
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.