New lower bounds for the degree/diameter problem via interaction with a browser-accessible LLM

Source: arXiv:2606.15860 · Published 2026-06-14 · By Ryosuke Mizuno

TL;DR

This paper addresses the degree/diameter problem in graph theory, which asks for the largest number of vertices N(Δ,D) in a simple undirected connected graph with maximum degree at most Δ and diameter at most D. While the problem has a long history, exact values of N(Δ,D) remain unknown for most parameter pairs. The author presents new explicit constructions for diameter 5 graphs with Δ=12 and Δ=16, improving known lower bounds from 29,621 to 34,992 and from 132,496 to 147,456 vertices respectively. These results approach but do not reach the Moore upper bounds, tightening the known bounds for these parameter settings.

What is distinctive is that these mathematical constructions emerged through a purely interactive process with ChatGPT via its standard web UI, without any automated orchestrator, external search engine, formal proof assistant, or problem-specific evaluator. Instead, the author engaged in a roughly 6-day dialogue involving meta-level prompts and mathematical abstractions that progressively refined the search space. The key conceptual breakthrough was the "route-chart lift", decomposing the problem into independent finite design tasks for a small "controller" graph and a linear-algebraic "fiber chart". This human–LLM collaborative process is documented and analyzed in detail, highlighting how the abstraction and mathematical insight appeared incrementally in the dialogue.

The main mathematical contribution and improved lower bounds are standalone: full correctness rests on explicitly stated constructions and finite algebraic certificates, detailed in an appendix with verification routines. The paper thus presents a rare combination of a new state-of-the-art graph theory result discovered with no external programming or formal machinery beyond a browser-accessible LLM, alongside a transparent account of the discovery process.

Key findings

• New lower bound for N(12,5) is 34,992 vertices, improving prior best of 29,621 by +18.13%.
• New lower bound for N(16,5) is 147,456 vertices, improving prior best of 132,496 by +11.29%.
• The constructions achieve diameter exactly 5 and degrees exactly 12 and 16 respectively, verified by finite certificates.
• The route-chart lift construction reduces finding large graphs to designing a small exact-NB-5 controller graph and a universal fiber-side route chart over finite fields.
• The controller is a 144-vertex 4-regular exact nonbacktracking 5-walk connected graph built via voltage lifts from C4 × C6.
• Fiber-side charts are constructed over finite fields F3^5 and F4^5 with controllability matrices nonsingular for all reduced words of length 5.
• Moore ratios (lower bound / Moore upper bound) achieved are 18.11% for (12,5) and 16.99% for (16,5), approaching theoretical limits.
• All design verification steps are reproducible from provided algebraic data and construction scripts without reliance on the LLM.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is not applicable here as the paper concerns mathematical graph construction and discovery. The threat model is essentially that of finding mathematical constructions that satisfy strict graph-theoretic constraints: maximum degree Δ and diameter D. The assumptions are that graphs must be simple, undirected, connected, and constructed explicitly with proofs validating maximum diameter and degree.

2. Data: The "data" corresponds to finite graphs, algebraic structures (finite fields), and labeled walks rather than empirical datasets. The key components include: a small controller graph C (constructed by voltage lifts from known base multigraphs), finite alphabets labeling directed edges, finite fields Fq of order 3, 4, 5, and s = 5 dimensions for coordinate charts, and algebraic matrices and vectors representing route charts. The splits or divisions occur naturally into controller (topology) and fiber (linear algebra) subproblems.

3. Architecture / Algorithm: The main novel architectural concept is the route-chart lift graph construction. Vertices have form (c,x) ∈ V(C) × Fq^s, where C is controller graph vertices and x is a fiber coordinate.

• Controller: a small ρ-regular graph C with an inverse-consistent labeling S of size ρ, supporting exact-NB-s walks of length s = 5 between all vertex pairs.
• Route chart: assigns invertible linear operators At and vectors bt over Fq^s to elements t in S, satisfying inverse-symbol relations, defining fiber edge lifts.
• The edges of the final graph join (u,x) to (v,y) if y = At x + λ bt for some λ in Fq corresponding to the label t of edge u→v in C.

The key novelty is decomposing the diameter and degree constraints into two independent finite problems: controller design (ensuring routing in exactly s nonbacktracking steps) and fiber chart design (ensuring the controllability matrix Mw for every reduced word w is nonsingular). This reduction enables construction verification by finite algebraic checks.

4. Training Regime: Not applicable; this is a mathematical construction, not a learned model.

5. Evaluation Protocol: Verification relies on explicit finite algebraic certificates enumerating conditions on controller walks and fiber controllability matrices. The diameter property is proved by verifying every pair of controller vertices can be connected by a length s nonbacktracking walk, and that the fiber-side linear systems have full rank for all reduced words of length s = 5. This ensures the final lifted graph has diameter ≤ 5. Comparative bounds are reported against the Moore upper bound and previous best-known constructions for (12,5) and (16,5). Ablations involve varying q and s, and attempts with different controllers and fiber charts.

6. Reproducibility: All final constructions, finite certificates, and verification code are provided as supplementary materials. The entire discovery dialogue transcript and LLM-generated intermediate files are also preserved. The author verified claims independently. There is no formalization beyond finite explicit algebraic proofs. The LLM conversation served only as an interactive ideation engine without external orchestration or automated proof systems.

Concrete Example (12,5 case): Starting with a 6-vertex base multigraph and voltage assignment to the abelian group C4 × C6, the author builds a 144-vertex 4-regular controller C. Edges of C are labeled with the alphabet S = {a, a−1, b, b−1} with inverse consistency. For each label t, a matrix At ∈ GL5(F3) and vector bt ∈ F3^5 are assigned satisfying At−1 = At^−1, bt−1 = At^−1 bt. The fiber chart is verified by checking nonsingularity of the 5×5 controllability matrices Mw for every reduced word w of length 5. Applying the route-chart lifting principle yields a 12-regular graph on 144 * 3^5 = 34,992 vertices with diameter ≤ 5, improving the known lower bound.

Technical innovations

• Introduction of the route-chart lift construction that separates diameter/degree graph construction into controller graph design and universal fiber-side controllability charts over finite fields.
• Definition of exact-NB-s controllers ensuring that every vertex pair in the controller has a nonbacktracking path of exact length s, enabling precise diameter proofs.
• Use of universal route charts with invertible controllability matrices for all reduced words of length s, ensuring fiber coordinate reachability via linear-algebraic control inputs.
• Integration of algebraic voltage lifts with linear algebraic chart constructions to form large regular graphs with diameter proofs fully certified by finite algebraic data.

Baselines vs proposed

• Recorded lower bound for N(12,5): 29,621 vs proposed: 34,992 (+18.13%)
• Recorded lower bound for N(16,5): 132,496 vs proposed: 147,456 (+11.29%)
• Moore upper bound for N(12,5): 193,261 with Moore ratio 18.11%
• Moore upper bound for N(16,5): 867,857 with Moore ratio 16.99%

Limitations

• Only two specific cases (Δ=12 and 16, D=5) are improved; the approach’s scalability to other parameters is not fully explored.
• The discovery process documented is a single case study; robustness or generality of human–LLM interaction remains uncertain.
• No formal adversarial or automated adversarial evaluation of LLM contributions; reliance on author’s independent verification.
• Potential account-level LLM context effects cannot be excluded, complicating reproducibility of the interactive discovery exactly as is.
• The fiber and controller conditions, while finite, may become computationally demanding for larger parameters, limiting practical application.
• The improvement, though significant, is still far from Moore bounds, indicating the fundamental hardness persists.

Open questions / follow-ons

• Can the route-chart lift framework be generalized to produce improved bounds for other degree/diameter parameter pairs beyond (12,5) and (16,5)?
• What automated or semi-automated orchestration layers, combining LLMs with evaluators or proof assistants, might accelerate or generalize this discovery process?
• Can the controller and fiber chart subproblems be solved or approximated more efficiently with algorithmic or ML tools?
• What is the theoretical potential and limitations of LLM-human collaboration in mathematical construction beyond this case?

Why it matters for bot defense

While the paper addresses a purely mathematical graph theory problem, the documented methodology of human–LLM interactive discovery without formalized orchestration layers is informative for bot-defense practitioners exploring adversarial or constructive challenges with LLMs. It demonstrates that large, complex search spaces can be decomposed into independent finite design problems and tackled via dialogue with a browser-accessible LLM under human meta-level control. The insights about constraint steering, avoiding unproductive local repair, and emphasizing finite verifiable certificates could inspire design principles for CAPTCHA or bot-detection systems involving LLM-generated candidate defenses. Furthermore, the transparent tracing of unsuccessful attempts and abstraction emergence provides a case study of iterative hypothesis refinement and meta-cognitive guidance in human–AI workflows, relevant when employing LLMs for novel or combinatorial bot-defense strategies.

Cite

@article{arxiv2606_15860,
  title={ New lower bounds for the degree/diameter problem via interaction with a browser-accessible LLM },
  author={ Ryosuke Mizuno },
  journal={arXiv preprint arXiv:2606.15860},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.15860}
}

Read the full paper

• arXiv:2606.15860 (abstract)
• arXiv:2606.15860 (PDF)