Asymptotic Moore bound in the degree–diameter problem
Follow the latest progress by email.
For fixed positive diameter k, how many vertices can a graph of maximum degree d and diameter at most k have as d tends to infinity? The Moore bound is dᵏ+Oₖ(dᵏ⁻¹); the target is a construction with nₖ(d)/dᵏ→1.
Why it matters and what counts as progress
Why it matters: Matching the Moore bound asymptotically would settle the degree–diameter problem at every fixed diameter.
What counts as progress: Construct graphs asymptotically attaining the Moore bound for additional diameters or prove the limit for every fixed k.
How the problem developed
- 2002 · Bound [1]
Noga Alon, Shlomo Hoory and Nathan Linial Extended the Moore bound from regular graphs to irregular graphs in the degree-girth problem.
- 4 Aug 2026 · Reported claim [2]
Wouter Cames van Batenburg and Samuel Korsky Proved that for each fixed diameter k, the maximum order nₖ(d) of a graph with maximum degree d satisfies nₖ(d)/dᵏ→1 as d→∞.
AI contribution
Asymptotically attaining the Moore bound
For every fixed positive diameter k, the maximum number nₖ(d) of vertices in a graph of maximum degree at most d and diameter at most k satisfies nₖ(d)/dᵏ→1 as d grows. Halved-flag graphs supply the construction.
Sources
Website timeline
Publication dates and editorial changes.