graph_lly_curvature_lower_bound_two_le_one
For every finite connected graph G, the lower Lin–Lu–Yau curvature bound at scale 2 is at most 1: κ_LLY^(2)(G) ≤ 2/2 = 1.
Statement
theorem graph_lly_curvature_lower_bound_two_le_one {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) : graph_lly_curvature_lower_bound G 2 ≤ 1
- Source
- step towards edge_connectivity_ge_min_degree_mul_lly_lower_bound_two
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- graph_lly_curvature_le_two_div_distFor distinct vertices x, y of a finite connected graph, κ_LLY(x, y) ≤ 2/d(x, y).
- graph_lly_curvature_lower_boundThe lower Lin–Lu–Yau curvature bound at scale i: κ_LLY^(i)(G) = inf { κ_LLY(x, y) : d(x, y) = i }.
- graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
- Used by 1
- edge_connectivity_ge_min_degree_mul_lly_lower_bound_twoEvery finite connected graph of diameter 2 has κ'(G) ≥ δ(G) · κ_LLY^(2)(G).
The proof, explained
The scale-2 Lin–Lu–Yau curvature lower bound of a graph G is the infimum of κ_LLY(x, y) over all pairs of vertices at distance 2. If no pair of vertices is at distance 2, the set is empty, so its infimum is 0 ≤ 1 by Lean's convention for the real numbers. Otherwise, there exists a pair x, y with d(x, y) = 2; since the vertex set is finite, the set of curvatures is finite and bounded below, so its infimum is at most κ_LLY(x, y). Because d(x, y) = 2 implies x ≠ y, the general upper bound κ_LLY(x, y) ≤ 2 / d(x, y) = 1 applies, and transitivity completes the proof.
Unfold the definition of the scale-2 curvature bound and split into cases based on whether any pair of vertices has distance 2.
By definition, graph_lly_curvature_lower_bound G 2 is the infimum of the set of curvatures κ_LLY(x, y) over all pairs of vertices at distance 2. We use Set.eq_empty_or_nonempty to separate the cases where this set of curvatures is empty or nonempty.
uses
Set.eq_empty_or_nonemptyunfold graph_lly_curvature_lower_bound rcases Set.eq_empty_or_nonempty {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} with he | hne_set
If no two vertices are at distance 2, the scale-2 curvature lower bound is at most 1.
When the set of distance-2 curvatures is empty, its infimum in ℝ evaluates to 0 by Real.sInf_empty. Arithmetic simplification (norm_num) then confirms 0 ≤ 1.
uses
Real.sInf_empty· rw [he, Real.sInf_empty] norm_num
In the nonempty case, the infimum is at most the curvature κ_LLY(x, y) of some pair of vertices at distance 2.
Because the set is nonempty, there exist vertices x and y with G.dist x y = 2. Since V is a finite type, the Cartesian product V × V is finite, and the range of the curvature function on V × V is finite by Set.finite_range. The set of scale-2 curvatures is a subset of this range, hence finite and bounded below. By csInf_le, the infimum is bounded above by κ_LLY(x, y).
uses
Set.finite_range,csInf_le· rcases hne_set with ⟨_, x, y, hxy, rfl⟩ have hfin : ({κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} : Set ℝ).Finite := by have : {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} ⊆ Set.range (fun p : V × V => graph_lly_curvature G p.1 p.2) := by rintro _ ⟨a, b, -, rfl⟩ exact ⟨(a, b), rfl⟩ exact (Set.finite_range _).subset this have hle := csInf_le hfin.bddBelow ⟨x, y, hxy, rfl⟩
The curvature κ_LLY(x, y) between the chosen vertices is at most 1.
Since G.dist x y = 2, x ≠ y (as G.dist x x = 0 ≠ 2). Applying graph_lly_curvature_le_two_div_dist to the distinct vertices x and y in the connected graph G gives κ_LLY(x, y) ≤ 2 / G.dist x y. Substituting G.dist x y = 2 and simplifying 2 / 2 yields κ_LLY(x, y) ≤ 1.
uses
graph_lly_curvature_le_two_div_disthave hne : x ≠ y := by rintro rfl simp at hxy have hcurv := graph_lly_curvature_le_two_div_dist G hG x y hne rw [hxy] at hcurv norm_num at hcurv
The scale-2 curvature lower bound of G is at most 1.
Combining the inequality sInf {κ | ...} ≤ κ_LLY(x, y) with κ_LLY(x, y) ≤ 1 via transitivity (le_trans) establishes that graph_lly_curvature_lower_bound G 2 ≤ 1.
uses
le_transexact le_trans hle hcurv
Set.eq_empty_or_nonempty- Every set is either empty or nonempty.
Real.sInf_empty- The infimum of the empty set of real numbers is 0.
Set.finite_range- The range of a function defined on a finite domain is finite.
csInf_le- In a conditionally complete lattice such as ℝ, the infimum of a set bounded below is less than or equal to any element of that set.
graph_lly_curvature_le_two_div_dist- In any finite connected graph, the Lin–Lu–Yau curvature between distinct vertices x and y is at most 2 / d(x, y).
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
- In Lean's real analysis library, the infimum of the empty set in ℝ (Real.sInf_empty) is defined to be 0 by convention, so sInf ∅ ≤ 1 holds immediately without requiring the graph to have diameter at least 2.
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.
/-- The scale-2 curvature bound is at most 1, since κ_LLY(x,y) ≤ 2/d(x,y) = 1 for d(x,y)=2. -/theorem graph_lly_curvature_lower_bound_two_le_one {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hG : G.Connected) : graph_lly_curvature_lower_bound G 2 ≤ 1 := by unfold graph_lly_curvature_lower_bound rcases Set.eq_empty_or_nonempty {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} with he | hne_set · rw [he, Real.sInf_empty] norm_num · rcases hne_set with ⟨_, x, y, hxy, rfl⟩ have hfin : ({κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} : Set ℝ).Finite := by have : {κ | ∃ x y : V, G.dist x y = 2 ∧ graph_lly_curvature G x y = κ} ⊆ Set.range (fun p : V × V => graph_lly_curvature G p.1 p.2) := by rintro _ ⟨a, b, -, rfl⟩ exact ⟨(a, b), rfl⟩ exact (Set.finite_range _).subset this have hle := csInf_le hfin.bddBelow ⟨x, y, hxy, rfl⟩ have hne : x ≠ y := by rintro rfl simp at hxy have hcurv := graph_lly_curvature_le_two_div_dist G hG x y hne rw [hxy] at hcurv norm_num at hcurv exact le_trans hle hcurv