The standard Erdős girth conjecture (girth with edges)
DefinitionPivotADO_OneHop_Supplement_ErdosGirthThe standard Erdős girth conjecture states that for every integer there are graphs with girth at least and edges, where is the number of vertices. It is encoded as: for every integer there is a constant such that for every threshold there are and a simple graph on vertices with
By the Moore bound, a graph of girth at least has edges, so the conjectured count matches the Moore bound up to a constant factor. This conjecture is the hypothesis of the hopset lower bounds (Theorems 3 and 4). It differs from the constant-degree conjecture (Conjecture 1): it asks for no regularity, no bounded degree and no logarithmic girth.
Formalization Note This is an open conjecture, defined as a proposition to be used as a hypothesis; no axiom or proof is supplied. Vertices are ; girth is Mathlib's extended girth egirth, which is for acyclic graphs. The constant depends only on and is chosen before ; graphs are required only for arbitrarily large , the weakest reading of the -family.
import Definitions.Def_PivotADO_OneHop_Geometry
set_option autoImplicit false
open scoped Classical
namespace PivotADO.OneHop.Supplement
open PivotADO.OneHop
/-- The standard Erdős girth conjecture, as stated in Kadria–Roditty, STOC 2027 submission
#584 (October 2026), §6, p.24 (PDF 25) and Remark 3, p.31 (PDF 32): for every integer
`t ≥ 1` there are graphs of girth at least `2t + 2` with `Ω(N^{1+1/t})` edges. The
constant `a` depends only on `t` and precedes `N`; graphs are required for arbitrarily
large `N`. An acyclic graph has girth `⊤`. This is an open hypothesis, not an axiom. -/
def ErdosGirthConjecture : Prop :=
∀ t : ℕ, 1 ≤ t → ∃ a : ℝ, 0 < a ∧
∀ N₀ : ℕ, ∃ (N : ℕ) (B : SimpleGraph (Fin N)),
N₀ ≤ N ∧ ((2 * t + 2 : ℕ) : ℕ∞) ≤ B.egirth ∧
a * (N : ℝ) ^ (1 + 1 / (t : ℝ)) ≤ (edgeCount B : ℝ)
end PivotADO.OneHop.Supplement