VibeMathedMath problems solved with AI
Sign in

Existence of tt-Edge-Balanced Graphs for t≥3t \ge 3

A graph GG on nn vertices with kk edges is tt-edge-balanced if every graph on nn vertices with tt edges is contained in exactly the same number of subgraphs of KnK_n isomorphic to GG. Infinite families were known for t=2t = 2, but no example was known for any t≥3t \ge 3. Resolved in both directions: 33-edge-balanced graphs exist, and no nontrivial tt-edge-balanced graphs exist for t≥4t \ge 4.

Result
Proved
Status
Resolved
AI contribution
AI-assisted
Method
Computation
Field
Design theory
Posed by
open in the design theory literature
Year posed
—
Years open
—
Solved
2026-05-16
Model
ChatGPT
Vendor
OpenAI
Collaborators
Yeow Meng Chee
Verification
Unreviewed
Publication
Preprint
Significance
15 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What the AI did

Tooling rather than mathematics: the simulated annealing search was implemented in C++ with the code developed with the assistance of ChatGPT. The search then found zero-score graphs for 11 parameter sets including the ten smallest. The arithmetic conditions on the parameters and the nonexistence proof for t≥4t \ge 4 are the author's.

Verification

The examples are explicit graphs, published with source code, and each candidate had its subgraph count profile recomputed from scratch as an independent check. That makes the existence half verifiable by anyone who reruns the count. arXiv preprint, not peer-reviewed.

Source

Changelog4 changes
  • Rasmus Lindahlchanged Short name from “t-edge-balanced graphs” to “$t$-edge-balanced graphs”
  • Rasmus Lindahlchanged Name from “Existence of t-Edge-Balanced Graphs for t ≥ 3” to “Existence of $t$-Edge-Balanced Graphs for $t \ge 3$”
  • Rasmus Lindahlchanged Short name from “$t$-edge-balanced graphs” to “t-edge-balanced graphs”, also Name
  • Rasmus Lindahlchanged Significance note from “Settles a standing existence question in design theory, producing the first known examples…” to “Settles a standing existence question in design theory, producing the first known examples…”

Discussion