Proposition 3.4, p. 406 — the support graph of an extremal point of U(a, b) has no cycles; P has at most n + m − 1 nonzero entries
ProvedCompOT.Vertices.proposition_3_4Proposition 3.4 (Extremal solutions). Let , be histograms, and let be an extremal point of the transportation polytope
Let be the set of edges , , , with . Then the graph on the nodes , has no cycles. In particular,
The vertices of are therefore sparse: their supports are forests of the complete bipartite graph between sources and targets. Since a linear program over attains its minimum at a vertex, optimal transport plans can be sought among such sparse matrices; this is the structure exploited by the network simplex and the north-west corner rule.
Formalization Note Indices are Fin n, Fin m. Extremality is the book's midpoint definition relative to . "No cycles" is SimpleGraph.IsAcyclic of the undirected bipartite support graph. The simplex hypotheses come from the book's standing notation (p. 360) and imply nonempty index sets. Thus natural-number subtraction in agrees with the book's integer expression.
import Mathlib import Definitions.Def_CompOT_Vertices_Defs
namespace CompOT.Vertices
/-- Proposition 3.4 (Extremal solutions), p. 406: for the book's histograms
`a ∈ Σₙ`, `b ∈ Σₘ` (Notation, p. 360), if `P` is an extremal point of `U(a, b)`,
then its support graph has no cycles and `P` has at most `n + m − 1` nonzero entries. -/
theorem proposition_3_4 {n m : ℕ} (a : Fin n → ℝ) (b : Fin m → ℝ)
(P : Matrix (Fin n) (Fin m) ℝ)
(ha : a ∈ stdSimplex ℝ (Fin n)) (hb : b ∈ stdSimplex ℝ (Fin m))
(hP : IsExtremal (CompOT.Assignment.couplings a b) P) :
(supportGraph P).IsAcyclic ∧ (nonzeroEntries P).card ≤ n + m - 1 := by sorry
end CompOT.Vertices
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.