Asymptotic degree-diameter problem resolved for fixed diameter
The maximum order of a graph with maximum degree d and diameter k satisfies n_k(d)/d^k tending to 1 as d grows, for every fixed k, resolving the asymptotic form of a question open since 1978, with a Lean 4 formalization.
- Lab
- Independent
- Model
- GPT-5.6 Pro
- Field
- Mathematics
- Date
- 2026-08-04
- Human collaborators
- Wouter Cames van Batenburg, Samuel Korsky
- Problem posed
- 1978 · open 48 yrs
Sources
Original work
Independent commentary
What was found
The Moore bound caps the order of a graph of maximum degree d and diameter k at roughly d^k. Whether that cap is asymptotically attainable for fixed diameter was open: Bannai and Ito had settled which exact Moore graphs exist, and constructions had approached the bound only for small diameters. This proves the limit of n_k(d)/d^k is 1 for every fixed k, with a companion lower bound on the edge variant and a tight asymptotic for the bipartite version. The paper carries an explicit tool and computational resource disclosure: GPT-5.6 Pro was used in exploratory brainstorming directed by the authors, who formulated the required parameter scale and proposed higher-rank spherical buildings as the geometric setting. The model suggested splitting complete flags into their odd- and even-rank subflags, initially in connection with the edge problem; that suggestion became the halved-flag construction carrying the main theorem, and the graph is named for it.
Novelty check
The degree-diameter problem is a named and long-tracked question in extremal graph theory, surveyed by Bermond and Bollobas (1981) and with Bollobas's 1978 Extremal Graph Theory as the reference point for the asymptotic question; Bachraty, Siagiova and Siran had approached the bound for diameter three in 2019. The authors note that after completing the work they learned the projective-plane construction of an earlier paper shares the rank-2 incidence graph underlying the k=1 case of theirs, and state the higher-rank construction and its odd-even routing argument are independent and different. No prior proof of the general asymptotic result appears.
Caveats and known objections
Not peer-reviewed. Autonomy is graded ai-assisted, the weaker defensible reading, because the disclosure is explicit that the authors developed the suggestion into the construction, formulated and verified all mathematical arguments, and take full responsibility for the content; the model's contribution was one structural idea during brainstorming. Generative tools also assisted with the Lean formalization. The Lean repository is author-produced and had no independent audit at announcement.
Independent checks
vibemathed.com curator check of the Lean repository: checked at commit 32beb227: DegreeDiameter.theorem_1_1 states Theorem 1.1 itself and corollary_1_2 states Corollary 1.2, neither a weakened lemma, with a second independent route proved alongside each; no sorry or admit in the sources · link ↗
Disagree with these grades?
Bring a citation: a grade moves on evidence, not on argument.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Formally verified and AI-assisted.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Graded formally verified for verification and ai-assisted for autonomy. What these mean.
Cite this entry
whataifound.org. (2026). Asymptotic degree-diameter problem resolved for fixed diameter. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2026-08-04-moore-boundBibTeX
@misc{whataifound-independent-2026-bound,
title = {Asymptotic degree-diameter problem resolved for fixed diameter},
author = {{whataifound.org}},
year = {2026},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Independent. Verification: Formally verified. Autonomy: AI-assisted.},
url = {https://whataifound.org/finding/2026-08-04-moore-bound}
}