five_vertex_t_star_wasserstein_le
For 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, π(4,1)=(1−α)/3 shows W(μ_0^α, μ_1^α) ≤ 4/3 − α/3.
Statement
theorem five_vertex_t_star_wasserstein_le (α : ℝ) (hα0 : 2 / 5 ≤ α) (hα1 : α ≤ 1) :
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- Source
- step towards lly_positive_edge_connectivity_threshold_five
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_le_of_planThe Wasserstein distance is at most the cost of any transport plan.
- 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 theorem proves that on the 5-vertex T-graph, the 1-Wasserstein distance between the lazy random walk measures μ_0^α and μ_1^α is at most 4/3 - α/3 for any α ∈ [2/5, 1]. This is shown by constructing an explicit transport plan π with six nonzero entries. The proof checks entrywise nonnegativity using the bound α ≥ 2/5, verifies that the row and column marginals of π equal μ_0^α and μ_1^α by exhausting vertices in Fin 5, and evaluates the transport cost to be exactly 4/3 - α/3.
An explicit candidate transport plan π : Fin 5 → Fin 5 → ℝ is defined.
The coupling is assigned six nonzero values: π(0,0) = (1 - α)/2, π(0,1) = (5α - 2)/3, π(0,2) = (1 - α)/6, π(1,2) = (1 - α)/3, π(3,1) = (1 - α)/3, and π(4,1) = (1 - α)/3, with π(a,b) = 0 for all other pairs (a,b).
let π : Fin 5 → Fin 5 → ℝ := fun a b => if a = 0 ∧ b = 0 then (1 - α) / 2 else if a = 0 ∧ b = 1 then (5 * α - 2) / 3 else if a = 0 ∧ b = 2 then (1 - α) / 6 else if a = 1 ∧ b = 2 then (1 - α) / 3 else if a = 3 ∧ b = 1 then (1 - α) / 3 else if a = 4 ∧ b = 1 then (1 - α) / 3 else 0
Every entry of the transport plan π is nonnegative.
The proof exhaustively inspects all 25 pairs (a,b) ∈ Fin 5 × Fin 5 using `fin_cases`. Nonnegativity of the nonzero entries follows from 2/5 ≤ α ≤ 1 via linear arithmetic (`linarith`), since (1 - α) ≥ 0 and (5α - 2) ≥ 0.
have hπ : ∀ a b, 0 ≤ π a b := by intro a b fin_cases a <;> fin_cases b <;> { dsimp [π]; linarith }
The row sums of π match the first idle measure: ∑_b π(a, b) = μ_0^α(a) for all a ∈ Fin 5.
Exhausting a ∈ {0, 1, 2, 3, 4}, the sum over b is expanded using `Fin.sum_univ_five`. In the T-graph, vertex 0 has degree 3 with neighbors 1, 3, 4. Thus μ_0^α puts mass α on 0, mass (1 - α)/3 on each neighbor 1, 3, 4, and mass 0 on vertex 2. Evaluating `graph_idle_measure` and simplifying ring expressions confirms that the row sums match these probabilities in every case.
uses
Fin.sum_univ_five,if_neg,if_poshave h1 : ∀ a, ∑ b, π a b = graph_idle_measure five_vertex_t_star α 0 a := by intro a fin_cases a · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 0 0 = α := by unfold graph_idle_measure; simp rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring
The column sums of π match the second idle measure: ∑_a π(a, b) = μ_1^α(b) for all b ∈ Fin 5.
Exhausting b ∈ {0, 1, 2, 3, 4}, the sum over a is expanded using `Fin.sum_univ_five`. In the T-graph, vertex 1 has degree 2 with neighbors 0 and 2. Thus μ_1^α puts mass α on 1, mass (1 - α)/2 on each of 0 and 2, and mass 0 on vertices 3 and 4. In each case, evaluating `graph_idle_measure` and simplifying confirms that the column sum equals the required marginal weight.
uses
Fin.sum_univ_five,if_neg,if_poshave h2 : ∀ b, ∑ a, π a b = graph_idle_measure five_vertex_t_star α 1 b := by intro b fin_cases b · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 1 1 = α := by unfold graph_idle_measure; simp rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] rw [this]; ring
The total transport cost ∑_{a, b} d(a, b) π(a, b) equals 4/3 - α/3.
The graph distances between the relevant pairs are recorded: d(0,0)=0, d(0,1)=1, d(0,2)=2, d(1,2)=1, d(3,1)=2, and d(4,1)=2. Expanding the double sum over Fin 5 × Fin 5 with `Fin.sum_univ_five` and substituting these distances into ∑_{a, b} d(a,b) π(a,b) gives 1 · (5α - 2)/3 + 2 · (1 - α)/6 + 1 · (1 - α)/3 + 2 · (1 - α)/3 + 2 · (1 - α)/3, which simplifies via `ring` to 4/3 - α/3.
uses
SimpleGraph.dist_self,five_vertex_t_star_dist_eq.1,five_vertex_t_star_dist_eq.2.1,SimpleGraph.dist_eq_one_iff_adj.mpr,five_vertex_t_star_dist_eq.2.2.1,five_vertex_t_star_dist_eq.2.2.2.1,Fin.sum_univ_fivehave hcost : (∑ a, ∑ b, (five_vertex_t_star.dist a b : ℝ) * π a b) = 4 / 3 - α / 3 := by have hd00 : five_vertex_t_star.dist 0 0 = 0 := SimpleGraph.dist_self have hd01 : five_vertex_t_star.dist 0 1 = 1 := five_vertex_t_star_dist_eq.1 have hd02 : 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 hd31 : five_vertex_t_star.dist 3 1 = 2 := five_vertex_t_star_dist_eq.2.2.1 have hd41 : five_vertex_t_star.dist 4 1 = 2 := five_vertex_t_star_dist_eq.2.2.2.1 repeat rw [Fin.sum_univ_five] dsimp [π] rw [hd00, hd01, hd02, hd12, hd31, hd41] push_cast ring
The Wasserstein distance W(μ_0^α, μ_1^α) on the T-graph is at most 4/3 - α/3.
By `graph_wasserstein_dist_le_of_plan`, the Wasserstein distance is bounded by the cost of any valid coupling whose marginals match μ_0^α and μ_1^α. Applying this theorem to π using the verified nonnegativity, row sums, and column sums, and rewriting with the calculated cost, yields the upper bound.
uses
graph_wasserstein_dist_le_of_planhave h_bound := graph_wasserstein_dist_le_of_plan five_vertex_t_star (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) π hπ h1 h2 rw [hcost] at h_bound exact h_bound
Fin.sum_univ_five- For any function f on Fin 5 with values in an additive commutative monoid, its sum over Fin 5 is f 0 + f 1 + f 2 + f 3 + f 4.
if_neg- If a proposition c is false, then (if c then t else e) reduces to e.
if_pos- If a proposition c is true, then (if c then t else e) reduces to t.
SimpleGraph.dist_self- In any simple graph, the shortest-path distance from any vertex to itself is 0.
SimpleGraph.dist_eq_one_iff_adj.mpr- If two vertices in a simple graph are adjacent, the distance between them is 1.
five_vertex_t_star_dist_eq.1- In the 5-vertex T-graph, the distance between vertices 0 and 1 is 1.
five_vertex_t_star_dist_eq.2.1- In the 5-vertex T-graph, the distance between vertices 0 and 2 is 2.
five_vertex_t_star_dist_eq.2.2.1- In the 5-vertex T-graph, the distance between vertices 3 and 1 is 2.
five_vertex_t_star_dist_eq.2.2.2.1- In the 5-vertex T-graph, the distance between vertices 4 and 1 is 2.
graph_wasserstein_dist_le_of_plan- Any nonnegative transport plan π whose marginals match μ and ν provides an upper bound on the graph Wasserstein distance: W(μ, ν) ≤ ∑_{a, b} d(a, b) π(a, b).
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.
/-- Upper bound for the T-graph by an explicit transport plan. NOTE: the plan proposed in the earlier escalation was infeasible (its column-1 sum is (4α−1)/3, not α). The corrected table is: π(0,0)=(1−α)/2, π(0,1)=(5α−2)/3, π(0,2)=(1−α)/6, π(1,2)=(1−α)/3, π(3,1)=(1−α)/3, π(4,1)=(1−α)/3, everything else 0; it needs α ≥ 2/5 and has cost exactly 4/3 − α/3. -/theorem five_vertex_t_star_wasserstein_le (α : ℝ) (hα0 : 2 / 5 ≤ α) (hα1 : α ≤ 1) : 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 := by let π : Fin 5 → Fin 5 → ℝ := fun a b => if a = 0 ∧ b = 0 then (1 - α) / 2 else if a = 0 ∧ b = 1 then (5 * α - 2) / 3 else if a = 0 ∧ b = 2 then (1 - α) / 6 else if a = 1 ∧ b = 2 then (1 - α) / 3 else if a = 3 ∧ b = 1 then (1 - α) / 3 else if a = 4 ∧ b = 1 then (1 - α) / 3 else 0 have hπ : ∀ a b, 0 ≤ π a b := by intro a b fin_cases a <;> fin_cases b <;> { dsimp [π]; linarith } have h1 : ∀ a, ∑ b, π a b = graph_idle_measure five_vertex_t_star α 0 a := by intro a fin_cases a · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 0 0 = α := by unfold graph_idle_measure; simp rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 0 2 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring have h2 : ∀ b, ∑ a, π a b = graph_idle_measure five_vertex_t_star α 1 b := by intro b fin_cases b · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 1 1 = α := by unfold graph_idle_measure; simp rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : 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 rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 1 3 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] rw [this]; ring · rw [Fin.sum_univ_five]; dsimp [π] have : graph_idle_measure five_vertex_t_star α 1 4 = 0 := by unfold graph_idle_measure rw [if_neg (by decide), if_neg (by decide)] rw [this]; ring have hcost : (∑ a, ∑ b, (five_vertex_t_star.dist a b : ℝ) * π a b) = 4 / 3 - α / 3 := by have hd00 : five_vertex_t_star.dist 0 0 = 0 := SimpleGraph.dist_self have hd01 : five_vertex_t_star.dist 0 1 = 1 := five_vertex_t_star_dist_eq.1 have hd02 : 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 hd31 : five_vertex_t_star.dist 3 1 = 2 := five_vertex_t_star_dist_eq.2.2.1 have hd41 : five_vertex_t_star.dist 4 1 = 2 := five_vertex_t_star_dist_eq.2.2.2.1 repeat rw [Fin.sum_univ_five] dsimp [π] rw [hd00, hd01, hd02, hd12, hd31, hd41] push_cast ring have h_bound := graph_wasserstein_dist_le_of_plan five_vertex_t_star (graph_idle_measure five_vertex_t_star α 0) (graph_idle_measure five_vertex_t_star α 1) π hπ h1 h2 rw [hcost] at h_bound exact h_bound