graph_wasserstein_dist
def
The Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with row sums μ and column sums ν, of the cost Σ_{a,b} d(a,b) π(a,b), d the graph distance.
Statement
noncomputable def graph_wasserstein_dist {V : Type*} [Fintype V] (G : SimpleGraph V) (μ ν : V → ℝ) : ℝ
- Defined in
- arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Definition 2.1 (Wasserstein distance); finite vertex set, plans written as nonnegative functions V → V → ℝ (for probability measures they take values in [0,1] as in the paper).
- Verified
- 10 Oct 2026
- Axioms
- none listed
- Used by 24
- lly_five_vertex_pos_of_min_degree_twoEvery connected graph on 5 vertices with minimum degree at least 2 has positive Lin–Lu–Yau curvature on every edge.
- 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.
- graph_ollivier_curvature_div_le_two_div_distIn a finite connected graph, for x ≠ y and α ∈ [0, 1), κ_α(x, y)/(1 − α) ≤ 2/d(x, 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,…
- lly_curvature_pos_of_edge_connectivity_geIf a finite connected graph on n vertices has edge-connectivity κ'(G) ≥ 2n/3 − 1, then every edge xy has κ_LLY(x, y) > 0.
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- 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 *…
- graph_wasserstein_dist_ge_of_forall_planA lower bound on the cost of every transport plan between two probability measures is a lower bound on their Wasserstein distance.
- graph_lly_curvature_commThe Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
- graph_wasserstein_dist_le_of_planThe Wasserstein distance is at most the cost of any transport plan.
- graph_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
- lly_five_vertex_t_star_curvatureFor the tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2 one has κ_LLY(0,1) = −1/3.
- graph_wasserstein_dist_ge_of_lipschitzWeak Kantorovich duality: for probability measures μ, ν and any function f with f(a) − f(b) ≤ d(a, b), Σ f μ − Σ f ν ≤ W(μ, ν).
- graph_lly_curvature_le_of_lipschitz_cut_potentialKantorovich-duality bound on the Lin–Lu–Yau curvature at a pair: for x ≠ y and any 1-Lipschitz potential f with f(x) − f(y) = d(x,y),…
- 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_commThe Wasserstein distance is symmetric: W(μ, ν) = W(ν, μ).
- five_vertex_t_star_wasserstein_geFor the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α +…
- 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_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
- graph_lly_curvature_pos_of_wasserstein_lt_oneIf the Wasserstein distance between the lazy random-walk measures μ_x^α and μ_y^α on an edge xy is strictly less than 1 for some α ∈ (0,…
- graph_wasserstein_dist_self_eq_zeroThe Wasserstein distance from a nonnegative measure to itself is 0.
Lean source view module on GitHub
/-- Wasserstein (earth mover's) distance between `μ` and `ν` on a finite graph, with the graph distance as cost. -/ noncomputable def graph_wasserstein_dist {V : Type*} [Fintype V] (G : SimpleGraph V) (μ ν : V → ℝ) : ℝ := sInf {c | ∃ π : V → V → ℝ, (∀ a b, 0 ≤ π a b) ∧ (∀ a, ∑ b, π a b = μ a) ∧ (∀ b, ∑ a, π a b = ν b) ∧ c = ∑ a, ∑ b, (G.dist a b : ℝ) * π a b}