graph_lly_curvature_le_two_div_dist
For distinct vertices x, y of a finite connected graph, κ_LLY(x, y) ≤ 2/d(x, y).
Statement
theorem graph_lly_curvature_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) : graph_lly_curvature G x y ≤ 2 / (G.dist x y : ℝ)
- Source
- Helper for OP-164 (arXiv:2610.10559). The 1-Lipschitz function v ↦ d(v, y) gives W(μ_x^α, μ_y^α) ≥ d − 2(1 − α), hence κ_α ≤ 2(1 − α)/d; passing to the limit needs its existence (Sec. 2.2 of the paper: κ_α/(1 − α) is nondecreasing and bounded).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- 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_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, 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_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…
- Used by 3
- 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.
- 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…
- exists_dist_eq_three_of_three_le_diamIf the diameter of a finite connected graph is at least 3, then some pair of vertices is at distance exactly 3.
The proof, explained
Lin-Lu-Yau curvature κ_LLY(x, y) is defined as the limit of the rescaled Ollivier curvature κ_α(x, y) / (1 - α) as α → 1⁻. Since non-strict inequalities are preserved under limits, it suffices to show that the inequality holds eventually along the left-neighborhood filter at 1. The result then follows from the known bound κ_α(x, y) / (1 - α) ≤ 2 / d(x, y) valid for all α ∈ (0, 1), which forms an open left-neighborhood of 1.
To prove κ_LLY(x, y) ≤ 2 / d(x, y), it suffices to show that the rescaled Ollivier curvature satisfies κ_α(x, y) / (1 - α) ≤ 2 / d(x, y) eventually as α approaches 1 from below.
By definition, the Lin-Lu-Yau curvature κ_LLY(x, y) is the limit of the rescaled Ollivier curvature κ_α(x, y) / (1 - α) as α → 1⁻ (graph_lly_curvature_tendsto). Because limits preserve non-strict inequalities (le_of_tendsto), the upper bound on the limit follows if the inequality holds eventually along the left-neighborhood filter nhdsWithin 1 (Iio 1).
uses
le_of_tendsto,graph_lly_curvature_tendstoapply le_of_tendsto (graph_lly_curvature_tendsto G hG x y hxy)The rescaled Ollivier curvature bound κ_α(x, y) / (1 - α) ≤ 2 / d(x, y) holds eventually as α → 1⁻.
Since 0 < 1, the open interval (0, 1) is a left-neighborhood of 1 (by Ioo_mem_nhdsLT). Filtering upwards along this neighborhood, it suffices to establish the inequality for any α ∈ (0, 1). For every such α, we have 0 ≤ α and α < 1, so the result follows immediately from the Ollivier curvature bound graph_ollivier_curvature_div_le_two_div_dist.
uses
Ioo_mem_nhdsLT,graph_ollivier_curvature_div_le_two_div_distfilter_upwards [Ioo_mem_nhdsLT (show (0 : ℝ) < 1 by norm_num)] with α hα exact graph_ollivier_curvature_div_le_two_div_dist G hG x y hxy α hα.1.le hα.2
le_of_tendsto- If a function tends to a limit along a filter, and is eventually bounded above by a constant along that filter, then its limit is bounded above by that constant.
graph_lly_curvature_tendsto- As α approaches 1 from below, the rescaled Ollivier curvature κ_α(x, y) / (1 - α) converges to the Lin-Lu-Yau curvature κ_LLY(x, y).
Ioo_mem_nhdsLT- For any a < b, the open interval (a, b) belongs to the filter of left-neighborhoods of b.
graph_ollivier_curvature_div_le_two_div_dist- For distinct vertices x, y in a connected graph and any parameter 0 ≤ α < 1, the rescaled Ollivier curvature satisfies κ_α(x, y) / (1 - α) ≤ 2 / d(x, y).
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_lly_curvature_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) : graph_lly_curvature G x y ≤ 2 / (G.dist x y : ℝ) := by 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 graph_ollivier_curvature_div_le_two_div_dist G hG x y hxy α hα.1.le hα.2