Theorem 5 — Every edge-disjoint minimal preserver has O(n^(5/6)p^(1/2)) edges in its full range
OpenDistancePreserver934.Exact.Supplement.theorem_5additive-spannersdistance-preserversgraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
There is an absolute such that every -vertex undirected unweighted graph , technical unordered demand set of size , and inclusion-minimal preserver containing mutually edge-disjoint shortest paths for the demands satisfy
This bounds every admissible , rather than asserting existence of a specially chosen sparse one. No connectedness, regularity or shortest-path uniqueness is assumed. Empty graphs remain included. This companion theorem is separate from the proof of Theorem 1.
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 theorem_5 :
∃ C : ℝ, 0 < C ∧ ∀ {V : Type} [Fintype V]
(G H : SimpleGraph V) (P : Finset (Sym2 V))
(_π : EdgeDisjointFamily H P),
IsDemandSet G P → IsMinimalPreserver G H P →
(Fintype.card V : ℝ) ^ ((2 : ℝ) / 3) ≤ (P.card : ℝ) →
P.card ≤ Fintype.card V →
(numEdges H : ℝ) ≤ C * (Fintype.card V : ℝ) ^ ((5 : ℝ) / 6) *
(P.card : ℝ) ^ ((1 : ℝ) / 2)
:= 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; Theorem 5, printed p. 9 (PDF p. 10)