graph_ollivier_curvature_div_le_two_div_dist
In a finite connected graph, for x ≠ y and α ∈ [0, 1), κ_α(x, y)/(1 − α) ≤ 2/d(x, y).
Statement
theorem graph_ollivier_curvature_div_le_two_div_dist {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α < 1) : graph_ollivier_curvature G α x y / (1 - α) ≤ 2 / (G.dist x y : ℝ)
- Source
- Helper for graph_lly_curvature_le_two_div_dist (OP-164, arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature)).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_degree_pos_of_connected_of_neIn a connected graph, a vertex x with some other vertex y has positive degree.
- graph_idle_measure_nonnegμ_x^α is nonnegative for 0 ≤ α ≤ 1.
- graph_idle_measure_sum_eq_oneμ_x^α is a probability measure (total mass 1) when x has a neighbour.
- graph_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
- graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- graph_idle_measureThe lazy random-walk measure μ_x^α at x with idleness α: mass α at x, (1 − α)/d_x at each neighbour of x, 0 elsewhere.
- 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].
- Used by 2
- graph_lly_curvature_le_two_div_distFor distinct vertices x, y of a finite connected graph, κ_LLY(x, y) ≤ 2/d(x, y).
- graph_lly_curvature_tendstoIn a finite connected graph, for x ≠ y, κ_α(x, y)/(1 − α) converges as α → 1⁻, to κ_LLY(x, y): the limit in the definition of the…
The proof, explained
To bound the normalized Ollivier-Ricci curvature κ_α(x, y)/(1 - α) ≤ 2/d(x, y), it suffices to establish a lower bound on the Wasserstein distance W₁(μ_x, μ_y) between the idle random walk measures. By Kantorovich duality applied to the 1-Lipschitz test function f(v) = d(v, y), the Wasserstein distance is at least the difference of expectations 𝔼_{μ_x}[f] - 𝔼_{μ_y}[f]. Evaluating directly yields 𝔼_{μ_y}[f] = 1 - α, while the triangle inequality yields 𝔼_{μ_x}[f] ≥ d(x, y) - (1 - α). Subtracting these gives W₁(μ_x, μ_y) ≥ d(x, y) - 2(1 - α), which algebraically rearranges to the desired curvature bound.
The graph distance d(x, y) and degrees deg(x), deg(y) are strictly positive, 1 - α > 0, and the idle measures μ_x and μ_y are valid probability measures (non-negative and summing to 1).
Because G is connected and x ≠ y, the distance d(x, y) is strictly positive (via hG.pos_dist_of_ne) and both vertices have degree at least 1 (graph_degree_pos_of_connected_of_ne). The condition α < 1 implies 1 - α > 0. For α ∈ [0, 1), the idle measure μ_x, which places mass α on x and (1 - α) / deg(x) on each neighbor, is non-negative everywhere (graph_idle_measure_nonneg) and sums to 1 (graph_idle_measure_sum_eq_one), and similarly for μ_y.
uses
hG.pos_dist_of_ne,graph_degree_pos_of_connected_of_ne,graph_idle_measure_nonneg,graph_idle_measure_sum_eq_onehave hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy have hdx := graph_degree_pos_of_connected_of_ne G hG x y hxy have hdy := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm have h1α : 0 < 1 - α := by linarith have hnx := graph_idle_measure_nonneg G α hα0 hα1.le x have hny := graph_idle_measure_nonneg G α hα0 hα1.le y have hsx := graph_idle_measure_sum_eq_one G α x hdx have hsy := graph_idle_measure_sum_eq_one G α y hdy
The distance-to-y function v ↦ d(v, y) is 1-Lipschitz: d(a, y) - d(b, y) ≤ d(a, b) for all vertices a, b.
For any two vertices a and b, the graph triangle inequality (hG.dist_triangle) gives d(a, y) ≤ d(a, b) + d(b, y). Subtracting d(b, y) from both sides yields the 1-Lipschitz condition d(a, y) - d(b, y) ≤ d(a, b).
uses
hG.dist_trianglehave hf : ∀ a b, (fun v => (G.dist v y : ℝ)) a - (fun v => (G.dist v y : ℝ)) b ≤ G.dist a b := by intro a b have := hG.dist_triangle (u := a) (v := b) (w := y) simp only have : (G.dist a y : ℝ) ≤ G.dist a b + G.dist b y := by exact_mod_cast this linarith
The Wasserstein distance W₁(μ_x, μ_y) is bounded below by the difference of expectations ∑_a d(a, y) μ_x(a) - ∑_b d(b, y) μ_y(b).
By Kantorovich-Rubinstein duality for graph Wasserstein distance (graph_wasserstein_dist_ge_of_lipschitz), W₁(μ_x, μ_y) is bounded below by the difference of expectations of any 1-Lipschitz test function. Applying this duality to the 1-Lipschitz function v ↦ d(v, y) gives the inequality.
uses
graph_wasserstein_dist_ge_of_lipschitzhave hW := graph_wasserstein_dist_ge_of_lipschitz G _ _ hnx hny hsx hsy _ hfThe expectation of the distance to y under the idle measure at x satisfies ∑_a d(a, y) μ_x(a) ≥ d(x, y) - 1 + α.
We establish pointwise that ((d(x, y) - 1) + 𝟏_{a = x}) μ_x(a) ≤ d(a, y) μ_x(a) for every vertex a. If a = x, both sides equal d(x, y) μ_x(x). If a ≠ x is a neighbor of x, d(x, a) = 1 (SimpleGraph.dist_eq_one_iff_adj.mpr), so the triangle inequality d(x, y) ≤ 1 + d(a, y) gives d(x, y) - 1 ≤ d(a, y), which after multiplying by μ_x(a) ≥ 0 yields the bound. If a is neither x nor adjacent to x, μ_x(a) = 0 so both sides vanish. Summing over all a in V via Finset.sum_le_sum, distributing sums, and using ∑_a μ_x(a) = 1 and μ_x(x) = α evaluates the left-hand side to (d(x, y) - 1) + α.
uses
if_false,add_zero,mul_le_mul_of_nonneg_right,hG.dist_triangle,SimpleGraph.dist_eq_one_iff_adj.mpr,add_mul,Finset.sum_add_distrib,Finset.mul_sum,ite_mul,one_mul,zero_mul,Finset.sum_ite_eq',Finset.sum_ite_eq,Finset.mem_univ,if_true,Finset.sum_le_sumhave ex : (G.dist x y : ℝ) - 1 + α ≤ ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α x a := by have term : ∀ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a ≤ (G.dist a y : ℝ) * graph_idle_measure G α x a := by intro a by_cases hax : a = x · subst a; simp · simp only [hax, if_false, add_zero] by_cases hadj : G.Adj x a · apply mul_le_mul_of_nonneg_right _ (hnx a) have t := hG.dist_triangle (u := x) (v := a) (w := y) rw [SimpleGraph.dist_eq_one_iff_adj.mpr hadj] at t have : (G.dist x y : ℝ) ≤ 1 + G.dist a y := by exact_mod_cast t linarith · have : graph_idle_measure G α x a = 0 := by simp [graph_idle_measure, hax, hadj] rw [this] simp calc (G.dist x y : ℝ) - 1 + α = ∑ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a := by simp only [add_mul, Finset.sum_add_distrib, ← Finset.mul_sum, hsx, ite_mul, one_mul, zero_mul, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] simp [graph_idle_measure] _ ≤ _ := Finset.sum_le_sum fun a _ => term a
The expectation of the distance to y under the idle measure at y equals 1 - α, that is, ∑_a d(a, y) μ_y(a) = 1 - α.
For each vertex a, d(a, y) μ_y(a) = μ_y(a) - α 𝟏_{a = y}. This is checked by cases: if a = y, d(y, y) = 0 and μ_y(y) - α = α - α = 0; if a is adjacent to y, d(a, y) = 1 (using symmetry SimpleGraph.dist_comm and SimpleGraph.dist_eq_one_iff_adj.mpr); if a is non-adjacent and a ≠ y, μ_y(a) = 0. Summing this equality over all a and splitting the sum with Finset.sum_sub_distrib gives ∑_a μ_y(a) - α = 1 - α.
uses
SimpleGraph.dist_comm,SimpleGraph.dist_eq_one_iff_adj.mpr,Finset.sum_sub_distribhave ey : ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α y a = 1 - α := by have term : ∀ a, (G.dist a y : ℝ) * graph_idle_measure G α y a = graph_idle_measure G α y a - (if a = y then α else 0) := by intro a by_cases hay : a = y · subst a; simp [graph_idle_measure] · by_cases hadj : G.Adj y a · rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj.mpr hadj] simp [hay] · simp [graph_idle_measure, hay, hadj] simp_rw [term] rw [Finset.sum_sub_distrib, hsy] simp
The Wasserstein distance satisfies W₁(μ_x, μ_y) ≥ d(x, y) - 2(1 - α).
Combining the Kantorovich lower bound W₁(μ_x, μ_y) ≥ ∑_a d(a, y) μ_x(a) - ∑_a d(a, y) μ_y(a) with the lower bound d(x, y) - 1 + α on the first expectation and the exact value 1 - α for the second expectation, linear arithmetic (linarith) produces W₁(μ_x, μ_y) ≥ (d(x, y) - 1 + α) - (1 - α) = d(x, y) - 2(1 - α).
have hWlow : (G.dist x y : ℝ) - 2 * (1 - α) ≤ graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by linarith
The normalized Ollivier-Ricci curvature satisfies κ_α(x, y) / (1 - α) ≤ 2 / d(x, y).
By definition, κ_α(x, y) = 1 - W₁(μ_x, μ_y) / d(x, y). Since 1 - α > 0 and d(x, y) > 0, div_le_div_iff₀ translates the inequality κ_α(x, y) / (1 - α) ≤ 2 / d(x, y) into (1 - W₁ / d) * d ≤ 2(1 - α), which simplifies to d(x, y) - W₁ ≤ 2(1 - α). Using field_simp and the lower bound W₁ ≥ d(x, y) - 2(1 - α), non-linear arithmetic (nlinarith) closes the goal.
uses
div_le_div_iff₀unfold graph_ollivier_curvature rw [div_le_div_iff₀ h1α hd] have : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) / (G.dist x y : ℝ) * (G.dist x y : ℝ) = graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by field_simp nlinarith
hG.pos_dist_of_ne- In a connected graph, distinct vertices have strictly positive distance: if x ≠ y then 0 < d(x, y).
graph_degree_pos_of_connected_of_ne- In a connected graph, any vertex distinct from another vertex has degree strictly greater than 0.
graph_idle_measure_nonneg- For α ∈ [0, 1], the idle measure assigns non-negative mass to every vertex.
graph_idle_measure_sum_eq_one- For any vertex with positive degree, the total mass of the idle measure over all vertices is 1.
hG.dist_triangle- In a connected graph, the distance function satisfies the triangle inequality: d(u, w) ≤ d(u, v) + d(v, w).
graph_wasserstein_dist_ge_of_lipschitz- For any 1-Lipschitz function f on a graph and probability measures μ, ν, the Wasserstein distance W₁(μ, ν) is at least ∑ f(a) μ(a) - ∑ f(b) ν(b).
if_false- An if-then-else expression with condition False evaluates to the else branch: (if False then t else e) = e.
add_zero- Adding zero on the right leaves an element unchanged: a + 0 = a.
mul_le_mul_of_nonneg_right- Multiplying both sides of an inequality b ≤ c by a non-negative element a ≥ 0 preserves the inequality: b * a ≤ c * a.
SimpleGraph.dist_eq_one_iff_adj.mpr- Adjacent vertices in a graph are at distance 1 from each other: Adj u v → dist u v = 1.
add_mul- Multiplication distributes over addition from the right: (a + b) * c = a * c + b * c.
Finset.sum_add_distrib- The sum of a sum of functions is the sum of their individual sums: ∑ (f(x) + g(x)) = ∑ f(x) + ∑ g(x).
Finset.mul_sum- Multiplication distributes over finite sums: a * ∑ f(i) = ∑ (a * f(i)).
ite_mul- Multiplication distributes into an if-then-else: (if P then a else b) * c = if P then a * c else b * c.
one_mul- Multiplying by 1 on the left leaves an element unchanged: 1 * a = a.
zero_mul- Multiplying by 0 on the left yields 0: 0 * a = 0.
Finset.sum_ite_eq'- Summing (if x = a then b(x) else 0) over a finite set evaluates to b(a) if a is in the set and 0 otherwise.
Finset.sum_ite_eq- Summing (if a = x then b(x) else 0) over a finite set evaluates to b(a) if a is in the set and 0 otherwise.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
if_true- An if-then-else expression with condition True evaluates to the then branch: (if True then t else e) = t.
Finset.sum_le_sum- If f(i) ≤ g(i) for all indices i in a finite set, then ∑ f(i) ≤ ∑ g(i).
SimpleGraph.dist_comm- Graph distance is symmetric: dist u v = dist v u.
Finset.sum_sub_distrib- The sum of a difference of functions is the difference of their sums: ∑ (f(x) - g(x)) = ∑ f(x) - ∑ g(x).
div_le_div_iff₀- For positive denominators b > 0 and d > 0, a / b ≤ c / d if and only if a * d ≤ c * b.
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_ollivier_curvature_div_le_two_div_dist {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α < 1) : graph_ollivier_curvature G α x y / (1 - α) ≤ 2 / (G.dist x y : ℝ) := by have hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy have hdx := graph_degree_pos_of_connected_of_ne G hG x y hxy have hdy := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm have h1α : 0 < 1 - α := by linarith have hnx := graph_idle_measure_nonneg G α hα0 hα1.le x have hny := graph_idle_measure_nonneg G α hα0 hα1.le y have hsx := graph_idle_measure_sum_eq_one G α x hdx have hsy := graph_idle_measure_sum_eq_one G α y hdy have hf : ∀ a b, (fun v => (G.dist v y : ℝ)) a - (fun v => (G.dist v y : ℝ)) b ≤ G.dist a b := by intro a b have := hG.dist_triangle (u := a) (v := b) (w := y) simp only have : (G.dist a y : ℝ) ≤ G.dist a b + G.dist b y := by exact_mod_cast this linarith have hW := graph_wasserstein_dist_ge_of_lipschitz G _ _ hnx hny hsx hsy _ hf have ex : (G.dist x y : ℝ) - 1 + α ≤ ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α x a := by have term : ∀ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a ≤ (G.dist a y : ℝ) * graph_idle_measure G α x a := by intro a by_cases hax : a = x · subst a; simp · simp only [hax, if_false, add_zero] by_cases hadj : G.Adj x a · apply mul_le_mul_of_nonneg_right _ (hnx a) have t := hG.dist_triangle (u := x) (v := a) (w := y) rw [SimpleGraph.dist_eq_one_iff_adj.mpr hadj] at t have : (G.dist x y : ℝ) ≤ 1 + G.dist a y := by exact_mod_cast t linarith · have : graph_idle_measure G α x a = 0 := by simp [graph_idle_measure, hax, hadj] rw [this] simp calc (G.dist x y : ℝ) - 1 + α = ∑ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a := by simp only [add_mul, Finset.sum_add_distrib, ← Finset.mul_sum, hsx, ite_mul, one_mul, zero_mul, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true] simp [graph_idle_measure] _ ≤ _ := Finset.sum_le_sum fun a _ => term a have ey : ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α y a = 1 - α := by have term : ∀ a, (G.dist a y : ℝ) * graph_idle_measure G α y a = graph_idle_measure G α y a - (if a = y then α else 0) := by intro a by_cases hay : a = y · subst a; simp [graph_idle_measure] · by_cases hadj : G.Adj y a · rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj.mpr hadj] simp [hay] · simp [graph_idle_measure, hay, hadj] simp_rw [term] rw [Finset.sum_sub_distrib, hsy] simp have hWlow : (G.dist x y : ℝ) - 2 * (1 - α) ≤ graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by linarith unfold graph_ollivier_curvature rw [div_le_div_iff₀ h1α hd] have : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) / (G.dist x y : ℝ) * (G.dist x y : ℝ) = graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by field_simp nlinarith