VibeMathedMath problems solved by AI
Sign in

Asymptotically attaining the Moore bound

For positive integers dd and kk, let nk(d)n_k(d) be the maximum order of a graph of maximum degree at most dd and diameter at most kk. It is shown that lim⁡d→∞nk(d)dk=1\lim_{d \to \infty}\frac{n_k(d)}{d^k} = 1 for every fixed kk, thereby resolving the asymptotic degree-diameter problem for fixed diameter. Also proved a similar lower bound on the edge-variant of the problem, and a tight asymptotic for the bipartite variant of the edge problem.

Result
Proved
Status
Resolved
AI contribution
AI-assisted
Method
Construction
Field
Combinatorics
Posed by
—
Year posed
1960
Years open
66y
Solved
2026-08-04
Model
GPT-5.6
Vendor
OpenAI
Collaborators
Wouter Cames van Batenburg, Samuel Korsky
Verification
Lean-verified
Publication
Preprint
Significance
—
Disclosed cost
—
Wikipedia
No dedicated article

What the AI did

Contributed ideas in a discussion about the early versions of the construction related to the edge variant of the problem.

Verification

Links to a lean repository

Sources

Asymptotically attaining the Moore bound

Submitted by GoldenMongoose827

Changelog5 changes
  • Rasmus Lindahlchanged More links from “paper: Asymptotically attaining the Moore bound | https://arxiv.org/pdf/2608.03965” to “code: Asymptotically attaining the Moore bound — Lean 4 formalization | https://github.com…”
  • Rasmus Lindahlset More links to “paper: Asymptotically attaining the Moore bound | https://arxiv.org/pdf/2608.03965”
  • Rasmus Lindahlchanged Statement from “For positive integers $d$ and $k$, let $n_k(d)$ be the maximum order of a graph of maximum…” to “For positive integers $d$ and $k$, let $n_k(d)$ be the maximum order of a graph of maximum…”
  • Rasmus Lindahlapproved this entry
  • GoldenMongoose827submitted this entry

Discussion