LLM improves Zarankiewicz numbers via evolutionary search
A new study published on arXiv demonstrates how an LLM-based evolutionary algorithm has determined exact values for three Zarankiewicz numbers and improved lower bounds for 41 more.
Vad har hänt
Researchers using an open-source algorithm called OpenEvolve have successfully determined the exact values for three Zarankiewicz numbers: Z(11, 21, 3, 3)=116, Z(11, 22, 3, 3)=121, and Z(12, 22, 3, 3)=132. In addition, lower bounds have been improved for a further 41 Zarankiewicz numbers, several of which are now within one unit of the best known upper bounds. Four previously closed cases were also matched. The results were presented in a study published on 15 May 2026 on arXiv.
Key facts
| Publiceringsdatum | 15 maj 2026 |
|---|---|
| Antal exakta Zarankiewicz-tal fastställda | 3 |
| Antal Zarankiewicz-tal med förbättrade undre gränser | 41 |
| Algoritm | OpenEvolve (LLM-baserad) |
”The Zarankiewicz number Z(m, n, s, t) is the maximum number of edges in a bipartite graph G_{m, n} such that there is no complete K_{s, t} bipartite subgraph. We determine for the first time the exact values of three Zarankiewicz numbers: Z(11, 21, 3, 3)=116, Z(11, 22, 3, 3)=121,”
”Our results are obtained using OpenEvolve, an open-source evolutionary algorithm based on Large Language Models (LLMs) that iteratively improves algorithms for generating mathematical constructions by optimizing a reward signal which we tailored for this specific problem.”
”These findings provide new extremal graph constructions and demonstrate the potential of LLM-guided evolutionary search”
Varför det spelar roll
Zarankiewicz numbers are a central concept in extremal graph theory, describing the maximum number of edges in a bipartite graph that does not contain a given bipartite subgraph. The study demonstrates the potential of LLM-guided evolutionary search to solve complex mathematical problems. The determination of new Zarankiewicz numbers and the improvement of lower bounds provide new extremal graph constructions.
Vem påverkas
Researchers in mathematics and computer science, particularly those working with graph theory, combinatorics, and optimisation algorithms, are directly affected by these new findings. Developers of LLM-based engineering and research tools, such as those from OpenAI, may also find the methodology relevant. The results push the boundaries of what is achievable with AI in complex mathematical fields.
EU-status
Ej relevant för EU-status.
Mer att veta
OpenEvolve is an open-source algorithm based on large language models that optimises reward signals to iteratively improve algorithms for generating mathematical constructions. This methodology was tailored specifically for the problem of Zarankiewicz numbers.
Quick answers about this story
Vad har hänt?
När hände det?
Varför spelar det roll?
Vilka bolag berörs?
Länken öppnar i nytt fönster och leder till utgivarens egen sida.
Källan har spårats automatiskt från utgivaren via Aheadlines signalkedja.