AFTD Auto-Formalizing Theoretical Domains

graph_ollivier_curvature_div_monotoneOn

theoremverifiedformalization

In a finite connected graph, for x ≠ y, α ↦ κ_α(x, y)/(1 − α) is nondecreasing on (0, 1).

Statement

theorem graph_ollivier_curvature_div_monotoneOn {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) :
    MonotoneOn (fun α => graph_ollivier_curvature G α x y / (1 - α)) (Set.Ioo 0 1)
Formalizes
arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Sec. 2.2 (the monotonicity of κ_α/(1 − α) on which Definition 2.3 rests, quoted there from its reference [15]); proved here by mixing transport plans with the point masses at idleness 1 instead of through concavity.
Verified
10 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 8
Used by 2
  • 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,…
  • 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…

The proof, explained

To prove that α ↦ κ_α(x, y)/(1 - α) is nondecreasing on (0, 1), we fix 0 < α ≤ β < 1 and relate the idle measures at β to those at α. Because the idle measure m_β^x decomposes as a mixture of m_α^x and the Dirac mass δ_x with weight t = (1 - β)/(1 - α) ∈ [0, 1], convexity of the Wasserstein distance gives W₁(m_β^x, m_β^y) ≤ t W₁(m_α^x, m_α^y) + (1 - t) d(x, y). Multiplying by 1 - α and rewriting in terms of Ollivier curvature κ_α = 1 - W₁/d directly yields κ_α(x, y)/(1 - α) ≤ κ_β(x, y)/(1 - β).

  1. To show monotonicity on (0, 1), it suffices to prove that κ_α(x, y) / (1 - α) ≤ κ_β(x, y) / (1 - β) whenever 0 < α ≤ β < 1.

    We introduce parameters α and β in the open interval (0, 1) with α ≤ β and simplify the monotonicity goal to showing that the ratio evaluated at α is bounded by the ratio evaluated at β.

    lines 4–5

      intro α hα β hβ hab
      simp only
  2. The graph distance d(x, y) and vertex degrees are strictly positive, and the mixture parameter t = (1 - β) / (1 - α) belongs to [0, 1].

    Because G is connected and x ≠ y, the graph distance d(x, y) is strictly positive, and both x and y have positive degree by `graph_degree_pos_of_connected_of_ne`. Since α, β < 1, both 1 - α and 1 - β are positive. Consequently, the mixture ratio t = (1 - β)/(1 - α) is nonnegative by `div_nonneg`. Furthermore, since α ≤ β, we have 1 - β ≤ 1 - α, which implies t ≤ 1 by `div_le_one`.

    lines 6–12

    uses graph_degree_pos_of_connected_of_ne, div_nonneg, div_le_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 [hα.2]
      have h1β : 0 < 1 - β := by linarith [hβ.2]
      have ht0 : 0 ≤ (1 - β) / (1 - α) := div_nonneg h1β.le h1α.le
      have ht1 : (1 - β) / (1 - α) ≤ 1 := by rw [div_le_one h1α]; linarith
  3. The Wasserstein distance between the idle measures at parameter β satisfies W₁(m_β^x, m_β^y) ≤ ((1 - β) / (1 - α)) * W₁(m_α^x, m_α^y) + (1 - (1 - β) / (1 - α)) * d(x, y).

    The idle measures at parameter α are probability measures: they are nonnegative by `graph_idle_measure_nonneg` and sum to 1 by `graph_idle_measure_sum_eq_one` thanks to the positive degrees. Applying `graph_wasserstein_dist_mix_dirac_le` with mixture weight t = (1 - β)/(1 - α) ∈ [0, 1] bounds the Wasserstein distance between convex combinations with Dirac masses at x and y. Rewriting using `graph_idle_measure_eq_mix` identifies these mixtures precisely with the idle measures at parameter β.

    lines 13–17

    uses graph_wasserstein_dist_mix_dirac_le, graph_idle_measure_nonneg, graph_idle_measure_sum_eq_one, graph_idle_measure_eq_mix

      have hmix := graph_wasserstein_dist_mix_dirac_le G (graph_idle_measure G α x)
        (graph_idle_measure G α y) (graph_idle_measure_nonneg G α hα.1.le hα.2.le x)
        (graph_idle_measure_nonneg G α hα.1.le hα.2.le y) (graph_idle_measure_sum_eq_one G α x hdx)
        (graph_idle_measure_sum_eq_one G α y hdy) x y _ ht0 ht1
      rw [← graph_idle_measure_eq_mix G x α β hα.2, ← graph_idle_measure_eq_mix G y α β hα.2] at hmix
  4. Letting A = W₁(m_α^x, m_α^y), B = W₁(m_β^x, m_β^y), and d = d(x, y), we have B * (1 - α) ≤ (1 - β) * A + (β - α) * d.

    We unfold the definition of Ollivier curvature and abbreviate the Wasserstein distances as A and B and the graph distance as d. Multiplying the mixture inequality B ≤ ((1 - β)/(1 - α)) * A + (1 - (1 - β)/(1 - α)) * d by the positive factor 1 - α via `mul_le_mul_of_nonneg_right` and clearing the fractions yields B * (1 - α) ≤ (1 - β) * A + (β - α) * d.

    lines 18–26

    uses mul_le_mul_of_nonneg_right

      unfold graph_ollivier_curvature
      generalize graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) = A at hmix ⊢
      generalize graph_wasserstein_dist G (graph_idle_measure G β x) (graph_idle_measure G β y) = B at hmix ⊢
      generalize (G.dist x y : ℝ) = d at hmix hd ⊢
      have hB : B * (1 - α) ≤ (1 - β) * A + (β - α) * d := by
        have := mul_le_mul_of_nonneg_right hmix h1α.le
        have e1 : (1 - β) / (1 - α) * A * (1 - α) = (1 - β) * A := by field_simp
        have e2 : (1 - (1 - β) / (1 - α)) * d * (1 - α) = (β - α) * d := by field_simp; ring
        nlinarith [e1, e2]
  5. κ_α(x, y) / (1 - α) ≤ κ_β(x, y) / (1 - β).

    Since 1 - α > 0 and 1 - β > 0, clearing denominators via `div_le_div_iff₀` transforms the target inequality into (1 - A / d) * (1 - β) ≤ (1 - B / d) * (1 - α). Putting both sides over the common denominator d and dividing by d > 0 via `div_le_div_of_nonneg_right` reduces this to (d - A) * (1 - β) ≤ (d - B) * (1 - α). Expanding both sides and rearranging by linear arithmetic matches the previously established bound B * (1 - α) ≤ (1 - β) * A + (β - α) * d.

    lines 27–32

    uses div_le_div_iff₀, div_le_div_of_nonneg_right

      rw [div_le_div_iff₀ h1α h1β]
      have lhs : (1 - A / d) * (1 - β) = ((d - A) * (1 - β)) / d := by field_simp
      have rhs : (1 - B / d) * (1 - α) = ((d - B) * (1 - α)) / d := by field_simp
      rw [lhs, rhs]
      apply div_le_div_of_nonneg_right _ hd.le
      nlinarith
graph_degree_pos_of_connected_of_ne
In a connected graph with at least two distinct vertices, every vertex has strictly positive degree.
div_nonneg
The quotient of two nonnegative real numbers is nonnegative.
div_le_one
For a positive divisor b, the quotient a / b is at most 1 if and only if a ≤ b.
graph_wasserstein_dist_mix_dirac_le
The Wasserstein distance between convex combinations of probability measures with Dirac masses at x and y is bounded by t times the Wasserstein distance between the measures plus (1 - t) times the graph distance between x and y.
graph_idle_measure_nonneg
For idleness parameter α ∈ [0, 1], the idle measure at any vertex is everywhere nonnegative.
graph_idle_measure_sum_eq_one
If the degree of a vertex x is strictly positive, the idle measure at x has total sum 1.
graph_idle_measure_eq_mix
For α < 1, the idle measure at parameter β is a convex combination of the idle measure at α (with weight (1 - β)/(1 - α)) and the Dirac mass at the base vertex.
mul_le_mul_of_nonneg_right
Multiplying both sides of an inequality by a nonnegative number preserves the inequality.
div_le_div_iff₀
For positive denominators b and d, the inequality a / b ≤ c / d is equivalent to a * d ≤ c * b.
div_le_div_of_nonneg_right
Dividing both sides of an inequality by a nonnegative number preserves the inequality.

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_monotoneOn {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) (x y : V) (hxy : x ≠ y) :    MonotoneOn (fun α => graph_ollivier_curvature G α x y / (1 - α)) (Set.Ioo 0 1) := by  intro α hα β hβ hab  simp only  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 [hα.2]  have h1β : 0 < 1 - β := by linarith [hβ.2]  have ht0 : 0 ≤ (1 - β) / (1 - α) := div_nonneg h1β.le h1α.le  have ht1 : (1 - β) / (1 - α) ≤ 1 := by rw [div_le_one h1α]; linarith  have hmix := graph_wasserstein_dist_mix_dirac_le G (graph_idle_measure G α x)    (graph_idle_measure G α y) (graph_idle_measure_nonneg G α hα.1.le hα.2.le x)    (graph_idle_measure_nonneg G α hα.1.le hα.2.le y) (graph_idle_measure_sum_eq_one G α x hdx)    (graph_idle_measure_sum_eq_one G α y hdy) x y _ ht0 ht1  rw [← graph_idle_measure_eq_mix G x α β hα.2, ← graph_idle_measure_eq_mix G y α β hα.2] at hmix  unfold graph_ollivier_curvature  generalize graph_wasserstein_dist G (graph_idle_measure G α x) (graph_idle_measure G α y) = A at hmix ⊢  generalize graph_wasserstein_dist G (graph_idle_measure G β x) (graph_idle_measure G β y) = B at hmix ⊢  generalize (G.dist x y : ℝ) = d at hmix hd ⊢  have hB : B * (1 - α) ≤ (1 - β) * A + (β - α) * d := by    have := mul_le_mul_of_nonneg_right hmix h1α.le    have e1 : (1 - β) / (1 - α) * A * (1 - α) = (1 - β) * A := by field_simp    have e2 : (1 - (1 - β) / (1 - α)) * d * (1 - α) = (β - α) * d := by field_simp; ring    nlinarith [e1, e2]  rw [div_le_div_iff₀ h1α h1β]  have lhs : (1 - A / d) * (1 - β) = ((d - A) * (1 - β)) / d := by field_simp  have rhs : (1 - B / d) * (1 - α) = ((d - B) * (1 - α)) / d := by field_simp  rw [lhs, rhs]  apply div_le_div_of_nonneg_right _ hd.le  nlinarith
See it in the graphDiscuss this resultChallenge it