Asymptotically attaining the Moore bound
2026-08-04 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors study how big a graph can get if it has a limit on how connected it is (maximum degree) and how far apart points can be (diameter). They prove that as the allowed maximum degree gets very large, the largest possible graph size grows roughly like the degree raised to the diameter power. This solves a longstanding question in graph theory posed by Bollobás. They achieve the result by constructing special graphs based on algebraic structures over finite fields and also build graphs controlling a related measure called line-graph diameter.
graph theorymaximum degreediameterdegree-diameter problemfinite fieldsregular graphsline graphasymptotic analysisBollobás conjecturepartial flags
Authors
Wouter Cames van Batenburg, Samuel Korsky
Abstract
For positive integers $d$ and $k$, let $n_k(d)$ be the maximum order of a graph of maximum degree at most $d$ and diameter at most $k$. We prove that $$ \lim_{d\to\infty}\frac{n_k(d)}{d^k}=1$$ for every fixed $k$, thereby resolving the asymptotic degree-diameter problem for fixed diameter and proving a conjecture of Bollobás. The lower bound comes from regular graphs $H_{k,q}$, indexed by prime powers $q$, whose vertices are partial flags in $\mathbb{F}_q^{\,2k+1}$. These graphs have diameter $k$ and order $|V(H_{k,q})| =(1+o(1))Δ(H_{k,q})^k$. We also construct, for every fixed $\ell \ge 2$, graphs of maximum degree at most $d$ and line-graph diameter at most $\ell$ with $(1+o(1))d^{\ell}$ edges.