Lemma 21, p. 809 — restricted distance from a large vertex set
ProvedLeightonRao.ShortPaths.lemma_21graph-distancep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1short-path-flowsparsest-cut
Let be a connected capacitated graph on vertices, with uniform sparsest cut value and maximum incident capacity . Let be a nonnegative symmetric distance function of total weight , and let contain at least vertices. If is a real number satisfying , then, with distances restricted to paths of at most edges,
In particular, all restricted distances in this sum are finite. The estimate links the large component to vertices outside it.
Formalization Note The logarithm in the hypothesis is natural , while other bounds in the paper use base-two . Restricted distances take values in the extended nonnegative reals.
Preamble
import Mathlib import Definitions.Def_LeightonRao_ShortPaths_Setting
Formal statement
namespace LeightonRao.ShortPaths
/-- Lemma 21, p. 809. The length `L` is real, as on the page; `d(T, u)` uses walks with at most
`L / 4` edges. The restricted distances are extended nonnegative reals. -/
theorem lemma_21 {V : Type} [Fintype V] [DecidableEq V]
(N : Network V) (hn : 2 ≤ Fintype.card V) (hconn : IsConnectedNet N)
(d : V → V → ℝ) (hd : IsDistanceFunction d)
(L : ℝ)
(hL : 12 * cmax N * Real.log (Fintype.card V : ℝ) /
((Fintype.card V : ℝ) * minCut N) ≤ L)
(T : Finset V)
(hT : 2 * (Fintype.card V : ℝ) ≤ 3 * (T.card : ℝ)) :
∑ u ∈ Tᶜ, distFromL N d (L / 4) T u ≤
ENNReal.ofReal (6 * totalWeight N d /
((Fintype.card V : ℝ) * minCut N)) := by sorry
end LeightonRao.ShortPaths
Source
Leighton and Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM 46 (1999), p. 809, Lemma 21
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.