Abstract:Let $N(\Delta,D)$ denote the maximum number of vertices in a simple undirected connected graph with maximum degree at most $\Delta$ and diameter at most $D$. Determining $N(\Delta,D)$ is known as the degree/diameter problem. Although the problem has been studied for many years, the exact value of $N(\Delta,D)$ is unknown for most pairs $(\Delta,D)$. In this paper we construct explicit graphs, using a construction discovered through interaction with ChatGPT via its standard web interface, showing that $N(12,5)\ge 34{,}992$ and $N(16,5)\ge 147{,}456$. These improve the corresponding recorded lower bounds 29,621 and 132,496. The search was conducted without an external orchestration layer around ChatGPT: no custom agent framework, automated evaluator-driven search loop, problem-specific search engine, or formal proof assistant was set up in advance by the author. As far as the visible transcript shows, the author did not prompt the model with the concrete components or candidate families of the construction. After presenting the mathematical result, we describe the discovery process on the basis of the visible transcript. We focus on the meta-level interventions made during the approximately six-day search, and we identify the stage at which the abstraction underlying the construction first appeared.
From: Ryosuke Mizuno [view email]
[v1]
Sun, 14 Jun 2026 15:29:58 UTC (9,774 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。