AFTD Auto-Formalizing Theoretical Domains

graph_ollivier_curvature_div_le_two_div_dist

theoremverified

In a finite connected graph, for x ≠ y and α ∈ [0, 1), κ_α(x, y)/(1 − α) ≤ 2/d(x, y).

Statement

theorem graph_ollivier_curvature_div_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)
    (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α < 1) :
    graph_ollivier_curvature G α x y / (1 - α) ≤ 2 / (G.dist x y : ℝ)
Source
Helper for graph_lly_curvature_le_two_div_dist (OP-164, arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature)).
Verified
10 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 2

The proof, explained

To bound the normalized Ollivier-Ricci curvature κ_α(x, y)/(1 - α) ≤ 2/d(x, y), it suffices to establish a lower bound on the Wasserstein distance W₁(μ_x, μ_y) between the idle random walk measures. By Kantorovich duality applied to the 1-Lipschitz test function f(v) = d(v, y), the Wasserstein distance is at least the difference of expectations 𝔼_{μ_x}[f] - 𝔼_{μ_y}[f]. Evaluating directly yields 𝔼_{μ_y}[f] = 1 - α, while the triangle inequality yields 𝔼_{μ_x}[f] ≥ d(x, y) - (1 - α). Subtracting these gives W₁(μ_x, μ_y) ≥ d(x, y) - 2(1 - α), which algebraically rearranges to the desired curvature bound.

  1. The graph distance d(x, y) and degrees deg(x), deg(y) are strictly positive, 1 - α > 0, and the idle measures μ_x and μ_y are valid probability measures (non-negative and summing to 1).

    Because G is connected and x ≠ y, the distance d(x, y) is strictly positive (via hG.pos_dist_of_ne) and both vertices have degree at least 1 (graph_degree_pos_of_connected_of_ne). The condition α < 1 implies 1 - α > 0. For α ∈ [0, 1), the idle measure μ_x, which places mass α on x and (1 - α) / deg(x) on each neighbor, is non-negative everywhere (graph_idle_measure_nonneg) and sums to 1 (graph_idle_measure_sum_eq_one), and similarly for μ_y.

    lines 5–12

    uses hG.pos_dist_of_ne, graph_degree_pos_of_connected_of_ne, graph_idle_measure_nonneg, graph_idle_measure_sum_eq_one

      have hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy
      have hdx := graph_degree_pos_of_connected_of_ne G hG x y hxy
      have hdy := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm
      have h1α : 0 < 1 - α := by linarith
      have hnx := graph_idle_measure_nonneg G α hα0 hα1.le x
      have hny := graph_idle_measure_nonneg G α hα0 hα1.le y
      have hsx := graph_idle_measure_sum_eq_one G α x hdx
      have hsy := graph_idle_measure_sum_eq_one G α y hdy
  2. The distance-to-y function v ↦ d(v, y) is 1-Lipschitz: d(a, y) - d(b, y) ≤ d(a, b) for all vertices a, b.

    For any two vertices a and b, the graph triangle inequality (hG.dist_triangle) gives d(a, y) ≤ d(a, b) + d(b, y). Subtracting d(b, y) from both sides yields the 1-Lipschitz condition d(a, y) - d(b, y) ≤ d(a, b).

    lines 13–18

    uses hG.dist_triangle

      have hf : ∀ a b, (fun v => (G.dist v y : ℝ)) a - (fun v => (G.dist v y : ℝ)) b ≤ G.dist a b := by
        intro a b
        have := hG.dist_triangle (u := a) (v := b) (w := y)
        simp only
        have : (G.dist a y : ℝ) ≤ G.dist a b + G.dist b y := by exact_mod_cast this
        linarith
  3. The Wasserstein distance W₁(μ_x, μ_y) is bounded below by the difference of expectations ∑_a d(a, y) μ_x(a) - ∑_b d(b, y) μ_y(b).

    By Kantorovich-Rubinstein duality for graph Wasserstein distance (graph_wasserstein_dist_ge_of_lipschitz), W₁(μ_x, μ_y) is bounded below by the difference of expectations of any 1-Lipschitz test function. Applying this duality to the 1-Lipschitz function v ↦ d(v, y) gives the inequality.

    line 19

    uses graph_wasserstein_dist_ge_of_lipschitz

      have hW := graph_wasserstein_dist_ge_of_lipschitz G _ _ hnx hny hsx hsy _ hf
  4. The expectation of the distance to y under the idle measure at x satisfies ∑_a d(a, y) μ_x(a) ≥ d(x, y) - 1 + α.

    We establish pointwise that ((d(x, y) - 1) + 𝟏_{a = x}) μ_x(a) ≤ d(a, y) μ_x(a) for every vertex a. If a = x, both sides equal d(x, y) μ_x(x). If a ≠ x is a neighbor of x, d(x, a) = 1 (SimpleGraph.dist_eq_one_iff_adj.mpr), so the triangle inequality d(x, y) ≤ 1 + d(a, y) gives d(x, y) - 1 ≤ d(a, y), which after multiplying by μ_x(a) ≥ 0 yields the bound. If a is neither x nor adjacent to x, μ_x(a) = 0 so both sides vanish. Summing over all a in V via Finset.sum_le_sum, distributing sums, and using ∑_a μ_x(a) = 1 and μ_x(x) = α evaluates the left-hand side to (d(x, y) - 1) + α.

    lines 20–42

    uses if_false, add_zero, mul_le_mul_of_nonneg_right, hG.dist_triangle, SimpleGraph.dist_eq_one_iff_adj.mpr, add_mul, Finset.sum_add_distrib, Finset.mul_sum, ite_mul, one_mul, zero_mul, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true, Finset.sum_le_sum

      have ex : (G.dist x y : ℝ) - 1 + α ≤ ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α x a := by
        have term : ∀ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a
            ≤ (G.dist a y : ℝ) * graph_idle_measure G α x a := by
          intro a
          by_cases hax : a = x
          · subst a; simp
          · simp only [hax, if_false, add_zero]
            by_cases hadj : G.Adj x a
            · apply mul_le_mul_of_nonneg_right _ (hnx a)
              have t := hG.dist_triangle (u := x) (v := a) (w := y)
              rw [SimpleGraph.dist_eq_one_iff_adj.mpr hadj] at t
              have : (G.dist x y : ℝ) ≤ 1 + G.dist a y := by exact_mod_cast t
              linarith
            · have : graph_idle_measure G α x a = 0 := by
                simp [graph_idle_measure, hax, hadj]
              rw [this]
              simp
        calc (G.dist x y : ℝ) - 1 + α
            = ∑ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a := by
              simp only [add_mul, Finset.sum_add_distrib, ← Finset.mul_sum, hsx, ite_mul, one_mul,
                zero_mul, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true]
              simp [graph_idle_measure]
          _ ≤ _ := Finset.sum_le_sum fun a _ => term a
  5. The expectation of the distance to y under the idle measure at y equals 1 - α, that is, ∑_a d(a, y) μ_y(a) = 1 - α.

    For each vertex a, d(a, y) μ_y(a) = μ_y(a) - α 𝟏_{a = y}. This is checked by cases: if a = y, d(y, y) = 0 and μ_y(y) - α = α - α = 0; if a is adjacent to y, d(a, y) = 1 (using symmetry SimpleGraph.dist_comm and SimpleGraph.dist_eq_one_iff_adj.mpr); if a is non-adjacent and a ≠ y, μ_y(a) = 0. Summing this equality over all a and splitting the sum with Finset.sum_sub_distrib gives ∑_a μ_y(a) - α = 1 - α.

    lines 43–55

    uses SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj.mpr, Finset.sum_sub_distrib

      have ey : ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α y a = 1 - α := by
        have term : ∀ a, (G.dist a y : ℝ) * graph_idle_measure G α y a =
            graph_idle_measure G α y a - (if a = y then α else 0) := by
          intro a
          by_cases hay : a = y
          · subst a; simp [graph_idle_measure]
          · by_cases hadj : G.Adj y a
            · rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj.mpr hadj]
              simp [hay]
            · simp [graph_idle_measure, hay, hadj]
        simp_rw [term]
        rw [Finset.sum_sub_distrib, hsy]
        simp
  6. The Wasserstein distance satisfies W₁(μ_x, μ_y) ≥ d(x, y) - 2(1 - α).

    Combining the Kantorovich lower bound W₁(μ_x, μ_y) ≥ ∑_a d(a, y) μ_x(a) - ∑_a d(a, y) μ_y(a) with the lower bound d(x, y) - 1 + α on the first expectation and the exact value 1 - α for the second expectation, linear arithmetic (linarith) produces W₁(μ_x, μ_y) ≥ (d(x, y) - 1 + α) - (1 - α) = d(x, y) - 2(1 - α).

    lines 56–58

      have hWlow : (G.dist x y : ℝ) - 2 * (1 - α) ≤
          graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by
        linarith
  7. The normalized Ollivier-Ricci curvature satisfies κ_α(x, y) / (1 - α) ≤ 2 / d(x, y).

    By definition, κ_α(x, y) = 1 - W₁(μ_x, μ_y) / d(x, y). Since 1 - α > 0 and d(x, y) > 0, div_le_div_iff₀ translates the inequality κ_α(x, y) / (1 - α) ≤ 2 / d(x, y) into (1 - W₁ / d) * d ≤ 2(1 - α), which simplifies to d(x, y) - W₁ ≤ 2(1 - α). Using field_simp and the lower bound W₁ ≥ d(x, y) - 2(1 - α), non-linear arithmetic (nlinarith) closes the goal.

    lines 59–65

    uses div_le_div_iff₀

      unfold graph_ollivier_curvature
      rw [div_le_div_iff₀ h1α hd]
      have : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) /
          (G.dist x y : ℝ) * (G.dist x y : ℝ) =
          graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by
        field_simp
      nlinarith
hG.pos_dist_of_ne
In a connected graph, distinct vertices have strictly positive distance: if x ≠ y then 0 < d(x, y).
graph_degree_pos_of_connected_of_ne
In a connected graph, any vertex distinct from another vertex has degree strictly greater than 0.
graph_idle_measure_nonneg
For α ∈ [0, 1], the idle measure assigns non-negative mass to every vertex.
graph_idle_measure_sum_eq_one
For any vertex with positive degree, the total mass of the idle measure over all vertices is 1.
hG.dist_triangle
In a connected graph, the distance function satisfies the triangle inequality: d(u, w) ≤ d(u, v) + d(v, w).
graph_wasserstein_dist_ge_of_lipschitz
For any 1-Lipschitz function f on a graph and probability measures μ, ν, the Wasserstein distance W₁(μ, ν) is at least ∑ f(a) μ(a) - ∑ f(b) ν(b).
if_false
An if-then-else expression with condition False evaluates to the else branch: (if False then t else e) = e.
add_zero
Adding zero on the right leaves an element unchanged: a + 0 = a.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality b ≤ c by a non-negative element a ≥ 0 preserves the inequality: b * a ≤ c * a.
SimpleGraph.dist_eq_one_iff_adj.mpr
Adjacent vertices in a graph are at distance 1 from each other: Adj u v → dist u v = 1.
add_mul
Multiplication distributes over addition from the right: (a + b) * c = a * c + b * c.
Finset.sum_add_distrib
The sum of a sum of functions is the sum of their individual sums: ∑ (f(x) + g(x)) = ∑ f(x) + ∑ g(x).
Finset.mul_sum
Multiplication distributes over finite sums: a * ∑ f(i) = ∑ (a * f(i)).
ite_mul
Multiplication distributes into an if-then-else: (if P then a else b) * c = if P then a * c else b * c.
one_mul
Multiplying by 1 on the left leaves an element unchanged: 1 * a = a.
zero_mul
Multiplying by 0 on the left yields 0: 0 * a = 0.
Finset.sum_ite_eq'
Summing (if x = a then b(x) else 0) over a finite set evaluates to b(a) if a is in the set and 0 otherwise.
Finset.sum_ite_eq
Summing (if a = x then b(x) else 0) over a finite set evaluates to b(a) if a is in the set and 0 otherwise.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
if_true
An if-then-else expression with condition True evaluates to the then branch: (if True then t else e) = t.
Finset.sum_le_sum
If f(i) ≤ g(i) for all indices i in a finite set, then ∑ f(i) ≤ ∑ g(i).
SimpleGraph.dist_comm
Graph distance is symmetric: dist u v = dist v u.
Finset.sum_sub_distrib
The sum of a difference of functions is the difference of their sums: ∑ (f(x) - g(x)) = ∑ f(x) - ∑ g(x).
div_le_div_iff₀
For positive denominators b > 0 and d > 0, a / b ≤ c / d if and only if a * d ≤ c * b.

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_ollivier_curvature_div_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)    (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α < 1) :    graph_ollivier_curvature G α x y / (1 - α) ≤ 2 / (G.dist x y : ℝ) := by  have hd : (0 : ℝ) < G.dist x y := by exact_mod_cast hG.pos_dist_of_ne hxy  have hdx := graph_degree_pos_of_connected_of_ne G hG x y hxy  have hdy := graph_degree_pos_of_connected_of_ne G hG y x hxy.symm  have h1α : 0 < 1 - α := by linarith  have hnx := graph_idle_measure_nonneg G α hα0 hα1.le x  have hny := graph_idle_measure_nonneg G α hα0 hα1.le y  have hsx := graph_idle_measure_sum_eq_one G α x hdx  have hsy := graph_idle_measure_sum_eq_one G α y hdy  have hf : ∀ a b, (fun v => (G.dist v y : ℝ)) a - (fun v => (G.dist v y : ℝ)) b ≤ G.dist a b := by    intro a b    have := hG.dist_triangle (u := a) (v := b) (w := y)    simp only    have : (G.dist a y : ℝ) ≤ G.dist a b + G.dist b y := by exact_mod_cast this    linarith  have hW := graph_wasserstein_dist_ge_of_lipschitz G _ _ hnx hny hsx hsy _ hf  have ex : (G.dist x y : ℝ) - 1 + α ≤ ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α x a := by    have term : ∀ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a        ≤ (G.dist a y : ℝ) * graph_idle_measure G α x a := by      intro a      by_cases hax : a = x      · subst a; simp      · simp only [hax, if_false, add_zero]        by_cases hadj : G.Adj x a        · apply mul_le_mul_of_nonneg_right _ (hnx a)          have t := hG.dist_triangle (u := x) (v := a) (w := y)          rw [SimpleGraph.dist_eq_one_iff_adj.mpr hadj] at t          have : (G.dist x y : ℝ) ≤ 1 + G.dist a y := by exact_mod_cast t          linarith        · have : graph_idle_measure G α x a = 0 := by            simp [graph_idle_measure, hax, hadj]          rw [this]          simp    calc (G.dist x y : ℝ) - 1 + α        = ∑ a, ((G.dist x y : ℝ) - 1 + (if a = x then 1 else 0)) * graph_idle_measure G α x a := by          simp only [add_mul, Finset.sum_add_distrib, ← Finset.mul_sum, hsx, ite_mul, one_mul,            zero_mul, Finset.sum_ite_eq', Finset.sum_ite_eq, Finset.mem_univ, if_true]          simp [graph_idle_measure]      _ ≤ _ := Finset.sum_le_sum fun a _ => term a  have ey : ∑ a, (G.dist a y : ℝ) * graph_idle_measure G α y a = 1 - α := by    have term : ∀ a, (G.dist a y : ℝ) * graph_idle_measure G α y a =        graph_idle_measure G α y a - (if a = y then α else 0) := by      intro a      by_cases hay : a = y      · subst a; simp [graph_idle_measure]      · by_cases hadj : G.Adj y a        · rw [SimpleGraph.dist_comm, SimpleGraph.dist_eq_one_iff_adj.mpr hadj]          simp [hay]        · simp [graph_idle_measure, hay, hadj]    simp_rw [term]    rw [Finset.sum_sub_distrib, hsy]    simp  have hWlow : (G.dist x y : ℝ) - 2 * (1 - α) ≤      graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by    linarith  unfold graph_ollivier_curvature  rw [div_le_div_iff₀ h1α hd]  have : graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) /      (G.dist x y : ℝ) * (G.dist x y : ℝ) =      graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) := by    field_simp  nlinarith
See it in the graphDiscuss this resultChallenge it