Papers With

← All papers
First page of Asymptotically attaining the Moore bound

Asymptotically attaining the Moore bound

Wouter Cames van Batenburg, Samuel Korsky

math.CO Aug 4, 2026 · v1 cs.DM
formalization combinatorics
Read PDF arXiv abstract Code
TL;DR
The main results, including the halved-flag construction proving the asymptotic Moore bound, are accompanied by a Lean 4 formalization published on GitHub.
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.
Problem

The degree-diameter problem asks for n_k(d), the maximum order of a graph with maximum degree at most d and diameter at most k. Bollobás conjectured that n_k(d)/d^k tends to 1 for fixed k. This was previously known only for k in {2,3,5}.

Approach

The authors build regular graphs H_{k,q} whose vertices are the even-rank partial flags in F_q^{2k+1}. Two vertices are adjacent when they share a compatible odd-rank partial flag. The diameter bound uses odd-even transposition sorting to route between complete flags by alternately changing odd-rank and even-rank members. A bipartite doubling construction then gives the line-graph (edge) version, and the results come with a Lean 4 formalization.

Results

The authors prove that lim n_k(d)/d^k = 1 for every fixed k, resolving Bollobás' conjecture. They also construct graphs with maximum degree at most d and line-graph diameter at most ℓ that have (1+o(1))d^ℓ edges, which is asymptotically tight in the bipartite setting.