Δ7 · D4stood 42 years
346 → 359
Delorme & Farhi 1984
C. Delorme, G. Farhi, “Large graphs with given degree and diameter, Part I”, IEEE Transactions on Computers C-33 (1984) 857–860. source
The problem, in one minute
How big can a bipartite network get?
A network here is just points and the links between them; mathematicians call it a graph, with vertices and edges. The game: fit in as many points as you can, while every point obeys three rules. It is an open research problem, worked on for decades, because for most sizes nobody knows the largest network possible. So mathematicians keep a table of the biggest ones anyone has built. Each entry is a record.
Two sides
Every point is brass or blue, and links only join brass to blue, never two of a colour. That is what bipartite means.
At most Δ links
No point gets more than Δ links, like a limit on handshakes. In the table, Δ runs from 3 to 16.
At most D hops
Every point reaches every other along at most D links. That is the diameter.
The catch: rules 2 and 3 pull against each other. Few links each, yet everyone close: every extra point makes that harder, and past a certain size it is impossible.
How to read a record
- Δ7at most 7 links per point
- D5every point within 5 hops of every other
- two sidesalways, for every record here
old record1,134points, by 2009
new record1,140points, Oct 10, 2026
Every label like Δ7 · D5 on this page names one cell of that table. Eight of them got new records.
- records broken
- 8
- years the oldest had stood
- 42
- vertices past the old records
- 85
- islands at a time at the peak, eight Haikus each
- 48
- programs written
- 33,075
- from the idea to the eighth record
- 9 h 52 m
- new theorem, proved in Lean
- 1
The day · October 10, 2026
One day, eight records
The whole day, replayed in forty seconds. Each line is one record, climbing toward 100% of the number it had to beat, and each Clawd rides its line, hopping up whenever the search finds a bigger graph. Past 100% the record is broken: the Clawd turns gold, and the party starts. The buttons under the replay play the same day as five 3D scenes.
Real data: every new best graph the search logged, at the minute it was logged. Clawd is Claude’s mascot.
How they were found
Evolution, with Haikus doing the mutating
No one drew these graphs by hand. They came out of an evolutionary search, the same idea as breeding: keep the best, change them a little, keep the best again. The twist is who makes the changes. Claude Haiku 5.5, a small and fast AI model, rewrites the programs that build the graphs, thousands of times. The method follows Google DeepMind’s AlphaEvolve (2025). Using Claude Haiku as the cheap mutator comes from Ryan Xu, who improved 25 square-packing records this way; this project started from his post.
The loop is a picture of the method; its pace is illustrative. The climb is real: every step is a graph the search found, in Pacific time.
- Pick parents. Choose a few of the best programs found so far.
- Haiku rewrites. Eight Haikus at once each get a parent’s code plus a page of hints, and write a changed version. This is the mutation step, and it is where the new ideas come from.
- Run. Each new program gets 60 seconds to build a graph.
- Check. A strict checker tests the three rules. A graph that breaks one scores zero; a valid one scores by how big it is.
- Survive. The best programs join the population and become the next parents. Repeat.
Islands
68 separate populations were launched in Claude Code cloud sessions; 61 got a machine and ran, up to 48 at a time, eight Haikus each. Some specialised in one cell, some used a fast C engine. New islands started from their siblings’ best programs, so good ideas spread between islands, like migration.
What the evolution bought
Five hours on one laptop matched two records and beat none. Once the islands ran in the cloud, the first record fell after 31 minutes, and six fell within 82. In all, Haikus wrote over 33,000 programs, starting from two starter programs.
From a search to a theorem
Three of the records grew by exactly 2 in the same way. Claude Opus read the pattern off those three graphs; it works for an infinite family of graphs, and it is now proved in Lean.
Why it is hard
A perfect small answer, and a ceiling
Small cases can be solved completely, like the one on the left. Big ones cannot yet, and the gap between the best network found and the most the rules could ever allow is where the records live.
Try it · a perfect small answer
The Heawood graph: Δ = 3, D = 3, 14 vertices
Click any vertex. It turns white, and the rest are coloured by how many steps away they are. Everyone is within 3 steps. No bipartite graph with these rules can have more than 14 vertices, so this one is a perfect answer. The big 3D view at the top does the same thing to our record graphs, with up to 1,774 vertices.
Why it is hard
Every step can multiply the reach by Δ − 1, at most
From one vertex, step 1 reaches at most Δ vertices. Each of those has at most Δ − 1 new neighbours, and so on: a tree. That caps how big any graph can be. Real graphs fall short because paths collide and reach the same vertex twice. The reach bars in the 3D panel compare each step with this tree.
most at step k = Δ·(Δ−1)k−1 · ceiling for two sides = 2·(1 + (Δ−1) + … + (Δ−1)D−1)
What we beat
Eight records, the oldest from 1984
Every entry in the table came from a paper or a computer search. Here is each one we beat, who set it, and how long it stood, oldest first.
Δ11 · D4stood 42 years
1,734 → 1,774
Delorme & Farhi 1984
Same paper: built by their “graph duplication” method. source
Δ4 · D5stood 17+ years
160 → 162
Hafner, and independently Loz by 2009
The table cites no paper for it. Earliest listing we found: Eyal Loz’s degree–diameter table, January 2009. source
Δ5 · D5stood 17+ years
336 → 354
Eyal Loz, in a project with Pérez-Rosés & Pineda-Villavicencio by 2009
Loz found it in his PhD work, 2006–2008; listed in his January 2009 table. Related paper: E. Loz, G. Pineda-Villavicencio, The Computer Journal 53 (2010). source
Δ7 · D5stood 17+ years
1,134 → 1,140
Eyal Loz, in a project with Pérez-Rosés & Pineda-Villavicencio by 2009
Same project and table as the line above. source
Δ11 · D3stood 14+ years
190 → 192
Feria-Purón, Miller & Pineda-Villavicencio by 2012
R. Feria-Purón, M. Miller, G. Pineda-Villavicencio, “On large bipartite graphs of diameter 3”, Discrete Mathematics 313 (2013). The table already listed 190 in January 2012, before the paper. Araujo-Pardo & López later matched it independently. source
Δ13 · D3stood 6 years
274 → 276
Araujo-Pardo & López 2020
G. Araujo-Pardo, N. López, “On new record graphs close to bipartite Moore graphs”, arXiv:2005.02427 (May 2020); Graphs and Combinatorics (2022). Their paper lists improving it as an open problem. source
Δ15 · D3stood 6 years
374 → 376
Araujo-Pardo & López 2020
Same paper, same family of graphs. All three of their cells grew by exactly 2. source
Each year is when the record first became public: in a paper, its preprint, or the earliest table we found it in, whichever came first. “By” means it may be older. “Stood” counts from that year to 2026. The table is the Combinatorics Wiki’s bipartite degree–diameter table; a literature search found nothing larger published for any of these eight cells (two sources were out of reach). Our records are not in the published table yet: the next step is to send them to its moderators.
A new theorem · proved in Lean
The +2 theorem
Three of our records grew by exactly 2 vertices, in the same way. That was not luck. The pattern works for a whole infinite family of graphs, and we proved it.
See it · the fourth hat
Step 1 of 5
A perfect network
- a point of the plane
- a line of the plane
- a link: the point is on the line
- room for one more link
- half of a hat: a copy of a point of ℓ, or of a line through A
- what just changed
Same rule, order q =
Orders 9, 11 and 13 give 192, 276 and 376 vertices: the sizes of three of our records.
Theorem
For every finite projective plane of order q ≥ 4, there is a bipartite graph with 2(q² + q + 6) vertices, maximum degree q + 2 and diameter 3.
Araujo-Pardo and López (2022) built graphs of size 2(q² + q + 5) and listed improving the construction as an open problem. This beats it by 2, for every q, including planes nobody has written down. The trick is a fourth “hat”: one more copy of a point and of a line, wired in by rotating three connections in a small cycle.
theorem plus2_of_order … (h : 4 ≤ ProjectivePlane.order P L) :
∃ G : SimpleGraph (Fin (2 * (q ^ 2 + q + 6))),
IsBipartiteDegDiam G (q + 2) 3
∃ G : SimpleGraph (Fin (2 * (q ^ 2 + q + 6))),
IsBipartiteDegDiam G (q + 2) 3
Checked by Lean’s kernel. Depends only on the three standard axioms (propext, Classical.choice, Quot.sound): no gaps, no shortcuts.
How it was found
- Haikus, by evolutionary search, found graphs of 192, 276 and 376 vertices: each 2 above the 2022 record.
- Claude Opus 5.5 compared them with the 2022 construction, saw the shared pattern, and wrote a proof that it works for every plane.
- A Haiku 5.5 agent then proved it again in Lean, the proof checker mathematicians use, so no one has to trust the prose.
What it gives
| q | Δ | 2022 | +2 | table |
|---|---|---|---|---|
| 4 | 6 | 50 | 52 | 62 (perfect) |
| 5 | 7 | 70 | 72 | 80 |
| 7 | 9 | 122 | 124 | 146 (perfect) |
| 8 | 10 | 154 | 156 | 182 (perfect) |
| 9 | 11 | 190 | 192 | 190 → now our record |
| 11 | 13 | 274 | 276 | 274 → now our record |
| 13 | 15 | 374 | 376 | 374 → now our record |
| 16 | 18 | 554 | 556 | not in table |
In the table’s range the theorem improves the table only at Δ = 11, 13 and 15: our three records. At Δ = 6, 9 and 10 a perfect graph is already in the table, and at Δ = 7 the table’s 80 beats 72.
The fleet
Sixty-one islands, writing programs
Each tile is one cloud island: a separate evolutionary search where Haikus write programs, the programs build graphs, and the best survive. Sixty-eight were launched; the seven dashed ones never got a cloud machine. Tiles show where each island stood in the final snapshot.
—islands writing at a time, at the peak
—islands got a cloud machine and ran
—programs written
Loading the fleet…
stopped at a usage limit
quiet before the stop
never started: no cloud machine
holds a graph above the table
rows: Py = Python engine, C = C engine · columns: first island, its twin (fleet doubled), two more (doubled again)
Room left
How close each cell is to its ceiling
The rail runs from zero to the best upper bound listed for the cell. The grey tick is the published record, the brass dot is ours. The diameter-3 cells sit within about 10–20% of their ceilings; the others leave a third of the rail or more. Nobody knows the true answers yet.
Loading…
Proof
Why we believe the graphs
Every record passes three separate checkers and a literature search. The Lean column says which graph has a machine-checked proof. The checkers, graphs and Lean files are all on GitHub, so anyone can rerun them.
| Cell | Table | Ours | In Lean | Old record |
|---|---|---|---|---|
| Loading… | ||||
A fast bitset checker confirms degree, two sides and the diameter.
networkx agrees using a completely separate library.
A from-scratch search from every vertex finds the exact diameter.
Seven of eight rebuilt on a second machine from the island’s own program. The 1,774 program gives 1,773, so that graph is the island’s saved copy.
Literature search found nothing larger published, and no proven bound below ours (two sources were out of reach).
Lean proofs, written by a Haiku in strict mode, trusting only Lean's kernel.
FAQ
why use haikus rather than opus or fable?
haikus are cheap, fast, and smart enough! meaning i can run approximately 200x more haikus than I can run fables (50x for opus) within subscription limits! When it comes to evolutionary search, many haiku together stronk.
Got a question? Ask me!
Credits
Who did what
Doğa Özden
Had the idea, steered the search and made the calls. More importantly, provided Claude with encouragement and emotional support.
Claude Opus 5.5
In Claude Code: built and coordinated the search across 61 cloud islands, checked every record, and turned the +2 pattern into a proof.
Claude Haiku 5.5
The searchers: up to 48 islands of eight at a time, over 33,000 programs in all. A Haiku also wrote the Lean proofs.
On the shoulders of
Google DeepMind’s AlphaEvolve, for the method; Ryan Xu, for Haiku as the cheap mutator; and the table’s authors and the Combinatorics Wiki’s maintainers, for the records to beat.
The visuals, one by one