AFTD Auto-Formalizing Theoretical Domains

lly_positive_edge_connectivity_threshold

deforiginal

c(n): the smallest natural number k such that every connected simple graph on n vertices with edge-connectivity at least k has positive Lin–Lu–Yau curvature on every edge.

Statement

noncomputable def lly_positive_edge_connectivity_threshold (n : ℕ) : ℕ
Related work
Open-problem entry OP-165 after arXiv:2610.10559 (Edge-Connectivity versus Lin--Lu--Yau Curvature), Theorems 1.3–1.4 (Theorem 1.3 gives c(n) ≤ ⌈2n/3 − 1⌉).
Verified
10 Oct 2026
Axioms
none listed
Built on 2
  • graph_edge_connectivityThe edge-connectivity κ'(G): the largest k such that removing fewer than k edges never disconnects G (0 for a disconnected graph; 0 also…
  • graph_lly_curvatureThe Lin–Lu–Yau curvature κ_LLY(x, y) = lim_{α → 1⁻} κ_α(x, y)/(1 − α).
Used by 3

Lean source view module on GitHub

/-- `c(n)`: least `k` such that every connected graph on `n` vertices with edge-connectivity `≥ k` has positive Lin–Lu–Yau curvature on all edges. -/
noncomputable def lly_positive_edge_connectivity_threshold (n : ℕ) : ℕ :=
  sInf {k | ∀ G : SimpleGraph (Fin n), ∀ [DecidableRel G.Adj], G.Connected →
    k ≤ graph_edge_connectivity G → ∀ x y, G.Adj x y → 0 < graph_lly_curvature G x y}
See it in the graphDiscuss this resultChallenge it