# New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search

arXiv: https://arxiv.org/abs/2605.01120 · HTML: https://mlsanity.com/paper/2605.01120/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 21 references that are in the map.
- First posted on arXiv 1 May 2026.

## Builds on (most cited first, 4 of 4)

- [GraphArena: Evaluating and Exploring Large Language Models on Graph Computation](https://mlsanity.com/paper/2407.00379/) (2024)
- [GraphEval36K: Benchmarking Coding and Reasoning Capabilities of Large Language Models on Graph Datasets](https://mlsanity.com/paper/2406.16176/) (2024)
- [Reinforced Generation of Combinatorial Structures: Ramsey Numbers](https://mlsanity.com/paper/2603.09172/) (2026)
- [An attack on Zarankiewicz's problem through SAT solving](https://mlsanity.com/paper/2203.02283/) (2022)

## Built on by (most cited first, 4 of 4)

- [Relay, Don't Route: Adaptive Population Handoff for Cost-Efficient LLM-Driven Evolution](https://mlsanity.com/paper/2608.05651/) (2026)
- [Algorithmic algorithm development with LLMs: A Case Study on LLM-Usage for Contraction Order Optimization in Tensor Networks](https://mlsanity.com/paper/2606.01975/) (2026)
- [Exact Zarankiewicz Values On Two Finite Frontier Slices](https://mlsanity.com/paper/2608.08154/) (2026)
- [RamseyGadgets: A Graph Construction Dataset for LLMs](https://mlsanity.com/paper/2608.14999/) (2026)

## Abstract (arXiv)

The Zarankiewicz number Z(m, n, s, t) is the maximum number of edges in a bipartite graph Gm, n such that there is no complete Ks, 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, and Z(12, 22, 3, 3)=132. We further establish lower bounds for 41 more Zarankiewicz numbers, including several that are within one edge of the best known upper bound, and we match the established value in four more closed cases. 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 to contribute to mathematical research. In addition to presenting the resulting constructions, we report the generation algorithms produced, describe the relevant implementation details, and provide our computational costs. Our costs are remarkably low, at less than 30 for each Zarankiewicz parameter combination, showing that LLM-guided evolutionary search can be an inexpensive, reproducible, and accessible tool for discovering new combinatorial constructions.