AFTD Auto-Formalizing Theoretical Domains

graph_lly_curvature_le_two_div_dist

theoremverified

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
Used by 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.

  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).

    line 4

    uses le_of_tendsto, graph_lly_curvature_tendsto

      apply le_of_tendsto (graph_lly_curvature_tendsto G hG x y hxy)
  2. 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.

    lines 5–6

    uses Ioo_mem_nhdsLT, graph_ollivier_curvature_div_le_two_div_dist

      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
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

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
See it in the graphDiscuss this resultChallenge it