lly_five_vertex_t_star_curvature
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
- lly_positive_edge_connectivity_threshold_fivec(5) = 2: every connected graph on 5 vertices with edge-connectivity at least 2 has positive Lin–Lu–Yau curvature on every edge, while the…
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$.
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)$.
uses
graph_lly_curvature_eq_of_ollivier_eqhave 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
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$.
uses
le_of_lt,five_vertex_t_star_wasserstein_le,five_vertex_t_star_wasserstein_ge,le_antisymmintro α 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
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)$.
uses
five_vertex_t_star_dist_eq.1unfold 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
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.
/-- 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