AFTD Auto-Formalizing Theoretical Domains

graph_lly_curvature_pos_of_wasserstein_lt_one

theoremverified

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

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.

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

    lines 9–11

    uses SimpleGraph.dist_eq_one_iff_adj.mpr

      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
  2. 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^α).

    lines 12–16

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

    lines 17–20

    uses div_pos

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

    lines 21–22

    uses graph_ollivier_curvature_div_monotoneOn, graph_lly_curvature_tendsto

      have hmono := graph_ollivier_curvature_div_monotoneOn G hG x y hne
      have htend := graph_lly_curvature_tendsto G hG x y hne
  5. 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.

    lines 23–29

    uses Filter.eventually_of_mem, mem_nhdsWithin.mpr, isOpen_Ioi, lt_trans, le_of_lt

      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)
  6. κ(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.

    lines 30–31

    uses ge_of_tendsto

      have hle : graph_ollivier_curvature G α x y / (1 - α) ≤ graph_lly_curvature G x y :=
        ge_of_tendsto htend hev
  7. The 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).

    line 32

      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

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