Lemma 28 — A hitting set gives a +2 spanner inside the preserver
OpenDistancePreserver934.Exact.Supplement.lemma_28additive-spannersdistance-preserversgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a minimal preserver of on at most vertices, with normalized distinct reachable unordered demands. Suppose and nonempty hits in , with finite . For one absolute , there is with additive error on relative to , and
The guarantee includes both distance inequalities, retains containment in , and allows , including a singleton hitting set. This converts a hitting certificate into an additive batch spanner.
Differences from the source:
- encoding: finite graphs on n vertices, with the section demand convention → an arbitrary finite vertex type, unordered technical demands in §4 and §7.1–7.2 and ordered demands in Definition 26 and §8; reason: the published graph and extended-distance definitions retain exactly these instances; undirected edges are counted once
- encoding: absolute O and Ω coefficients → positive existential real coefficients before every graph, demand and real parameter; reason: this makes the source uniformity explicit without selecting unsupported numerical constants
Preamble
import Definitions.Def_DistancePreserver934_Exact_Supplement_EdgePaths import Definitions.Def_DistancePreserver934_Exact_Supplement_Hitting import Definitions.Def_DistancePreserver934_Exact_Supplement_Sourcewise import Definitions.Def_DistancePreserver934_Exact_Supplement_Budgets set_option autoImplicit false
Formal statement
namespace DistancePreserver934.Exact.Supplement
open Classical
theorem lemma_28 :
∃ C : ℝ, 0 < C ∧ ∀ {V : Type} [Fintype V]
(G H : SimpleGraph V) (R Q : Finset (Sym2 V)) (S : Finset V) (n : ℕ),
Fintype.card V ≤ n → IsDemandSet G R → IsMinimalPreserver G H R →
Q.Nonempty → Q ⊆ R → S.Nonempty → HitsAll H S Q → diam H S ≠ ⊤ →
∃ J : SimpleGraph V, J ≤ H ∧ IsAdditiveUnordered G J Q 2 ∧
(numEdges J : ℝ) ≤ C * ((n : ℝ) +
Real.sqrt ((n : ℝ) * (Q.card : ℝ) * (S.card : ℝ) * ((diam H S).toNat : ℝ)))
:= by sorry
end DistancePreserver934.Exact.Supplement
Source
Yanyu Chen, Yu Chen, Zihan Tan, Mingyang Yang, Improved Bounds on Distance Preservers, STOC 2027 submission #934 (October 2026); canonical source.pdf SHA-256 79b3d23a6e7b7fc6148c7a627181474a0129fb2f4c1d04ccd94c1da7987ed76b; Lemma 28, printed p. 26–27 (PDF p. 27–28)