Source-linked AI summary
New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search
Jay Bhan, Nicole Nobili, Patrick Langer
TL;DR
The paper addresses the difficulty of finding finite lower-bound constructions for Zarankiewicz numbers. It uses OpenEvolve, an LLM-guided evolutionary search that improves construction-generating programs, and proves three exact values while adding bounds across dozens of cases. The experiments cost less than $30 per parameter combination, supporting the method’s accessibility for finite construction problems.
Problem
Lower-bound constructions for Zarankiewicz numbers remain underdeveloped because they are often difficult to obtain analytically and computationally specialized.
Method
OpenEvolve evolves LLM-generated algorithms that construct dense binary matrices while preserving the forbidden-submatrix constraints.
Results
The method proves Z(11, 21, 3, 3) = 116, Z(11, 22, 3, 3) = 121, and Z(12, 22, 3, 3) = 132, establishes 41 further lower bounds, and reproduces four known optimal constructions.
Takeaways & Limitations
Evolutionary program search can provide practical, inexpensive constructions for finite Zarankiewicz problems where analytic constructions are difficult.
Takeaways & Limitations
The experiments are restricted to s = t = 3 and selected m,n ranges, leaving extensions to other parameters for future work.
Abstract
from arXiv · showhide
The Zarankiewicz number $\textbf{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: $\textbf{Z}(11, 21, 3, 3)=116$, $\textbf{Z}(11, 22, 3, 3)=121$, and $\textbf{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.
1 Introduction
The Zarankiewicz problem asks for the densest bipartite graphs avoiding a prescribed complete bipartite subgraph, with applications in extremal graph theory and theoretical computer science. This work uses LLM-guided evolutionary search to generate constructions for lower bounds.
- The Zarankiewicz number is the maximum edge count in a bipartite graph with parts of sizes m and n that avoids K_s,t.
- Exact asymptotics for fixed s and t remain open despite extensive work on Zarankiewicz numbers.
- Zarankiewicz bounds connect extremal graph theory to bipartite Ramsey numbers, Boolean matrices, communication complexity, and circuit complexity.
- The paper applies OpenEvolve, an open-source AlphaEvolve-style system in which LLMs iteratively improve algorithms for mathematical constructions.
2 Method
The method represents Zarankiewicz constructions as binary matrices and evolves programs that generate dense feasible matrices. OpenEvolve scores mutated programs by their valid output and iteratively refines them across a staged multi-model search schedule.
- 2.1 Formulating the problem: A construction with c edges and no K_s,t yields the lower bound Z(m, n, s, t) ≥ c.
- 2.1 Formulating the problem: Candidates are binary m × n matrices, where maximizing ones is equivalent to maximizing edges while forbidding all-ones s × t submatrices.
- 2.2 AlphaEvolve: OpenEvolve maintains candidate programs, uses LLM mutations, evaluates generated matrices with a scoring function, and feeds strong candidates into later generations.
- 2.3 Choice of Zarankiewicz parameters: The study targets 51 cases with s = t = 3, including 44 previously unresolved combinations in 9 ≤ m ≤ 16 and 17 ≤ n ≤ 23.
- 2.4 Search algorithm: Each search phase runs 100 iterations, generates two matrices per mutated program, and scores valid outputs by their number of ones while penalizing violations.
- 2.5 Search schedule: The three-phase schedule varies Gemini and Claude models, then adds further phases when the lower bound improves without matching the upper bound.
3 Results
Across 51 s = t = 3 cases, the method reproduces four known optimal constructions, proves three upper bounds tight, and supplies lower bounds for 41 previously open cases.
- 3 Results: Four of seven previously determined values are replicated, while lower bounds are established for the other 41 of 44 open cases.
- 3 Results: Some newly established lower bounds lie within one edge of the corresponding upper bound.
4 Cost analysis
The reported search is inexpensive and fast, costing approximately $15–$30 per case with phases taking around 10 minutes. Figure 1 visualizes the three optimal binary matrices found for the exact cases.
- 4 Cost analysis: Each m × n case costs approximately $15 to $30, depending on the iterations needed before convergence.
- 4 Cost analysis: Each search phase takes around 10 minutes, making the experiments time efficient.
- 4 Cost analysis: Figure 1 displays the optimal matrices for the three exact values, with black squares representing ones and white squares representing zeros.
- 4 Cost analysis: The authors characterize LLM-based evolutionary discovery as an accessible tool for generating mathematical constructions without large-scale computational budgets.
5 Prior attempts on Zarankiewicz Numbers
Prior work emphasized upper bounds and exact values for special cases, while explicit lower-bound constructions remained comparatively underdeveloped and computationally difficult to obtain.
- Tan formulated lower-bound searches as satisfiability problems and upper-bound searches as unsatisfiability problems for graphs up to certain sizes.
- Davies et al. strengthened Roman’s linear-program constraints, improving upper bounds in 29 of the 44 open cases studied.
- Lower-bound research is underdeveloped compared with asymptotic upper bounds and exact upper-bound computations for special cases.
- Explicit lower-bound constructions are difficult because they often require computational or highly problem-specific methods.
6 Generated Search Algorithms
The generated search algorithms include direct matrix output, circulant constructions, and randomized ripup-and-repair procedures, with the latter suggesting a broader construction framework.
- The reported algorithms reproduce known constructions in four cases and prove tight upper bounds for Z(11, 21, 3, 3), Z(11, 22, 3, 3), and Z(12, 22, 3, 3).
- Seven generated algorithms fall into three categories: direct matrix output, circulant constructions, and randomized perturbation-and-repair methods.Two algorithms use minimal computation, two exploit circulant structure, and three use randomized perturbation and repair.
- Two algorithms exploit circulant structure through modular shift-set enumeration or a circulant base followed by greedy construction.
- Three algorithms use randomized repair, including iterative improvement, random removal of ones followed by greedy reinsertion, and local and global validity checks.
- The ripup-and-repair strategy may generalize to a broader search framework for dense K_s,t-free matrices and other Zarankiewicz parameters.
7 Discussion and Conclusion
The study shows that LLM-guided evolutionary program search can generate new finite Zarankiewicz constructions efficiently, while broader parameter coverage and automated upper-bound discovery remain future directions.
- The method proves Z(11, 21, 3, 3) = 116, Z(11, 22, 3, 3) = 121, and Z(12, 22, 3, 3) = 132, establishes 41 additional lower bounds, and reproduces four known optimal constructions.
- Each parameter combination costs less than $30, with searches completing in the order of minutes.
- The results indicate that evolutionary program search can be practical for discovering dense K_s,t-free bipartite graphs when analytic finite constructions are difficult.
- Future work includes extending beyond s = t = 3, consolidating ripup-and-repair into a universal lower-bound procedure, and automatically proving upper bounds.
A Successful Search Algorithms
The successful search algorithms establish tight upper bounds for Z(11,21,3,3), Z(11,22,3,3), and Z(12,22,3,3), while also reproducing several known exact constructions. They combine explicit matrices, circulant designs, greedy filling, and randomized perturbation or repair while enforcing K_{3,3}-freeness.
- New tight bounds: Z(11,21,3,3), Z(11,22,3,3), and Z(12,22,3,3) are established as tight against their previously known upper bounds.The corresponding searches are Algorithms 2, 3, and 4, respectively.
- Circulant constructions: 154 ones are obtained for Z(11,22,3,3) using two 11×11 circulant blocks with seven shifts each.The construction checks that every three rows have at most two common 1-columns, preventing a K_{3,3}.
- Circulant constructions: The Z(12,22,3,3) algorithm combines two circulant blocks over GF(11) with an extra row and greedy validity-preserving filling.The shift sets have sizes 5 and 6, and subsequent passes greedily improve cells while retaining the forbidden-subgraph constraint.
- Known exact cases: The search reproduces known exact constructions for Z(8,23,3,3), Z(9,22,3,3), and Z(15,16,3,3).The Z(8,23,3,3) construction has 94 ones, while the Z(15,16,3,3) construction starts from an exact 123-one matrix.