AFTD Auto-Formalizing Theoretical Domains

lly_five_vertex_t_star_curvature

theoremverified

For the tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2 one has κ_LLY(0,1) = −1/3.

Statement

theorem lly_five_vertex_t_star_curvature :
    graph_lly_curvature five_vertex_t_star (0 : Fin 5) (1 : Fin 5) = -(1 / 3)
Source
step towards lly_positive_edge_connectivity_threshold_five
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • five_vertex_t_starThe tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2: the path 3–0–1–2 with an extra leaf 4 attached at 0.
  • five_vertex_t_star_adj_decidableAdjacency in the T-graph is decidable.
  • five_vertex_t_star_wasserstein_leFor the T-graph and α in [2/5, 1], the explicit plan π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3,…
  • five_vertex_t_star_wasserstein_geFor the T-graph and α in [0,1], 4/3 − α/3 ≤ W(μ_0^α, μ_1^α), because f(v) = d(v,2) is 1-Lipschitz and Σ f μ_0^α − Σ f μ_1^α = (2α +…
  • graph_lly_curvature_eq_of_ollivier_eqIf κ_α(x, y) = (1 − α)c for all α in an interval (a, 1), then κ_LLY(x, y) = c.
  • graph_ollivier_curvatureThe α-Ollivier–Ricci curvature κ_α(x, y) = 1 − W(μ_x^α, μ_y^α)/d(x, y).
  • five_vertex_t_star_dist_eqIn the T-graph: d(0,1) = 1, d(0,2) = 2, d(3,1) = 2, d(4,1) = 2, d(3,2) = d(4,2) = 3.
  • 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_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
  • 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 1

The proof, explained

The Lin-Lu-Yau curvature is defined as the limit as $\alpha \to 1^-$ of the Ollivier-Ricci curvature rescaled by $1/(1 - \alpha)$. For $\alpha \in (2/5, 1)$, matching upper and lower bounds establish that the Wasserstein distance between the idle random walk measures at vertices 0 and 1 is precisely $4/3 - \alpha/3$. Since the graph distance between 0 and 1 is 1, the Ollivier curvature evaluates to $1 - (4/3 - \alpha/3) = (1 - \alpha)(-1/3)$. Taking the limit via `graph_lly_curvature_eq_of_ollivier_eq` concludes that $\kappa_{\mathrm{LLY}}(0, 1) = -1/3$.

  1. To determine $\kappa_{\mathrm{LLY}}(0, 1) = -1/3$, it suffices to show that $\kappa_\alpha(0, 1) = (1 - \alpha)(-1/3)$ for all $\alpha \in (2/5, 1)$.

    The inequality $2/5 < 1$ is verified by `norm_num`. Applying `graph_lly_curvature_eq_of_ollivier_eq` then reduces the calculation of the limit defining Lin-Lu-Yau curvature to proving that the Ollivier-Ricci curvature has the affine form $(1 - \alpha) \cdot (-1/3)$ on the interval $(2/5, 1)$.

    lines 4–5

    uses graph_lly_curvature_eq_of_ollivier_eq

      have ha : (2 / 5 : ℝ) < 1 := by norm_num
      apply graph_lly_curvature_eq_of_ollivier_eq five_vertex_t_star 0 1 (-(1 / 3)) (2 / 5) ha
  2. For any $\alpha \in (2/5, 1)$, the Wasserstein distance between the idle measures at vertices 0 and 1 is exactly $4/3 - \alpha/3$.

    Fixing $\alpha \in (2/5, 1)$, we obtain the non-strict bounds $2/5 \le \alpha$ and $\alpha \le 1$ via `le_of_lt`. Lemma `five_vertex_t_star_wasserstein_le` yields the upper bound $W \le 4/3 - \alpha/3$. Since $\alpha > 2/5$ implies $0 \le \alpha$ by linear arithmetic (`linarith`), lemma `five_vertex_t_star_wasserstein_ge` provides the matching lower bound $4/3 - \alpha/3 \le W$. Combining both inequalities with `le_antisymm` establishes the exact value $W = 4/3 - \alpha/3$.

    lines 6–14

    uses le_of_lt, five_vertex_t_star_wasserstein_le, five_vertex_t_star_wasserstein_ge, le_antisymm

      intro α hα_lower hα_upper
      have hα0 : (2 / 5 : ℝ) ≤ α := le_of_lt hα_lower
      have hα1 : α ≤ 1 := le_of_lt hα_upper
      have h_le := five_vertex_t_star_wasserstein_le α hα0 hα1
      have hα0_ge : 0 ≤ α := by linarith
      have h_ge := five_vertex_t_star_wasserstein_ge α hα0_ge hα1
      have h_w : graph_wasserstein_dist five_vertex_t_star
          (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) =
          4 / 3 - α / 3 := le_antisymm h_le h_ge
  3. For every $\alpha \in (2/5, 1)$, the Ollivier-Ricci curvature $\kappa_\alpha(0, 1)$ equals $(1 - \alpha)(-1/3)$.

    By definition, $\kappa_\alpha(0, 1) = 1 - W / d(0, 1)$. Rewriting with the exact Wasserstein distance $W = 4/3 - \alpha/3$ and the graph distance $d(0, 1) = 1$ (given by `five_vertex_t_star_dist_eq.1`), pushing the integer cast to the real numbers, and simplifying ring operations with `ring` establishes the identity $1 - (4/3 - \alpha/3) / 1 = (1 - \alpha)(-1/3)$.

    lines 15–20

    uses five_vertex_t_star_dist_eq.1

      unfold graph_ollivier_curvature
      rw [h_w]
      have h_dist : five_vertex_t_star.dist 0 1 = 1 := five_vertex_t_star_dist_eq.1
      rw [h_dist]
      push_cast
      ring
graph_lly_curvature_eq_of_ollivier_eq
If there exists $a < 1$ such that the Ollivier-Ricci curvature satisfies $\kappa_\alpha(x, y) = (1 - \alpha) c$ for all $\alpha \in (a, 1)$, then the Lin-Lu-Yau curvature $\kappa_{\mathrm{LLY}}(x, y)$ equals $c$.
le_of_lt
A strict inequality $a < b$ in a preorder implies the weak inequality $a \le b$.
five_vertex_t_star_wasserstein_le
For the 5-vertex tree, if $2/5 \le \alpha \le 1$, the Wasserstein distance between the idle random walk measures at vertices 0 and 1 is at most $4/3 - \alpha/3$.
five_vertex_t_star_wasserstein_ge
For the 5-vertex tree, if $0 \le \alpha \le 1$, the Wasserstein distance between the idle random walk measures at vertices 0 and 1 is at least $4/3 - \alpha/3$.
le_antisymm
In a partial order, if $a \le b$ and $b \le a$, then $a = b$.
five_vertex_t_star_dist_eq.1
In the 5-vertex tree, the graph distance between vertices 0 and 1 is 1.

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

/-- By the two Wasserstein bounds, κ_α(0,1) = 1 − W = (1−α)·(−1/3) for α ≥ 2/5, so the limit defining κ_LLY gives κ_LLY(0,1) = −1/3. This supplies the exact equality from the escalation, with the erroneous explicit plan replaced. -/theorem lly_five_vertex_t_star_curvature :    graph_lly_curvature five_vertex_t_star (0 : Fin 5) (1 : Fin 5) = -(1 / 3) := by  have ha : (2 / 5 : ℝ) < 1 := by norm_num  apply graph_lly_curvature_eq_of_ollivier_eq five_vertex_t_star 0 1 (-(1 / 3)) (2 / 5) ha  intro α hα_lower hα_upper  have hα0 : (2 / 5 : ℝ) ≤ α := le_of_lt hα_lower  have hα1 : α ≤ 1 := le_of_lt hα_upper  have h_le := five_vertex_t_star_wasserstein_le α hα0 hα1  have hα0_ge : 0 ≤ α := by linarith  have h_ge := five_vertex_t_star_wasserstein_ge α hα0_ge hα1  have h_w : graph_wasserstein_dist five_vertex_t_star      (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) =      4 / 3 - α / 3 := le_antisymm h_le h_ge  unfold graph_ollivier_curvature  rw [h_w]  have h_dist : five_vertex_t_star.dist 0 1 = 1 := five_vertex_t_star_dist_eq.1  rw [h_dist]  push_cast  ring
See it in the graphDiscuss this resultChallenge it