graph_ollivier_curvature
def
The α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
Statement
noncomputable def graph_ollivier_curvature {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (x y : V) : ℝ
- Defined in
- arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Definition 2.2 (Ollivier–Ricci curvature).
- Verified
- 10 Oct 2026
- Axioms
- none listed
- Built on 2
- 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.
- Used by 13
- 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).
- graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- graph_lly_curvature_commThe Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
- 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_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_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),…
- 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_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_lly_curvature_eq_of_ollivier_eqIf κ_α(x, y) = (1 − α)c for all α in an interval (a, 1), then κ_LLY(x, y) = c.
Lean source view module on GitHub
/-- α-Ollivier–Ricci curvature `κ_α(x, y) = 1 - W(μ_x^α, μ_y^α) / d(x, y)`. -/ noncomputable def graph_ollivier_curvature {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (α : ℝ) (x y : V) : ℝ := 1 - graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) / (G.dist x y : ℝ)