Discovery of 6 New Zarankiewicz Numbers via LLM-guided Evolutionary Search

We determine for the first time the exact values of six Zarankiewicz numbers, a classical problem in extremal graph theory and combinatorics \cite{Zarankiewicz1951}. The Zarankiewicz problem consists in finding the numbers $\textbf{Z}(m, n, s, t)$, representing the maximum number of edges in a bipartite graph $G_{m, n}$ that is free of any complete bipartite subgraph $K_{s,t}$. We further establish lower bounds for 38 more Zarankiewicz numbers, and we match the established value in four more closed cases. We obtain these results 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 that we tailored for this specific problem. Our costs are remarkably low, at less than \$30 for each Zarankiewicz number we investigated. Thus, our findings show the potential of LLM-guided evolutionary search as an inexpensive, effective, and accessible tool for mathematical research, specifically for discovering new combinatorial constructions.