graph_lly_curvature_pos_of_wasserstein_lt_one
If the Wasserstein distance between the lazy random-walk measures μ_x^α and μ_y^α on an edge xy is strictly less than 1 for some α ∈ (0, 1), then the Lin–Lu–Yau curvature κ_LLY(x, y) is strictly positive.
Statement
theorem graph_lly_curvature_pos_of_wasserstein_lt_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : G.Adj x y) (α : ℝ) (hα0 : 0 < α) (hα1 : α < 1) (hW : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) < 1) : 0 < graph_lly_curvature G x y
- Source
- step towards lly_curvature_pos_of_edge_connectivity_ge
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- graph_ollivier_curvature_div_monotoneOnIn a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).
- 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_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_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- Used by 2
- 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.
- 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.
The proof, explained
The proof bounds the Lin–Lu–Yau curvature κ_LLY(x, y) from below by the strictly positive normalized Ollivier curvature at laziness parameter α. Because x and y are adjacent, their graph distance is 1, so the Ollivier curvature κ(x, y, α) equals 1 - W(μ_x^α, μ_y^α) > 0, which makes the quotient κ(x, y, α) / (1 - α) strictly positive. Since the function β ↦ κ(x, y, β) / (1 - β) is monotone non-decreasing on (0, 1) and converges to κ_LLY(x, y) as β → 1⁻, this positive quotient at α provides an eventual lower bound near 1 that is preserved in the limit.
The vertices x and y are distinct and the graph distance d(x, y) equals 1.
Because x and y are adjacent in the simple graph G, they are distinct (x ≠ y), and their graph distance is 1 by SimpleGraph.dist_eq_one_iff_adj.mpr. Casting the distance to ℝ also yields 1.
uses
SimpleGraph.dist_eq_one_iff_adj.mprhave hne : x ≠ y := hxy.ne have hdist : G.dist x y = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hxy have hdistR : (G.dist x y : ℝ) = 1 := by rw [hdist]; norm_num
The Ollivier curvature κ(x, y, α) simplifies to 1 - W(μ_x^α, μ_y^α).
Unfolding the definition of Ollivier curvature gives 1 - W(μ_x^α, μ_y^α) / d(x, y). Substituting d(x, y) = 1 eliminates the division, leaving 1 - W(μ_x^α, μ_y^α).
have hcurv : graph_ollivier_curvature G α x y = 1 - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by unfold graph_ollivier_curvature rw [hdistR] simp
The Ollivier curvature κ(x, y, α) and the quotient κ(x, y, α) / (1 - α) are strictly positive.
By assumption, the Wasserstein distance W(μ_x^α, μ_y^α) is strictly less than 1, so 1 - W(μ_x^α, μ_y^α) > 0. Since α < 1, the denominator 1 - α is also strictly positive, so their quotient is strictly positive by div_pos.
uses
div_poshave hposcurv : 0 < graph_ollivier_curvature G α x y := by rw [hcurv]; linarith have hposf : 0 < graph_ollivier_curvature G α x y / (1 - α) := by apply div_pos hposcurv; linarith
The quotient β ↦ κ(x, y, β) / (1 - β) is monotone on (0, 1) and converges to the Lin–Lu–Yau curvature κ_LLY(x, y) as β → 1⁻.
Because G is connected and x ≠ y, graph_ollivier_curvature_div_monotoneOn establishes monotonicity of the quotient on (0, 1), and graph_lly_curvature_tendsto states that κ_LLY(x, y) is the limit of this quotient as β approaches 1 from below.
uses
graph_ollivier_curvature_div_monotoneOn,graph_lly_curvature_tendstohave hmono := graph_ollivier_curvature_div_monotoneOn G hG x y hne have htend := graph_lly_curvature_tendsto G hG x y hne
For all β sufficiently close to 1 from below, κ(x, y, α) / (1 - α) ≤ κ(x, y, β) / (1 - β).
The open ray (α, ∞) contains 1 since α < 1 and is open by isOpen_Ioi, so the trace interval (α, 1) belongs to the filter of left neighborhoods of 1 by mem_nhdsWithin.mpr. For every β in this interval, 0 < α < β < 1 (using lt_trans and le_of_lt), so monotonicity of the quotient implies that the value at α is bounded above by the value at β. Applying Filter.eventually_of_mem shows this inequality holds eventually along the filter.
uses
Filter.eventually_of_mem,mem_nhdsWithin.mpr,isOpen_Ioi,lt_trans,le_of_lthave hev : ∀ᶠ β in nhdsWithin 1 (Set.Iio 1), graph_ollivier_curvature G α x y / (1 - α) ≤ graph_ollivier_curvature G β x y / (1 - β) := by apply Filter.eventually_of_mem · exact mem_nhdsWithin.mpr ⟨Set.Ioi α, isOpen_Ioi, hα1, fun z hz => hz⟩ · intro β hβ exact hmono ⟨hα0, hα1⟩ ⟨lt_trans hα0 hβ.1, hβ.2⟩ (le_of_lt hβ.1)
κ(x, y, α) / (1 - α) ≤ κ_LLY(x, y).
Since the quotient converges to κ_LLY(x, y) as β → 1⁻ and is eventually bounded below by κ(x, y, α) / (1 - α), ge_of_tendsto guarantees that the limit inherits the same lower bound.
uses
ge_of_tendstohave hle : graph_ollivier_curvature G α x y / (1 - α) ≤ graph_lly_curvature G x y := ge_of_tendsto htend hevThe Lin–Lu–Yau curvature κ_LLY(x, y) is strictly positive.
Linear arithmetic combines the strict inequality 0 < κ(x, y, α) / (1 - α) with the weak inequality κ(x, y, α) / (1 - α) ≤ κ_LLY(x, y) to conclude 0 < κ_LLY(x, y).
linarith
SimpleGraph.dist_eq_one_iff_adj.mpr- Adjacent vertices in a simple graph have graph distance 1.
div_pos- The quotient of two strictly positive numbers is strictly positive.
graph_ollivier_curvature_div_monotoneOn- For any two distinct vertices in a connected graph, the quotient of Ollivier curvature by 1 - α is monotone non-decreasing in the laziness parameter α ∈ (0, 1).
graph_lly_curvature_tendsto- The quotient of Ollivier curvature by 1 - α converges to the Lin–Lu–Yau curvature as α approaches 1 from below.
Filter.eventually_of_mem- A property holds eventually along a filter if it holds everywhere on some set belonging to that filter.
mem_nhdsWithin.mpr- A set is in the neighborhood filter of a point within a subset if it contains the intersection of that subset with an open neighborhood of the point.
isOpen_Ioi- The open ray (a, ∞) is an open set.
lt_trans- Strict inequality is transitive: if a < b and b < c, then a < c.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
ge_of_tendsto- If a function tends to a limit along a filter and is eventually bounded below by a constant, then the limit is also bounded below by that constant.
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.
/-- If the Wasserstein distance between idle measures μ_x^α and μ_y^α is strictly less than 1 for some α ∈ (0, 1) along an edge xy, then the Lin–Lu–Yau curvature κ_LLY(x, y) is strictly positive. -/theorem graph_lly_curvature_pos_of_wasserstein_lt_one {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : G.Adj x y) (α : ℝ) (hα0 : 0 < α) (hα1 : α < 1) (hW : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) < 1) : 0 < graph_lly_curvature G x y := by have hne : x ≠ y := hxy.ne have hdist : G.dist x y = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hxy have hdistR : (G.dist x y : ℝ) = 1 := by rw [hdist]; norm_num have hcurv : graph_ollivier_curvature G α x y = 1 - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by unfold graph_ollivier_curvature rw [hdistR] simp have hposcurv : 0 < graph_ollivier_curvature G α x y := by rw [hcurv]; linarith have hposf : 0 < graph_ollivier_curvature G α x y / (1 - α) := by apply div_pos hposcurv; linarith have hmono := graph_ollivier_curvature_div_monotoneOn G hG x y hne have htend := graph_lly_curvature_tendsto G hG x y hne have hev : ∀ᶠ β in nhdsWithin 1 (Set.Iio 1), graph_ollivier_curvature G α x y / (1 - α) ≤ graph_ollivier_curvature G β x y / (1 - β) := by apply Filter.eventually_of_mem · exact mem_nhdsWithin.mpr ⟨Set.Ioi α, isOpen_Ioi, hα1, fun z hz => hz⟩ · intro β hβ exact hmono ⟨hα0, hα1⟩ ⟨lt_trans hα0 hβ.1, hβ.2⟩ (le_of_lt hβ.1) have hle : graph_ollivier_curvature G α x y / (1 - α) ≤ graph_lly_curvature G x y := ge_of_tendsto htend hev linarith