graph_lly_curvature_lower_bound_le_of_dist_eq
The scale-i lower curvature bound is a lower bound for κ_LLY at any pair at distance i: κ_LLY^(i)(G) ≤ κ_LLY(x,y) whenever d(x,y) = i.
Statement
theorem graph_lly_curvature_lower_bound_le_of_dist_eq {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (i : ℕ) (h : G.dist x y = i) : graph_lly_curvature_lower_bound G i ≤ graph_lly_curvature G x y
- Source
- step towards exists_dist_three_lly_curvature_le_cut
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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 − α).
The proof, explained
By definition, the scale-i lower curvature bound κ_LLY^(i)(G) is the infimum of the set of curvatures κ_LLY(a, b) over all vertex pairs at graph distance i. Because the graph has finitely many vertices, the set of all pairwise curvatures is finite, making this distance-i subset finite and therefore bounded below. Since the vertices x and y are at distance i, their curvature belongs to this set, and the infimum is at most any element of the set.
Unfolding the definition, the set of curvatures achieved by pairs at distance i is contained in the range of the curvature function on all vertex pairs V × V.
By definition, `graph_lly_curvature_lower_bound G i` is the infimum of the set S = {κ : ℝ | ∃ a b, d(a, b) = i ∧ κ_LLY(a, b) = κ}. Any κ in this set is the curvature of some pair (a, b) ∈ V × V, so S is a subset of the range of (u, v) ↦ κ_LLY(u, v).
unfold graph_lly_curvature_lower_bound have hS : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ 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⟩
The set of curvatures achieved by pairs at distance i is finite.
Since the vertex type V is finite, the product V × V is finite. By `Set.finite_range`, the range of the curvature function on V × V is finite. Because the set of distance-i curvatures is a subset of this range, `Set.Finite.subset` implies it is also finite.
uses
Set.Finite.subset,Set.finite_rangehave hfin : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ graph_lly_curvature G x y = κ}).Finite := Set.Finite.subset (Set.finite_range _) hSThe scale-i lower curvature bound is at most κ_LLY(x, y).
A finite set of real numbers is bounded below. Since d(x, y) = i, κ_LLY(x, y) is an element of the set defining the lower bound. By `csInf_le`, the infimum of a set bounded below is less than or equal to any of its elements.
uses
csInf_leexact csInf_le hfin.bddBelow ⟨x, y, h, rfl⟩
Set.Finite.subset- A subset of a finite set is finite.
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 the set.
- The fact that any finite set of real numbers is bounded below is supplied in line 14 via the dot-notation method `hfin.bddBelow` (`Set.Finite.bddBelow`).
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 infimum defining κ_LLY^(i)(G) is attained-below by every distance-i pair. -/theorem graph_lly_curvature_lower_bound_le_of_dist_eq {V : Type} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (x y : V) (i : ℕ) (h : G.dist x y = i) : graph_lly_curvature_lower_bound G i ≤ graph_lly_curvature G x y := by unfold graph_lly_curvature_lower_bound have hS : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ 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⟩ have hfin : ({κ : ℝ | ∃ x y, G.dist x y = i ∧ graph_lly_curvature G x y = κ}).Finite := Set.Finite.subset (Set.finite_range _) hS exact csInf_le hfin.bddBelow ⟨x, y, h, rfl⟩