Corollary 3.3, p. 6 — a cost-minimizing Lightning Network is bipartite, with all net flows from A to B
ProvedLNTopology.Local.corollary_3_3Let be a channel cost function satisfying (MO), (SY), (CI) and (SA), and let be a Lightning Network on a finite node set that is cost-minimizing for a payment flow . Then there is a set , with complement , such that
- the channel graph of — nodes , an edge between and whenever — is bipartite with parts and ; and
- every net flow goes from to :
This is the structural conclusion of §3.1: in a cost-minimizing Lightning Network, the nodes split into pure senders and pure receivers, and every channel joins a sender to a receiver.
Formalization Note The bipartite clause uses Mathlib's SimpleGraph.IsBipartiteWith A Aᶜ on SimpleGraph.fromRel (fun a b => Λ a b ≠ 0). The flow-direction clause is the stronger content and is stated separately. The statement is conditional: it does not claim that a cost-minimizing network exists. (SA) is used in the corrected form for all (the printed range is unsatisfiable). Cost-minimizing compares with networks on the same node set.
import Mathlib import Definitions.Def_LNTopology_Local_Model
namespace LNTopology.Local
/-- Corollary 3.3 (SSRN 4439190, p. 6; proof p. 10): a cost-minimizing Lightning Network is a
bipartite graph with parts `A` and `B = Aᶜ` in which every net flow goes from `A` to `B`. -/
theorem corollary_3_3 {V : Type*} [Fintype V] (c : ℝ → ℝ) (hc : IsChannelCost c)
(f : V → ℝ) (Λ : V → V → ℝ) (hmin : IsCostMinimizing c f Λ) :
∃ A : Set V, (SimpleGraph.fromRel (fun a b => Λ a b ≠ 0)).IsBipartiteWith A Aᶜ ∧
∀ i j, 0 < Λ i j → i ∈ A ∧ j ∉ A := by sorry
end LNTopology.Local
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.