Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Normalized edit distance, ε-farness and the size factor of distance testing

Definition
InducedExpanderTest989_Structural_Supplement_Distance

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1property-testing

Let GGG and HHH be simple graphs on the same vertex set [n][n][n], both of maximum degree at most a fixed bound ddd. Their edit distance is the number ∣E(G)△E(H)∣|E(G)\triangle E(H)|∣E(G)△E(H)∣ of unordered vertex pairs that are an edge of exactly one of them, and their normalized distance is

distd(G,H)=∣E(G)△E(H)∣dn.\mathrm{dist}_d(G,H)=\frac{|E(G)\triangle E(H)|}{dn}.distd​(G,H)=dn∣E(G)△E(H)∣​.

For a graph property P\mathcal PP, distd(G,P)\mathrm{dist}_d(G,\mathcal P)distd​(G,P) is the minimum of distd(G,H)\mathrm{dist}_d(G,H)distd​(G,H) over the graphs H∈PH\in\mathcal PH∈P of maximum degree at most ddd, and GGG is ε\varepsilonε-far from P\mathcal PP when distd(G,P)>ε\mathrm{dist}_d(G,\mathcal P)>\varepsilondistd​(G,P)>ε, that is, when every such HHH satisfies ∣E(G)△E(H)∣>εdn|E(G)\triangle E(H)|>\varepsilon dn∣E(G)△E(H)∣>εdn.

Distance testing at the original core size runs the structural tester with the size-relaxation factor

κ(α,ε)=1−min⁡{14,ε8α}.\kappa(\alpha,\varepsilon)=1-\min\Big\{\frac14,\frac{\varepsilon}{8\alpha}\Big\}.κ(α,ε)=1−min{41​,8αε​}.

These objects state the distance-testing promise of Theorem 5.1 and the repair bounds of Lemma 5.1 and Corollary 5.1.

Formalization Note The edit distance is the cardinality of the symmetric difference of the two edge sets (editDistance). The predicate FarFrom d ε G P writes the minimum out as a statement about every target graph; when no target graph of maximum degree at most ddd exists, the minimum over the empty set is +∞+\infty+∞ and every graph is far. distKappa α ε is the factor κ(α,ε)\kappa(\alpha,\varepsilon)κ(α,ε).

Definition code
import Mathlib
import Definitions.Def_InducedExpanderTest989_Structural_Graph

set_option autoImplicit false
open scoped BigOperators ENNReal NNReal symmDiff
noncomputable section

namespace InducedExpanderTest989.Structural.Supplement

/-- `|E(G) △ E(H)|`: the number of unordered pairs that are an edge of exactly one of the two
graphs on the same vertex set `[n]` (§1.1, p. 3). -/
def editDistance {n : ℕ} (G H : SimpleGraph (Fin n)) : ℕ :=
  (symmDiff G.edgeSet H.edgeSet).ncard

/-- `G` is `ε`-far from the property `P` (§1.1, p. 3): `dist_d(G, P) > ε`, where
`dist_d(G, H) = |E(G) △ E(H)| / (d n)` and the minimum ranges over graphs `H ∈ P` of maximum
degree at most `d`. The minimum is written out: every such `H` is at normalized distance `> ε`.
With no such `H` the minimum over `∅` is `+∞` and every graph is far. -/
def FarFrom {n : ℕ} (d : ℕ) (ε : ℝ) (G : SimpleGraph (Fin n))
    (P : SimpleGraph (Fin n) → Prop) : Prop :=
  ∀ H : SimpleGraph (Fin n), DegreeBound d H → P H → ε * d * n < (editDistance G H : ℝ)

/-- The size-relaxation factor of Theorem 5.1: `κ = 1 − min{1/4, ε/(8α)}`. -/
def distKappa (α ε : ℝ) : ℝ := 1 - min (1/4) (ε / (8 * α))

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.3 (PDF p.5), §1.1 "Distance testing"; p.32 (PDF p.34), Theorem 5.1 (choice of κ)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me