graph_lly_curvature_le_of_lipschitz_cut_potential
Kantorovich-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), κ_LLY(x,y) ≤ (d − A_x + A_y)/d, where A_z is the average of f over the neighbourhood of z.
Statement
theorem graph_lly_curvature_le_of_lipschitz_cut_potential {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) (f : V → ℝ) (hf : ∀ a b : V, f a - f b ≤ (G.dist a b : ℝ)) (hval : f x - f y = (G.dist x y : ℝ)) : graph_lly_curvature G x y ≤ ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ)
- Source
- step towards exists_dist_three_lly_curvature_le_cut
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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_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_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…
- graph_degree_pos_of_connected_of_neIn a connected graph, a vertex x with some other vertex y has positive degree.
- 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_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- graph_idle_measure_nonnegμ_x^α is nonnegative for 0 ≤ α ≤ 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 1
- exists_dist_three_lly_curvature_le_cut_interiorIf x lies in the interior of X (all its neighbours in X) and y in the interior of Xᶜ, and d(x,y) = 3, then κ_LLY(x,y) ≤ 2·|E(X,Xᶜ)| / (3…
The proof, explained
To bound the Lin–Lu–Yau curvature κ_LLY(x, y) from above, we first express the expectation of any function under the idle random walk measure m_z^α as a convex combination α * f(z) + (1 - α) * A_z of its value at z and its neighborhood average A_z. By Kantorovich duality, the Wasserstein distance between the idle measures at x and y is bounded below by the difference in these expectations for the 1-Lipschitz potential f. This translates into an upper bound on the Ollivier curvature ratio κ_O(α, x, y) / (1 - α) for all α ∈ [0, 1), and taking the limit as α → 1⁻ yields the Kantorovich bound on κ_LLY(x, y).
The distance between x and y is strictly positive, and both x and y have positive degree.
Because G is connected and x ≠ y, the distance between x and y is strictly positive (from hG.pos_dist_of_ne). Furthermore, in any connected graph with at least two vertices, both vertices have strictly positive degree (graph_degree_pos_of_connected_of_ne).
uses
graph_degree_pos_of_connected_of_nehave hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy have hdx : 0 < G.degree x := graph_degree_pos_of_connected_of_ne G hG x y hxy have hdy : 0 < G.degree y := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm
For any vertex z of positive degree and any α ∈ ℝ, the expectation of f under the idle measure at z is α * f(z) + (1 - α) * A_z, where A_z is the average of f over the neighbors of z.
We isolate the vertex z from the sum over all vertices using Finset.add_sum_erase. At z, the idle measure evaluates to α, giving α * f(z). For each a ≠ z, the idle measure evaluates to (1 - α) / deg(z) if a is adjacent to z, and 0 otherwise. Factoring (1 - α) / deg(z) out of the sum over a ≠ z (Finset.mul_sum), the remaining sum consists of f(a) for all a ≠ z adjacent to z. Since simple graphs have no self-loops (SimpleGraph.irrefl), z is never adjacent to itself, so this sum equals the sum of f over all neighbors of z. Denominators are then cleared with field_simp.
uses
Finset.add_sum_erase,Finset.mem_univ,Finset.sum_congr,Finset.mem_erase.mp,Finset.mul_sum,mul_comm,Finset.sum_filter,SimpleGraph.neighborFinset_eq_filter,SimpleGraph.irrefl,if_false,zero_addhave sumid : ∀ (z : V), 0 < G.degree z → ∀ α : ℝ, ∑ a, f a * graph_idle_measure G α z a = α * f z + (1 - α) * ((∑ a ∈ G.neighborFinset z, f a) / (G.degree z : ℝ)) := by intro z hz α have hd_ne : (G.degree z : ℝ) ≠ 0 := by positivity have step1 : ∑ a, f a * graph_idle_measure G α z a = f z * α + ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0) := by rw [← Finset.add_sum_erase Finset.univ (fun a => f a * graph_idle_measure G α z a) (Finset.mem_univ z)] congr 1 · simp [graph_idle_measure] · apply Finset.sum_congr rfl intro a ha have haz : a ≠ z := (Finset.mem_erase.mp ha).1 simp [graph_idle_measure, haz] have step2 : ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0) = (1 - α) / (G.degree z : ℝ) * ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro a ha by_cases h : G.Adj z a <;> simp [h, mul_comm] have step3 : ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by have h1 : ∑ a, (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by rw [← Finset.sum_filter, SimpleGraph.neighborFinset_eq_filter] have h2 : (if G.Adj z z then f z else 0) + ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) = ∑ a, (if G.Adj z a then f a else 0) := Finset.add_sum_erase Finset.univ (fun a => if G.Adj z a then f a else 0) (Finset.mem_univ z) rw [← h2] at h1 simp only [SimpleGraph.irrefl, if_false, zero_add] at h1 exact h1 rw [step1, step2, step3] field_simp
For every α ∈ [0, 1), the Ollivier curvature ratio satisfies κ_O(α, x, y) / (1 - α) ≤ (d(x, y) - A_x + A_y) / d(x, y).
For α ∈ [0, 1), the idle measures at x and y are non-negative (graph_idle_measure_nonneg) and sum to 1 (graph_idle_measure_sum_eq_one). By Kantorovich duality (graph_wasserstein_dist_ge_of_lipschitz), the Wasserstein distance W₁ is bounded below by the difference between the expectations of the 1-Lipschitz function f. Using the expectation formula sumid and the condition f(x) - f(y) = d(x, y), this gives W₁ ≥ d(x, y) - (1 - α) * (d(x, y) - A_x + A_y). Unfolding the definition of Ollivier curvature κ_O(α) = 1 - W₁ / d(x, y) and cross-multiplying denominators with div_le_div_iff₀, this lower bound on W₁ is equivalent to the desired upper bound on the curvature ratio.
uses
graph_idle_measure_nonneg,graph_idle_measure_sum_eq_one,graph_wasserstein_dist_ge_of_lipschitz,div_le_div_iff₀have key : ∀ α : ℝ, 0 ≤ α → α < 1 → graph_ollivier_curvature G α x y / (1 - α) ≤ ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ) := by intro α hα0 hα1 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 hW := graph_wasserstein_dist_ge_of_lipschitz G (graph_idle_measure G α x) (graph_idle_measure G α y) hnx hny hsx hsy f hf rw [sumid x hdx α, sumid y hdy α] at hW have hWlow : (G.dist x y : ℝ) - (1 - α) * ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) ≤ graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by nlinarith [hW, hval] unfold graph_ollivier_curvature rw [div_le_div_iff₀ h1α hd] have hsimp : (1 - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) / (G.dist x 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 rw [hsimp] nlinarith [hWlow]
The Lin–Lu–Yau curvature κ_LLY(x, y) is at most (d(x, y) - A_x + A_y) / d(x, y).
The Lin–Lu–Yau curvature is defined as the limit of κ_O(α, x, y) / (1 - α) as α → 1⁻ (graph_lly_curvature_tendsto). Since the upper bound holds for all α in the open interval (0, 1) (Ioo_mem_nhdsLT), passing to the limit preserves the non-strict inequality (le_of_tendsto).
uses
le_of_tendsto,graph_lly_curvature_tendsto,Ioo_mem_nhdsLTapply le_of_tendsto (graph_lly_curvature_tendsto G hG x y hxy) filter_upwards [Ioo_mem_nhdsLT (show (0 : ℝ) < 1 by norm_num)] with α hα exact key α hα.1.le hα.2
graph_degree_pos_of_connected_of_ne- in a connected graph with at least two vertices, every vertex has strictly positive degree
Finset.add_sum_erase- a sum over a finite set can be decomposed as the term at a chosen element plus the sum over the remaining elements
Finset.mem_univ- every element of a finite type belongs to the universal finset
Finset.sum_congr- two sums are equal if their index sets are equal and their summands agree on each element
Finset.mem_erase.mp- membership in an erased set implies distinctness from the erased element
Finset.mul_sum- multiplication by a constant distributes over a finite sum
mul_comm- multiplication is commutative
Finset.sum_filter- a sum over a filtered subset equals the sum over the ambient set with an indicator function
SimpleGraph.neighborFinset_eq_filter- the neighbor set of a vertex is the finset of all vertices adjacent to it
SimpleGraph.irrefl- in a simple graph, no vertex is adjacent to itself (no self-loops)
if_false- an if-expression with a false condition evaluates to its else branch
zero_add- zero plus any element equals that element
graph_idle_measure_nonneg- the idle random walk measure assigns non-negative values to all vertices when α is in [0, 1]
graph_idle_measure_sum_eq_one- the idle random walk measure sums to 1 when the vertex has positive degree
graph_wasserstein_dist_ge_of_lipschitz- Kantorovich duality: the Wasserstein distance between probability measures is bounded below by the difference between expectations of any 1-Lipschitz function
div_le_div_iff₀- for positive denominators, a / b ≤ c / d is equivalent to a * d ≤ c * b
le_of_tendsto- if a function converges to a limit and is eventually bounded above by b, its limit is at most b
graph_lly_curvature_tendsto- the Ollivier curvature ratio κ_O(α) / (1 - α) tends to the Lin–Lu–Yau curvature as α approaches 1 from the left
Ioo_mem_nhdsLT- the open interval (a, b) is a neighborhood of b in the left-half-line topology when a < b
- The algebraic rearrangements between the lower bound on the Wasserstein distance and the upper bound on the Ollivier curvature ratio (lines 62 and 69) are carried out by the non-linear arithmetic tactic `nlinarith`.
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.
/-- Kantorovich-duality (1-Lipschitz potential) upper bound for the Lin–Lu–Yau curvature at a pair of distinct vertices. -/theorem graph_lly_curvature_le_of_lipschitz_cut_potential {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) (f : V → ℝ) (hf : ∀ a b : V, f a - f b ≤ (G.dist a b : ℝ)) (hval : f x - f y = (G.dist x y : ℝ)) : graph_lly_curvature G x y ≤ ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ) := by have hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy have hdx : 0 < G.degree x := graph_degree_pos_of_connected_of_ne G hG x y hxy have hdy : 0 < G.degree y := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm have sumid : ∀ (z : V), 0 < G.degree z → ∀ α : ℝ, ∑ a, f a * graph_idle_measure G α z a = α * f z + (1 - α) * ((∑ a ∈ G.neighborFinset z, f a) / (G.degree z : ℝ)) := by intro z hz α have hd_ne : (G.degree z : ℝ) ≠ 0 := by positivity have step1 : ∑ a, f a * graph_idle_measure G α z a = f z * α + ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0) := by rw [← Finset.add_sum_erase Finset.univ (fun a => f a * graph_idle_measure G α z a) (Finset.mem_univ z)] congr 1 · simp [graph_idle_measure] · apply Finset.sum_congr rfl intro a ha have haz : a ≠ z := (Finset.mem_erase.mp ha).1 simp [graph_idle_measure, haz] have step2 : ∑ a ∈ (Finset.univ.erase z), f a * (if G.Adj z a then (1 - α) / (G.degree z : ℝ) else 0) = (1 - α) / (G.degree z : ℝ) * ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro a ha by_cases h : G.Adj z a <;> simp [h, mul_comm] have step3 : ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by have h1 : ∑ a, (if G.Adj z a then f a else 0) = ∑ a ∈ G.neighborFinset z, f a := by rw [← Finset.sum_filter, SimpleGraph.neighborFinset_eq_filter] have h2 : (if G.Adj z z then f z else 0) + ∑ a ∈ (Finset.univ.erase z), (if G.Adj z a then f a else 0) = ∑ a, (if G.Adj z a then f a else 0) := Finset.add_sum_erase Finset.univ (fun a => if G.Adj z a then f a else 0) (Finset.mem_univ z) rw [← h2] at h1 simp only [SimpleGraph.irrefl, if_false, zero_add] at h1 exact h1 rw [step1, step2, step3] field_simp have key : ∀ α : ℝ, 0 ≤ α → α < 1 → graph_ollivier_curvature G α x y / (1 - α) ≤ ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) / (G.dist x y : ℝ) := by intro α hα0 hα1 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 hW := graph_wasserstein_dist_ge_of_lipschitz G (graph_idle_measure G α x) (graph_idle_measure G α y) hnx hny hsx hsy f hf rw [sumid x hdx α, sumid y hdy α] at hW have hWlow : (G.dist x y : ℝ) - (1 - α) * ((G.dist x y : ℝ) - (∑ a ∈ G.neighborFinset x, f a) / (G.degree x : ℝ) + (∑ b ∈ G.neighborFinset y, f b) / (G.degree y : ℝ)) ≤ graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by nlinarith [hW, hval] unfold graph_ollivier_curvature rw [div_le_div_iff₀ h1α hd] have hsimp : (1 - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) / (G.dist x 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 rw [hsimp] nlinarith [hWlow] apply le_of_tendsto (graph_lly_curvature_tendsto G hG x y hxy) filter_upwards [Ioo_mem_nhdsLT (show (0 : ℝ) < 1 by norm_num)] with α hα exact key α hα.1.le hα.2