AFTD Auto-Formalizing Theoretical Domains

chvatal_hanson_bound

def

For natural numbers D and M, the Chvátal-Hanson edge bound on ℕ is D * M + (D / 2) * (M / ((D + 1) / 2)), using truncated natural number division.

Statement

def chvatal_hanson_bound (D M : ℕ) : ℕ
Defined in
arXiv:2611.01259 eq. (12)
Verified
07 Nov 2026
Axioms
none listed

Read back from the Lean

The function chvatal_hanson_bound takes two natural numbers, D and M, and returns the natural number D * M + (D / 2) * (M / ((D + 1) / 2)), where all division operations are natural number (truncating/floor) division.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The Chvátal-Hanson bound on the number of edges under degree and matching constraints. -/
def chvatal_hanson_bound (D M : ℕ) : ℕ := D * M + (D / 2) * (M / ((D + 1) / 2))
See it in the graphDiscuss this resultChallenge it