five_vertex_t_star_wasserstein_ge
For 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α + 7(1−α)/3) − 1 = 4/3 − α/3.
Statement
theorem five_vertex_t_star_wasserstein_ge (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) :
4 / 3 - α / 3 ≤ graph_wasserstein_dist five_vertex_t_star
(graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1)- Source
- step towards lly_positive_edge_connectivity_threshold_five
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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_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_dist_ge_of_lipschitzWeak Kantorovich duality: for probability measures μ, ν and any function f with f(a) − f(b) ≤ d(a, b), Σ f μ − Σ f ν ≤ W(μ, ν).
- graph_idle_measure_sum_eq_oneμ_x^α is a probability measure (total mass 1) when x has a neighbour.
- graph_idle_measure_nonnegμ_x^α is nonnegative for 0 ≤ α ≤ 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.
- graph_wasserstein_distThe Wasserstein distance W(μ, ν) between two measures on the vertices of a finite graph: the infimum, over all transport plans π ≥ 0 with…
- Used by 2
- 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…
- lly_five_vertex_t_star_curvatureFor the tree on 5 vertices with edges 0–1, 0–3, 0–4, 1–2 one has κ_LLY(0,1) = −1/3.
The proof, explained
The proof establishes the lower bound by Kantorovich duality using the test function f(v) = d(v, 2), which is shown to be 1-Lipschitz via the graph triangle inequality. After checking that the lazy random walk measures μ_0^α and μ_1^α are valid probability distributions, Kantorovich duality bounds the Wasserstein distance below by the difference in their expectations under f. Evaluating f and both measures explicitly at each of the five vertices yields the expectation difference 4/3 - α/3, completing the proof.
The graph five_vertex_t_star is connected, and the test function f(v) = d(v, 2) is 1-Lipschitz.
Connectedness of the finite graph is verified by exhaustive computation (decide). For any two vertices a and b, the triangle inequality d(a, 2) ≤ d(a, b) + d(b, 2) holds in any connected graph. Rearranging this inequality yields f(a) - f(b) ≤ d(a, b), establishing that f is 1-Lipschitz.
have hconn : five_vertex_t_star.Connected := by decide let f : Fin 5 → ℝ := fun v => (five_vertex_t_star.dist v 2 : ℝ) have hf : ∀ a b, f a - f b ≤ (five_vertex_t_star.dist a b : ℝ) := by intro a b dsimp [f] have := hconn.dist_triangle (u := a) (v := b) (w := 2) have h : (five_vertex_t_star.dist a 2 : ℝ) ≤ (five_vertex_t_star.dist a b : ℝ) + (five_vertex_t_star.dist b 2 : ℝ) := by exact_mod_cast this linarith
The idle measures μ_0^α and μ_1^α are probability measures, and Kantorovich duality bounds the Wasserstein distance below by ∑ f μ_0^α - ∑ f μ_1^α.
Since α ∈ [0, 1], the idle measures are pointwise nonnegative by graph_idle_measure_nonneg. The degrees of vertices 0 and 1 are strictly positive (verified by decide), so graph_idle_measure_sum_eq_one implies both measures sum to 1. Applying Kantorovich duality (graph_wasserstein_dist_ge_of_lipschitz) with the 1-Lipschitz function f provides the lower bound.
uses
graph_idle_measure_nonneg,graph_idle_measure_sum_eq_one,graph_wasserstein_dist_ge_of_lipschitzhave hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure five_vertex_t_star α 0 a := by intro a exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 0 a have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure five_vertex_t_star α 1 b := by intro b exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 1 b have hd0 : 0 < five_vertex_t_star.degree 0 := by decide have hd1 : 0 < five_vertex_t_star.degree 1 := by decide have hμ1 : ∑ a, graph_idle_measure five_vertex_t_star α 0 a = 1 := graph_idle_measure_sum_eq_one five_vertex_t_star α 0 hd0 have hν1 : ∑ b, graph_idle_measure five_vertex_t_star α 1 b = 1 := graph_idle_measure_sum_eq_one five_vertex_t_star α 1 hd1 have hge := graph_wasserstein_dist_ge_of_lipschitz five_vertex_t_star (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) hμ_nonneg hν_nonneg hμ1 hν1 f hf
The values of the test function f at vertices 0, 1, 2, 3, 4 are 2, 1, 0, 3, 3 respectively.
The values d(0, 2) = 2, d(3, 2) = 3, and d(4, 2) = 3 are extracted from the lemma five_vertex_t_star_dist_eq. Vertices 1 and 2 are adjacent (decide), so d(1, 2) = 1 by SimpleGraph.dist_eq_one_iff_adj.mpr. Finally, d(2, 2) = 0 by SimpleGraph.dist_self.
uses
five_vertex_t_star_dist_eq.2.1,SimpleGraph.dist_eq_one_iff_adj.mpr,SimpleGraph.dist_self,five_vertex_t_star_dist_eq.2.2.2.2.1,five_vertex_t_star_dist_eq.2.2.2.2.2have hd00 : five_vertex_t_star.dist 0 2 = 2 := five_vertex_t_star_dist_eq.2.1 have hd12 : five_vertex_t_star.dist 1 2 = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr (by decide) have hd22 : five_vertex_t_star.dist 2 2 = 0 := SimpleGraph.dist_self have hd32 : five_vertex_t_star.dist 3 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.1 have hd42 : five_vertex_t_star.dist 4 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.2
The measure μ_0^α evaluates to α at 0, (1 - α)/3 at 1, 3, 4, and 0 at 2.
By definition of graph_idle_measure, the measure puts mass α at the base vertex 0. The remaining mass 1 - α is distributed equally among the neighbours of 0. Since vertex 0 has degree 3 with neighbours 1, 3, and 4, each neighbour receives mass (1 - α)/3. Vertex 2 is not adjacent to 0, so it receives mass 0. Each case is resolved by simplifying the conditional branches using if_pos and if_neg with decidable adjacency.
uses
if_neg,if_poshave hμ0 : graph_idle_measure five_vertex_t_star α 0 0 = α := by unfold graph_idle_measure; simp have hμ1_val : graph_idle_measure five_vertex_t_star α 0 1 = (1 - α) / 3 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 0 = 3 := by decide rw [hd]; norm_cast have hμ2_val : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] have hμ3_val : graph_idle_measure five_vertex_t_star α 0 3 = (1 - α) / 3 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 0 = 3 := by decide rw [hd]; norm_cast have hμ4_val : graph_idle_measure five_vertex_t_star α 0 4 = (1 - α) / 3 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 0 = 3 := by decide rw [hd]; norm_cast
The measure μ_1^α evaluates to α at 1, (1 - α)/2 at 0 and 2, and 0 at 3 and 4.
Similarly, the idle measure at vertex 1 places mass α on vertex 1. Because vertex 1 has degree 2 with neighbours 0 and 2, each neighbour gets (1 - α)/2. Vertices 3 and 4 are not adjacent to 1 and receive mass 0. These values are confirmed by simplifying the conditionals via if_pos and if_neg.
uses
if_neg,if_poshave hν0_val : graph_idle_measure five_vertex_t_star α 1 0 = (1 - α) / 2 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 1 = 2 := by decide rw [hd]; norm_cast have hν1_val : graph_idle_measure five_vertex_t_star α 1 1 = α := by unfold graph_idle_measure; simp have hν2_val : graph_idle_measure five_vertex_t_star α 1 2 = (1 - α) / 2 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 1 = 2 := by decide rw [hd]; norm_cast have hν3_val : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] have hν4_val : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)]
The difference between the expected values of f under μ_0^α and μ_1^α equals 4/3 - α/3.
Expanding the summations over the 5 vertices using Fin.sum_univ_five and substituting the computed values of f, μ_0^α, and μ_1^α, the expression simplifies via ring normalization to (2α + 7(1 - α)/3) - 1 = 4/3 - α/3.
uses
Fin.sum_univ_fivehave hdiff : ∑ a, f a * graph_idle_measure five_vertex_t_star α 0 a - ∑ b, f b * graph_idle_measure five_vertex_t_star α 1 b = 4 / 3 - α / 3 := by rw [Fin.sum_univ_five, Fin.sum_univ_five] dsimp [f] rw [hd00, hd12, hd22, hd32, hd42] rw [hμ0, hμ1_val, hμ2_val, hμ3_val, hμ4_val] rw [hν0_val, hν1_val, hν2_val, hν3_val, hν4_val] push_cast ring
The Wasserstein distance satisfies 4/3 - α/3 ≤ W(μ_0^α, μ_1^α).
Combining the Kantorovich lower bound W(μ_0^α, μ_1^α) ≥ ∑ f μ_0^α - ∑ f μ_1^α with the calculated expectation difference 4/3 - α/3, linear arithmetic closes the goal.
linarith
graph_idle_measure_nonneg- The idle measure of any vertex in a graph assigns a nonnegative value to every vertex, provided the idle parameter α satisfies 0 ≤ α ≤ 1.
graph_idle_measure_sum_eq_one- The idle measure of a vertex with strictly positive degree sums to 1 over all vertices in the graph.
graph_wasserstein_dist_ge_of_lipschitz- By Kantorovich duality, the Wasserstein distance between two probability measures on a graph is bounded below by the difference of their expectations against any 1-Lipschitz function.
five_vertex_t_star_dist_eq.2.1- In five_vertex_t_star, the shortest path distance between vertex 0 and vertex 2 is 2.
SimpleGraph.dist_eq_one_iff_adj.mpr- In a simple graph, two adjacent vertices have distance 1.
SimpleGraph.dist_self- In a simple graph, the distance from any vertex to itself is 0.
five_vertex_t_star_dist_eq.2.2.2.2.1- In five_vertex_t_star, the shortest path distance between vertex 3 and vertex 2 is 3.
five_vertex_t_star_dist_eq.2.2.2.2.2- In five_vertex_t_star, the shortest path distance between vertex 4 and vertex 2 is 3.
if_neg- A conditional expression evaluates to its second branch when the condition is false.
if_pos- A conditional expression evaluates to its first branch when the condition is true.
Fin.sum_univ_five- The sum of a function over Fin 5 equals the sum of its values at 0, 1, 2, 3, and 4.
- On paper, the graph distances and idle measure values are obtained by direct inspection of the graph; the formal Lean proof evaluates them vertex by vertex using decidability and case analysis on conditionals.
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.
/-- Lower bound for the T-graph by Kantorovich duality with the 1-Lipschitz test function f = dist(·,2), whose values on the vertices are (2,1,0,3,3). -/theorem five_vertex_t_star_wasserstein_ge (α : ℝ) (hα0 : 0 ≤ α) (hα1 : α ≤ 1) : 4 / 3 - α / 3 ≤ graph_wasserstein_dist five_vertex_t_star (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) := by have hconn : five_vertex_t_star.Connected := by decide let f : Fin 5 → ℝ := fun v => (five_vertex_t_star.dist v 2 : ℝ) have hf : ∀ a b, f a - f b ≤ (five_vertex_t_star.dist a b : ℝ) := by intro a b dsimp [f] have := hconn.dist_triangle (u := a) (v := b) (w := 2) have h : (five_vertex_t_star.dist a 2 : ℝ) ≤ (five_vertex_t_star.dist a b : ℝ) + (five_vertex_t_star.dist b 2 : ℝ) := by exact_mod_cast this linarith have hμ_nonneg : ∀ a, 0 ≤ graph_idle_measure five_vertex_t_star α 0 a := by intro a exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 0 a have hν_nonneg : ∀ b, 0 ≤ graph_idle_measure five_vertex_t_star α 1 b := by intro b exact graph_idle_measure_nonneg five_vertex_t_star α hα0 hα1 1 b have hd0 : 0 < five_vertex_t_star.degree 0 := by decide have hd1 : 0 < five_vertex_t_star.degree 1 := by decide have hμ1 : ∑ a, graph_idle_measure five_vertex_t_star α 0 a = 1 := graph_idle_measure_sum_eq_one five_vertex_t_star α 0 hd0 have hν1 : ∑ b, graph_idle_measure five_vertex_t_star α 1 b = 1 := graph_idle_measure_sum_eq_one five_vertex_t_star α 1 hd1 have hge := graph_wasserstein_dist_ge_of_lipschitz five_vertex_t_star (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) hμ_nonneg hν_nonneg hμ1 hν1 f hf have hd00 : five_vertex_t_star.dist 0 2 = 2 := five_vertex_t_star_dist_eq.2.1 have hd12 : five_vertex_t_star.dist 1 2 = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr (by decide) have hd22 : five_vertex_t_star.dist 2 2 = 0 := SimpleGraph.dist_self have hd32 : five_vertex_t_star.dist 3 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.1 have hd42 : five_vertex_t_star.dist 4 2 = 3 := five_vertex_t_star_dist_eq.2.2.2.2.2 have hμ0 : graph_idle_measure five_vertex_t_star α 0 0 = α := by unfold graph_idle_measure; simp have hμ1_val : graph_idle_measure five_vertex_t_star α 0 1 = (1 - α) / 3 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 0 = 3 := by decide rw [hd]; norm_cast have hμ2_val : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] have hμ3_val : graph_idle_measure five_vertex_t_star α 0 3 = (1 - α) / 3 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 0 = 3 := by decide rw [hd]; norm_cast have hμ4_val : graph_idle_measure five_vertex_t_star α 0 4 = (1 - α) / 3 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 0 = 3 := by decide rw [hd]; norm_cast have hν0_val : graph_idle_measure five_vertex_t_star α 1 0 = (1 - α) / 2 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 1 = 2 := by decide rw [hd]; norm_cast have hν1_val : graph_idle_measure five_vertex_t_star α 1 1 = α := by unfold graph_idle_measure; simp have hν2_val : graph_idle_measure five_vertex_t_star α 1 2 = (1 - α) / 2 := by unfold graph_idle_measure rw [if_neg (by decide), if_pos (by decide)] have hd : five_vertex_t_star.degree 1 = 2 := by decide rw [hd]; norm_cast have hν3_val : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] have hν4_val : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] have hdiff : ∑ a, f a * graph_idle_measure five_vertex_t_star α 0 a - ∑ b, f b * graph_idle_measure five_vertex_t_star α 1 b = 4 / 3 - α / 3 := by rw [Fin.sum_univ_five, Fin.sum_univ_five] dsimp [f] rw [hd00, hd12, hd22, hd32, hd42] rw [hμ0, hμ1_val, hμ2_val, hμ3_val, hμ4_val] rw [hν0_val, hν1_val, hν2_val, hν3_val, hν4_val] push_cast ring linarith