Theorem 2 — every -pivot -hop -stretch ADO needs space , improved for
OpenPivotADO.OneHop.Supplement.theorem_2Assume Conjecture 1 (the constant-degree Erdős girth conjecture). Fix a real and an integer . Then there are constants and such that for every threshold there are and a simple graph on vertices with maximum degree at most and edges, , with the following property: for every integer and every -pivot -hop -stretch ADO for (Definition 3),
and, if , moreover
In words: on these constant-degree sparse graphs every such oracle requires space, and for it requires space. The constants depend only on and , and the graph does not depend on or on the oracle.
This extends the one-hop lower bound of the mission's goal (Theorem 1) to oracles that answer a query with up to stored hops through intermediate vertices. For the goal gives a stronger bound.
Differences from the source:
- encoding: constant-degree graphs with m = Θ(n) edges and an Ω(·) space bound, for arbitrarily large n → explicit Δ ∈ ℕ and a, b, κ > 0 chosen before the threshold N, then n ≥ N and G with maximum degree ≤ Δ, a·n ≤ m ≤ b·n, and the division-free inequality κ·m^e ≤ r²·(log n)^{6−4/β}·|E_H|; reason: this is the meaning of the asymptotic notation with constants depending on k and β only
- encoding: both conclusions for the same family of graphs → one conjunction with one κ; reason: a single κ (the smaller of the two) covers both bounds, so no instance changes
- encoding: log of unspecified base → natural logarithm Real.log, with the real exponent 6 − 4/β taken as a real power; reason: a change of base is absorbed in κ
- encoding: n-vertex graph with ℝ-valued distances and stored weights → SimpleGraph on Fin n, distances and stored weights in [0, ∞] (stored edges of weight ∞ allowed and counted); reason: Lean convention; no instance changes
import Definitions.Def_PivotADO_OneHop_Conjecture import Definitions.Def_PivotADO_OneHop_Supplement_HopOracle set_option autoImplicit false open scoped Classical
namespace PivotADO.OneHop.Supplement
open PivotADO.OneHop
/-- Theorem 2, Kadria–Roditty, STOC 2027 submission #584 (October 2026), p.20 (PDF 21).
All constants precede `n` and `G`; the same graph works for every `r ≥ 1` and every
r-pivot β-hop k-stretch ADO. Both conclusions (the general bound and the improved bound
for `β = 2`) hold on the same graph. The open constant-degree girth conjecture is an
explicit hypothesis. -/
theorem theorem_2 (hconj : ConstantDegreeGirthConjecture) :
∀ k : ℝ, 1 ≤ k → ∀ β : ℕ, 1 ≤ β → ∃ (Δ : ℕ) (a b κ : ℝ),
0 < a ∧ 0 < b ∧ 0 < κ ∧
∀ N : ℕ, ∃ (n : ℕ) (G : SimpleGraph (Fin n)),
N ≤ n ∧ (∀ v, G.degree v ≤ Δ) ∧
a * (n : ℝ) ≤ (edgeCount G : ℝ) ∧ (edgeCount G : ℝ) ≤ b * (n : ℝ) ∧
∀ r : ℕ, 1 ≤ r → ∀ O : HopOracle G r β k,
κ * (edgeCount G : ℝ) ^ (1 + 2 / ((β : ℝ) * (k + 1))) ≤
(r : ℝ) ^ 2 * Real.log (n : ℝ) ^ (6 - 4 / (β : ℝ)) *
(edgeCount O.storage.graph : ℝ) ∧
(β = 2 →
κ * (edgeCount G : ℝ) ^ (1 + 1 / (k + 1)) ≤
(r : ℝ) ^ 2 * Real.log (n : ℝ) ^ 3 * Real.log ((r : ℝ) + 1) *
(edgeCount O.storage.graph : ℝ)) := by sorry
end PivotADO.OneHop.Supplement