Lemma 2.4 — subset betweenness reduction: whp
ProvedBFAlmostLinear.lemma_2_4graph-algorithmsnegative-weightsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-algorithmsshortest-paths
Let be a weighted graph on vertices with frozen flags, a set of vertices, , and hop bounds . Let contain each vertex of independently with probability . For every there is (independent of the graph) such that with probability at least over the following holds: for every integer , all with , and every potential that fixes ,
This is the subset betweenness reduction guarantee that Lemma 2.2 bootstraps.
Differences from the source:
- generalization: one hop bound → a pair ; reason: Lemma 4.6's proof (p.18) applies §2 to ; is the printed form.
- generalization: the negative vertices → any set of vertices; reason: the proof uses only that is sampled from .
- encoding: "with high probability" → for every there is with probability ; reason: footnote 2, p.1.
- encoding: → ; reason: Lean form of the .
- encoding: the frozen-flag convention → hypothesis that every arc of negative weight is flagged; reason: §1.1 counts all negative edges as hops.
Preamble
import Mathlib import Definitions.Def_BFAlmostLinear_WGraph import Definitions.Def_BFAlmostLinear_sampleMass
Formal statement
namespace BFAlmostLinear
open Classical in
/-- **Lemma 2.4**, p.7. "With high probability over the randomness of U, the following holds for all integers
ℓ ∈ [n] and all subsets S, T ⊆ V with |S| = |T| = ℓ: for any potential function ϕ that fixes U, the set
R_ϕ = {r : X_ϕ[S, r, T] ≠ ∅} has size at most O(bℓ log n)."
Hair, Li, Li, Zhang, *Bellman-Ford in Almost-Linear Time*, STOC 2027 submission (manuscript sha256
873b9acb…), Lemma 2.4, p.7, with the sample of Lemma 2.2, p.6: "U ⊆ N … each vertex in N is sampled with
probability 1/b".
**Formalization Note.**
* "With high probability" is `∀ c > 0`, a probability at least `1 − n^{−c}`, with `K` chosen after `c`.
* Generalized to a hop pair `(h₁, h₂)`; the printed form is `h₁ = h₂ = h`. `N` is any set of vertices. `b ≥ 1` is a real.
* No lower bound on `n` is needed: for `n ≤ 1` the probability bound `1 − n^{−c}` is at most `0`. -/
theorem lemma_2_4 :
∀ c : ℝ, 0 < c → ∃ K : ℝ, 0 < K ∧
∀ (V E : Type) [Fintype V] [Fintype E] (G : WGraph V E) (N : Finset V) (b : ℝ) (h₁ h₂ : ℕ),
G.Frozen → 1 ≤ b →
1 - (Fintype.card V : ℝ) ^ (-c) ≤
goodMass N b fun U =>
∀ ℓ : ℕ, 1 ≤ ℓ → ℓ ≤ Fintype.card V → ∀ S T : Finset V, S.card = ℓ → T.card = ℓ →
∀ ϕ : V → ℝ, G.Fixes h₁ h₂ U ϕ →
(((N.filter fun r => ∃ s ∈ S, ∃ t ∈ T, G.InX h₁ h₂ ϕ s r t).card : ℕ) : ℝ) ≤
K * b * ℓ * Real.log (Fintype.card V) := by sorry
end BFAlmostLinear
Source
Hair, Li, Li, Zhang, Bellman-Ford in Almost-Linear Time, STOC 2027 submission (manuscript sha256 873b9acb…), Lemma 2.4, p.7, with the sample of Lemma 2.2, p.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.