graph_lly_curvature
def
The Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
Statement
noncomputable def graph_lly_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.3 (Lin–Lu–Yau curvature); the limit is written with `Filter.limUnder`, which agrees with it since the limit exists (Sec. 2.2).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- graph_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
- Used by 21
- 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_lower_bound_two_le_oneFor every finite connected graph G, the lower Lin–Lu–Yau curvature bound at scale 2 is at most 1: κ_LLY^(2)(G) ≤ 2/2 = 1.
- lly_positive_edge_connectivity_threshold_fivec(5) = 2: every connected graph on 5 vertices with edge-connectivity at least 2 has positive Lin–Lu–Yau curvature on every edge, while the…
- 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…
- lly_positive_edge_connectivity_thresholdc(n): the smallest natural number k such that every connected simple graph on n vertices with edge-connectivity at least k has positive…
- 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.
- 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.
- graph_lly_curvature_commThe Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
- graph_lly_curvature_lower_bound_le_of_dist_eqThe scale-i lower curvature bound is a lower bound for κ_LLY at any pair at distance i: κ_LLY^(i)(G) ≤ κ_LLY(x,y) whenever d(x,y) = i.
- graph_lly_curvature_pos_of_threeIn a finite connected graph with exactly three vertices x, y, z, every edge xy has positive Lin–Lu–Yau curvature.
- 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),…
- edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_bound_of_eq_minDegreeOP-164 holds for every finite connected graph whose edge-connectivity equals its minimum degree: then κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) for…
- lly_positive_edge_connectivity_threshold_threec(3) = 0: every connected graph on 3 vertices has positive Lin–Lu–Yau curvature on every edge, whatever its edge-connectivity.
- graph_lly_curvature_lower_boundThe lower Lin–Lu–Yau curvature bound at scale i: κ_LLY^(i)(G) = inf { κ_LLY(x, y) : d(x, y) = i }.
- 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,…
- 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…
- 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
/-- Lin–Lu–Yau curvature: the limit of `κ_α(x, y) / (1 - α)` as the idleness `α` tends to `1` from below. -/ noncomputable def graph_lly_curvature {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) : ℝ := Filter.limUnder (nhdsWithin 1 (Set.Iio 1)) (fun α => graph_ollivier_curvature G α x y / (1 - α))