Corollary 5.1 — size slack implies small edit distance
OpenInducedExpanderTest989.Structural.Supplement.corollary_5_1graph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testing
Let , , , and . Write for the class of graphs on having a vertex set with and , with conductance normalized by . For every and every simple graph on of maximum degree at most ,
where and the minimum ranges over graphs of maximum degree at most .
The corollary converts a core that misses the size threshold by the slack into a full-size core at small normalized edit distance. It is the soundness step of Theorem 5.1.
Formalization Note is the mission's beta α κ, and is LargeEnough n α κ. The conclusion is stated as the existence of a witness of maximum degree at most in with .
Differences from the source:
- encoding: dist_d(G, P_{α,θ/(2d+2)}) ≤ 5β/2 → some H of maximum degree ≤ d with HasCore d H α (θ/(2d+2)) and |E(G)△E(H)| ≤ (5β/2)·d·n; reason: the minimum over the finite set of graphs on [n] is attained, and dn > 0
- encoding: G of maximum degree at most d (implicit) → hypothesis DegreeBound d G; reason: dist_d is defined only between graphs with degree bound d (§1.1)
Preamble
import Mathlib import Definitions.Def_InducedExpanderTest989_Structural_Parameters import Definitions.Def_InducedExpanderTest989_Structural_Supplement_Distance set_option autoImplicit false open scoped BigOperators ENNReal NNReal noncomputable section
Formal statement
namespace InducedExpanderTest989.Structural.Supplement
/-- Peng–Shen, STOC 2027 #989, Corollary 5.1 (p. 33, PDF 35), with `β = (1 − κ)α` = `beta α κ`.
`dist_d(G, P_{α,θ/(2d+2)}) ≤ 5β/2` is the existence of a target `H` of maximum degree at most
`d` with `|E(G) △ E(H)| ≤ (5β/2) d n`. -/
theorem corollary_5_1 (n d : ℕ) (α κ : ℝ) (hd : 3 ≤ d) (hα : 0 < α) (hα1 : α ≤ 1)
(hκ : 3/4 ≤ κ) (hκ1 : κ < 1) (hn : LargeEnough n α κ) (θ : ℝ) (hθ : 0 < θ) (hθ1 : θ ≤ 1)
(G : SimpleGraph (Fin n)) (hG : DegreeBound d G)
(hcore : HasCore d G (α - beta α κ) θ) :
∃ H : SimpleGraph (Fin n), DegreeBound d H ∧ HasCore d H α (θ / (2 * d + 2)) ∧
(editDistance G H : ℝ) ≤ (5 * beta α κ / 2) * d * n := by sorry
end InducedExpanderTest989.Structural.Supplement
Source
Pan Peng, Ranran Shen, Testing for a Large Induced Expander: Sublinear Algorithms and Query Lower Bounds, STOC 2027 submission #989 (October 2026), source.pdf SHA-256 98b4035a0ac121d1c1bfb6abdeb3cdb6cf3304ef3cb21b2cd58c97e4bbce6334, p.33 (PDF p.35), Corollary 5.1; distance definition p.3 (PDF p.5)