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
- 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_positive_edge_connectivity_threshold_threec(3) = 0: every connected graph on 3 vertices has positive Lin–Lu–Yau curvature on every edge, whatever its edge-connectivity.
- not_forall_lly_positive_edge_connectivity_threshold_eq_ceilIt is not true that c(n) = ⌈2n/3 − 1⌉ for all n ≥ 3. Already c(3) = 0, since every connected graph on 3 vertices (the path and the…
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}