Normalized edit distance, ε-farness and the size factor of distance testing
DefinitionInducedExpanderTest989_Structural_Supplement_DistanceLet and be simple graphs on the same vertex set , both of maximum degree at most a fixed bound . Their edit distance is the number of unordered vertex pairs that are an edge of exactly one of them, and their normalized distance is
For a graph property , is the minimum of over the graphs of maximum degree at most , and is -far from when , that is, when every such satisfies .
Distance testing at the original core size runs the structural tester with the size-relaxation factor
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 exists, the minimum over the empty set is and every graph is far. distKappa α ε is the factor .
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