Definition 9 — demand hitting
DefinitionDistancePreserver934_Exact_Supplement_Hittingadditive-spannersdistance-preserversgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
A vertex hits a demand in if an edge is essential to and one of its endpoints is adjacent to in . A set hits when
Essentiality is the published predicate quantifying over every shortest walk in the current graph. Hitting differs from covering by the extra adjacency; it includes no private-edge, density or length hypothesis.
Definition code
import Definitions.Def_DistancePreserver934_Exact_Essential
set_option autoImplicit false
namespace DistancePreserver934.Exact.Supplement
open Classical
/-- Definition 9: one adjacency from a vertex to an endpoint of an essential edge. -/
def Hits {V : Type} (H : SimpleGraph V) (u : V) (q : Sym2 V) : Prop :=
∃ e ∈ H.edgeSet, ∃ x ∈ e, H.Adj u x ∧ IsEssential H q e
/-- Every demand has a hitting tuple whose first vertex lies in S. -/
def HitsAll {V : Type} (H : SimpleGraph V) (S : Finset V) (Q : Finset (Sym2 V)) : Prop :=
∀ q ∈ Q, ∃ u ∈ S, Hits H u q
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; Definition 9, printed p. 13 (PDF p. 14)