graph_wasserstein_dist_le_of_plan
The Wasserstein distance is at most the cost of any transport plan.
Statement
theorem graph_wasserstein_dist_le_of_plan {V : Type*} [Fintype V] (G : SimpleGraph V) (μ ν : V → ℝ) (π : V → V → ℝ) (hπ : ∀ a b, 0 ≤ π a b) (h1 : ∀ a, ∑ b, π a b = μ a) (h2 : ∀ b, ∑ a, π a b = ν b) : graph_wasserstein_dist G μ ν ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b
- Source
- Helper for the curvature computations of arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature) (upper bounds on W by explicit plans, as in the proof of Lemma 3.2).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- Used by 9
- graph_lly_curvature_of_twinsIf x and y are adjacent and have the same neighbours apart from each other, then κ_LLY(x, y) = (d_x + 1)/d_x.
- not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- graph_lly_curvature_of_leafIf x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
- five_vertex_t_star_wasserstein_leFor the T-graph and α in [2/5, 1], the explicit plan π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3,…
- wasserstein_dist_le_of_diameter_twoOn any graph of diameter at most 2, the Wasserstein distance between probability measures μ and ν with d(x, y) = 1 is bounded by 2 - 2 *…
- five_vertex_min_degree_two_wasserstein_lt_oneEvery connected graph on 5 vertices with minimum degree at least 2 has, for each edge xy, some α ∈ (0, 1) with W(μ_x^α, μ_y^α) < 1.
- graph_wasserstein_dist_mix_dirac_leMixing with point masses: W(tμ + (1−t)δ_x, tν + (1−t)δ_y) ≤ t W(μ, ν) + (1−t) d(x, y) for probability measures μ, ν and t ∈ [0, 1].
- graph_idle_wasserstein_lt_one_of_edge_partitionGiven the edge partition of a graph of diameter at most 2 whose minimum degree is at least 2n/3 − 1, the idleness-1/2 measures at the…
- graph_wasserstein_dist_self_eq_zeroThe Wasserstein distance from a nonnegative measure to itself is 0.
The proof, explained
The graph Wasserstein distance is defined as the infimum of the total transport cost over all valid transport plans between μ and ν. The proof applies `csInf_le`, which states that the infimum of a set bounded below is at most any of its elements. It establishes that 0 is a lower bound because graph distances and plan weights are non-negative, and concludes by observing that the assumed plan π is a valid coupling whose cost belongs to the set.
To show that the Wasserstein distance is at most the transport cost of π, it suffices to show that the set of transport costs is bounded below and that the cost of π is an element of that set.
By definition, the graph Wasserstein distance is the infimum of all transport costs across valid plans coupling μ and ν. By `csInf_le`, the infimum of a non-empty set bounded below is at most any of its elements.
uses
csInf_leapply csInf_leThe set of transport costs is bounded below by 0.
We provide 0 as a candidate lower bound. For any valid coupling p and its associated transport cost c = ∑ a, ∑ b, dist(a, b) * p(a, b), the distances dist(a, b) are non-negative and the weights p(a, b) are non-negative. By `mul_nonneg`, each term in the sum is non-negative, and by `Finset.sum_nonneg`, the double sum of non-negative reals is non-negative. Hence 0 ≤ c.
uses
Finset.sum_nonneg,mul_nonneg· refine ⟨0, ?_⟩ rintro c ⟨p, hp, -, -, rfl⟩ exact Finset.sum_nonneg fun a _ => Finset.sum_nonneg fun b _ => mul_nonneg (by positivity) (hp a b)
The cost of π belongs to the set of transport costs.
The given plan π is non-negative by hπ and has marginals μ and ν by h1 and h2, so its cost is indeed a member of the set of transport costs between μ and ν.
· exact ⟨π, hπ, h1, h2, rfl⟩
csInf_le- In a conditionally complete lattice, the infimum of a set that is bounded below is less than or equal to any element of that set.
Finset.sum_nonneg- A finite sum of non-negative elements is non-negative.
mul_nonneg- The product of two non-negative elements is non-negative.
- The nonnegativity of the graph distance G.dist a b in line 8 is discharged automatically by the `positivity` tactic.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem graph_wasserstein_dist_le_of_plan {V : Type*} [Fintype V] (G : SimpleGraph V) (μ ν : V → ℝ) (π : V → V → ℝ) (hπ : ∀ a b, 0 ≤ π a b) (h1 : ∀ a, ∑ b, π a b = μ a) (h2 : ∀ b, ∑ a, π a b = ν b) : graph_wasserstein_dist G μ ν ≤ ∑ a, ∑ b, (G.dist a b : ℝ) * π a b := by apply csInf_le · refine ⟨0, ?_⟩ rintro c ⟨p, hp, -, -, rfl⟩ exact Finset.sum_nonneg fun a _ => Finset.sum_nonneg fun b _ => mul_nonneg (by positivity) (hp a b) · exact ⟨π, hπ, h1, h2, rfl⟩