graph_lly_curvature_comm
The Lin–Lu–Yau curvature is symmetric: κ_LLY(x, y) = κ_LLY(y, x).
Statement
theorem graph_lly_curvature_comm {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) : graph_lly_curvature G x y = graph_lly_curvature G y x
- Source
- Helper for the refutation of OP-165 (arXiv:2610.10559, after Theorem 1.4).
- Verified
- 10 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- graph_wasserstein_dist_commThe Wasserstein distance is symmetric: W(μ, ν) = W(ν, μ).
- 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 3
- not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- graph_lly_curvature_pos_of_threeIn a finite connected graph with exactly three vertices x, y, z, every edge xy has positive Lin–Lu–Yau curvature.
- exists_dist_three_lly_curvature_le_cut_interiorIf x lies in the interior of X (all its neighbours in X) and y in the interior of Xᶜ, and d(x,y) = 3, then κ_LLY(x,y) ≤ 2·|E(X,Xᶜ)| / (3…
The proof, explained
The Lin–Lu–Yau curvature κ_LLY(x, y) is defined as the limit as α → 1⁻ of the normalized Ollivier curvature κ_α(x, y) / (1 - α). After unfolding the definitions, equality of the limits reduces by functional extensionality to pointwise equality of the quotient expressions for every α. This pointwise symmetry holds immediately because both the graph distance d(x, y) and the Wasserstein distance between the idle measures are symmetric.
The equality of Lin–Lu–Yau curvatures is expanded in terms of limits of Ollivier curvatures.
Unfolding the definitions of Lin–Lu–Yau curvature and Ollivier curvature rewrites each side into the limit as α → 1⁻ of (1 - W(m_x^α, m_y^α) / d(x, y)) / (1 - α).
unfold graph_lly_curvature graph_ollivier_curvatureIt suffices to show that the expressions coincide pointwise for each parameter α.
By congruence of limits and functional extensionality over α, the two limits agree if their underlying functions agree at every α.
congr 1 funext α
The expressions are identical for each α, concluding the proof.
Rewriting with the symmetry of the Wasserstein distance (graph_wasserstein_dist_comm) and the symmetry of the graph distance (SimpleGraph.dist_comm) makes the two sides syntactically identical.
uses
graph_wasserstein_dist_comm,SimpleGraph.dist_commrw [graph_wasserstein_dist_comm, SimpleGraph.dist_comm]
graph_wasserstein_dist_comm- The Wasserstein distance on a graph is symmetric: W(μ, ν) = W(ν, μ).
SimpleGraph.dist_comm- The shortest-path distance between vertices in a simple graph is symmetric: d(u, v) = d(v, u).
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_lly_curvature_comm {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) : graph_lly_curvature G x y = graph_lly_curvature G y x := by unfold graph_lly_curvature graph_ollivier_curvature congr 1 funext α rw [graph_wasserstein_dist_comm, SimpleGraph.dist_comm]