Definition 1 — -hopsets and the -hop distance
DefinitionPivotADO_OneHop_Supplement_HopsetLet be an undirected, unweighted simple graph with shortest-path distance (equal to between different components). Let be an integer and a real number. A set of edges on is a -hopset for when every edge carries the weight and, for all ,
where is the minimum weight of a – path in that uses at most edges (an edge of has weight ). The size of the hopset is ; the edges of are not counted, and may contain edges of .
The definition is the object of the hopset lower bounds (Theorems 3 and 4). The reverse inequality holds automatically and is not part of the definition.
Formalization Note is a simple graph on (unordered, loopless edges) and its size is its number of edges. The -hop distance is the infimum, in , over walks of length at most in of the sum of over the walk's edges; walks and paths give the same minimum, the empty walk gives for , and the infimum is when no walk of at most edges exists. The factor enters as ENNReal.ofReal k.
import Definitions.Def_PivotADO_OneHop_Geometry
set_option autoImplicit false
open scoped Classical ENNReal
noncomputable section
namespace PivotADO.OneHop.Supplement
/-! Definition 1 ((k, β)-hopset), Kadria–Roditty, STOC 2027 submission #584
(October 2026), pp.5–6 (PDF 6–7). The hopset `F` is a set of unordered edges on the
vertex set, encoded as a simple graph; an edge `(x, y)` of `F` has weight `δ_G(x, y)`,
and an edge of `G` has weight `1 = δ_G(x, y)`. -/
/-- `d^{≤β}_{G∪F}(u, v)`: the minimum weight of a `u`–`v` walk in `G ∪ F` with at most
`β` edges, each edge `(x, y)` weighted by `δ_G(x, y)`. It is `⊤` when no such walk exists,
and `0` for `u = v` (the empty walk). Walks and paths give the same minimum. -/
def hopDistance {V : Type*} (G F : SimpleGraph V) (β : ℕ) (u v : V) : ℝ≥0∞ :=
⨅ (p : (G ⊔ F).Walk u v) (_ : p.length ≤ β),
(p.darts.map fun d => distance G d.fst d.snd).sum
/-- `F` is a `(k, β)`-hopset for `G`: `d^{≤β}_{G∪F}(u, v) ≤ k · δ_G(u, v)` for all `u, v`.
The size of the hopset is `edgeCount F`; `F` may contain edges of `G`. -/
def IsHopset {V : Type*} (G F : SimpleGraph V) (k : ℝ) (β : ℕ) : Prop :=
∀ u v : V, hopDistance G F β u v ≤ ENNReal.ofReal k * distance G u v
end PivotADO.OneHop.Supplement