ProbXiv
sign in

Asymptotically attaining the Moore bound

Combinatorics · posed by Béla Bollobás, 1978 · solved

1 attempt · 1 machine check

Statement

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.

Context

Settles two conjectures. Theorem 1.1 proves Bollobas's asymptotic degree-diameter conjecture, in the stronger liminf form rather than the conjectured limsup. Corollary 1.2 proves Conjecture 3 of Cambie, Cames van Batenburg, de Joannis de Verclos and Kang on the edge variant, again in the stronger liminf form, and is tight for bipartite graphs.

The degree-diameter problem carries its own Electronic Journal of Combinatorics dynamic survey (DS14, Miller and Siran), and the asymptotic form is Bollobas's own conjecture, recorded in Extremal Graph Theory and Random Graphs. It stood 48 years with the asymptotic known only for k in {2, 3, 5}, through generalized polygons, and the best uniform coefficient for large k was 0.629.

People

begin a project on this problem →

Attempts

1 attempt

No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

review this attempt →

  • #1

    Attempt 1

    constructionGPT-5.6 with Wouter Cames van Batenburg, Samuel Korsky ·
    AI involvement
    ai co developed
    — a person and a model developed the result together.
    models
    GPT-5.6
    people
    Wouter Cames van Batenburg, Samuel Korsky

    The paper's tool disclosure states that GPT-5.6 Pro, used in exploratory brainstorming directed by the authors, suggested splitting complete flags into their odd- and even-rank subflags. That suggestion arose in connection with the edge problem but became the halved-flag construction carrying Theorem 1.1 itself, the graph being named for it. The authors developed it, formulated and verified every argument, and take full responsibility. Generative AI also assisted the Lean 4 formalization.

    Reviews

    1 machine check

    No person has reviewed this attempt. 1 machine check below — a machine check is not human verification.

    • Machine check · not human verification

      machine: correct

      Recorded from Lean ·

      scope Lean formalization of the result

      Lean 4 formalization at github.com/woutercvb/wewantmoore, checked by the site on 2026-08-06 at commit 32beb227. DegreeDiameter.theorem_1_1 states Theorem 1.1 itself, as a limit of nKD k d / d^k, and corollary_1_2 states Corollary 1.2; neither is a weakened lemma, and a second independent route is proved alongside each under _via_big_cell. No sorry or admit appears in the sources, and the committed axiom audit shows both final theorems resting only on propext, Classical.choice and Quot.sound. That audit is not taken on trust: the repository's CI builds the project from the pinned toolchain and manifest, regenerates the axiom and dependency reports, and fails if they differ from the committed ones. It passes on this commit. The formalization was itself AI-assisted, per the paper's disclosure, and the authors note it is not a line-by-line transcription: k = 1 is handled by the same construction rather than by complete graphs, and the order and cap asymptotics go through leading terms rather than the displayed O_k(q^-1) estimates.

      No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.

    Discussion of this attempt

    no comments

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.

Discussion

no comments

Nothing has been said about this problem yet.

Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.