Corollary 3.12 — a star topology costs at most
ProvedLNTopology.StarBound.corollary_3_12Let be a finite set of nodes, a channel cost function satisfying (MO), (SY), (CI) and (SA), and a payment flow with . For every hub , the star centered at (each node has a single channel, to , carrying its flow ) satisfies
where is the minimal cost of a Lightning Network on that supports .
The star is the natural candidate for a cost-minimal topology; Corollary 3.11 shows it is generally not optimal, and this corollary shows that it is never worse than optimal by more than a factor of two, for every cost function satisfying the axioms.
Formalization Note. The bound is stated for every hub, matching the paper's sentence "the star topology is at most twice as costly as the minimum"; the paper's proof uses one particular hub. is an infimum over Lightning Networks on the same node set (the paper's "min" need not be attained when is discontinuous). The hypothesis is the model's standing identity (§2, p. 4) and is required: without it is a junk value. (SA) is in its corrected form, for all (the printed range is unsatisfiable, which would make the statement vacuous).
import Mathlib import Definitions.Def_LNTopology_StarBound_Model import Definitions.Def_LNTopology_StarBound_MinCost import Definitions.Def_LNTopology_Local_Star
namespace LNTopology.StarBound
/-- Corollary 3.12, p. 9: for any flow `f` (with `∑ i, f i = 0`), the LNTopology.Local.star centered at any hub
costs at most twice the minimal cost of a Lightning Network supporting `f`. -/
theorem corollary_3_12 {V : Type*} [Fintype V] [DecidableEq V] (c : ℝ → ℝ)
(hc : IsChannelCost c) (f : V → ℝ) (hf : ∑ i, f i = 0) (h : V) :
cost c (LNTopology.Local.star f h) ≤ 2 * cmin c f := by sorry
end LNTopology.StarBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.