Lemma 2.1: the penalized optimum approximates distance
ProvedTriFreeEst247.Main.lemma_2_1graph-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1property-testingquery-complexity
Let be any graph on vertices, let , and let . With distance normalized by and as above,
This compares the penalized optimum with the original distance and retains both inequalities.
Differences from the source:
- encoding: finite graphs and their vertex sets → simple graphs on Fin n, with unordered edges and triangles; reason: relabeling preserves every source instance and all normalized quantities
- encoding: λ ≥ R△(ε) → removalParameter ε ≤ ENNReal.ofReal λ; reason: the extended parameter retains infinity; the comparison forces a finite nonnegative weight at least one
Preamble
import Mathlib import Definitions.Def_TriFreeEst247_Main_Score open scoped ENNReal
Formal statement
namespace TriFreeEst247.Main
theorem lemma_2_1 {n : ℕ} (hn : 1 ≤ n) (G : Graph n) (ε lam : ℝ)
(hε : 0 < ε ∧ ε < 1) (hlam : removalParameter ε ≤ ENNReal.ofReal lam) :
scoreOpt G lam ≤ distance G ∧ distance G ≤ scoreOpt G lam + ε := by sorry
end TriFreeEst247.Main
Source
Asaf Shapira, Nick Kushnir, Triangle-Freeness: Estimation Is as Easy as Testing, STOC 2027 submission #247 (October 2026), source.pdf SHA-256 c24a6ad41f5c2465027e143e0aa757c3288add8cceb703078b9c0c2e18a0c3ad, p.7, Lemma 2.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.