graph_ollivier_curvature_div_monotoneOn
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
- graph_wasserstein_dist_mix_dirac_leMixing with point masses: W(tμ + (1−t)δ_x, tν + (1−t)δ_y) ≤ t W(μ, ν) + (1−t) d(x, y) for probability measures μ, ν and t ∈ [0, 1].
- graph_idle_measure_eq_mixFor α < 1 and any β, μ_x^β = λ μ_x^α + (1 − λ) δ_x with λ = (1 − β)/(1 − α).
- graph_degree_pos_of_connected_of_neIn a connected graph, a vertex x with some other vertex y has positive degree.
- graph_idle_measure_nonnegμ_x^α is nonnegative for 0 ≤ α ≤ 1.
- graph_idle_measure_sum_eq_oneμ_x^α is a probability measure (total mass 1) when x has a neighbour.
- 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.
- 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 - β).
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 β.
intro α hα β hβ hab simp only
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`.
uses
graph_degree_pos_of_connected_of_ne,div_nonneg,div_le_onehave 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
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 β.
uses
graph_wasserstein_dist_mix_dirac_le,graph_idle_measure_nonneg,graph_idle_measure_sum_eq_one,graph_idle_measure_eq_mixhave 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
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.
uses
mul_le_mul_of_nonneg_rightunfold 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]
κ_α(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.
uses
div_le_div_iff₀,div_le_div_of_nonneg_rightrw [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
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_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