pith. machine review for the scientific record. sign in

arxiv: 2605.01120 · v2 · submitted 2026-05-01 · 💻 cs.AI · math.CO

Recognition: unknown

New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search

Jay Bhan , Nicole Nobili , Srinivasan Raghuraman , Patrick Langer
Authors on Pith no claims yet

Pith reviewed 2026-05-09 18:59 UTC · model grok-4.3

classification 💻 cs.AI math.CO
keywords Zarankiewicz numbersbipartite graphsextremal graph theoryK_{3,3}-free graphsevolutionary algorithmsLLM-guided searchcombinatorial constructions
0
0 comments X

The pith

An LLM evolutionary search determines exact values for three Zarankiewicz numbers and improves lower bounds for 41 more.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper uses an open-source evolutionary algorithm driven by large language models to search for bipartite graphs with the maximum number of edges while avoiding any complete K_{3,3} subgraph. Running this search produces constructions that achieve the absolute maximum for three specific sizes, fixing those Zarankiewicz numbers exactly at 116, 121, and 132. The same method also supplies new lower bounds in 41 additional cases, some of which sit only one edge below the best known upper bounds. All of this work stays under 30 dollars per parameter combination and includes both the graphs and the code that generated them.

Core claim

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.

What carries the argument

OpenEvolve, an LLM-based evolutionary algorithm that iteratively refines programs for producing K_{3,3}-free bipartite graphs by maximizing an edge-count reward.

If this is right

  • Explicit constructions now exist that set the exact value for three Zarankiewicz parameters and tighten the gap in 41 others.
  • Four previously open cases are now closed by matching the known upper bound.
  • The same search process produces both the final graphs and the generation algorithms used to create them.
  • Total compute cost remains below 30 dollars per parameter tuple, making the method reproducible with modest resources.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same LLM evolutionary loop could be redirected to other extremal questions such as finding Ramsey numbers or C_4-free graphs.
  • Independent verification of the adjacency matrices would confirm the absence of K_{3,3} and allow direct comparison with future upper-bound improvements.
  • Refining the reward function or adding symmetry-breaking steps might push the method to larger vertex sets where current bounds remain wide.
  • Releasing the generation code lets other researchers run longer searches or adapt the framework to different forbidden subgraphs.

Load-bearing premise

The upper bounds taken from earlier papers are correct and the new constructions contain no K_{3,3} subgraphs that escaped detection during verification.

What would settle it

Either a K_{3,3} subgraph found inside one of the reported constructions or a K_{3,3}-free bipartite graph on the same vertex sets with strictly more edges than the reported number.

Figures

Figures reproduced from arXiv: 2605.01120 by Jay Bhan, Nicole Nobili, Patrick Langer, Srinivasan Raghuraman.

Figure 1
Figure 1. Figure 1: Optimal Zarankiewicz matrices for Z(11, 21, 3, 3) = 116, Z(11, 22, 3, 3) = 121 and Z(12, 22, 3, 3) = 132 found by our work. Black squares represent ones and white squares represent zeros. that LLM based evolutionary discovery methods do not require large scale computational budgets and can instead serve as accessible tools for generating mathematical constructions that lead to new results. 5 Prior attempts… view at source ↗
Figure 2
Figure 2. Figure 2: Upper and lower bounds for Zarankiewicz numbers view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript introduces OpenEvolve, an open-source LLM-based evolutionary algorithm, and applies it to generate explicit bipartite graphs establishing new lower bounds on Zarankiewicz numbers Z(m,n,3,3). It claims exact determinations Z(11,21,3,3)=116, Z(11,22,3,3)=121, and Z(12,22,3,3)=132 by matching generated constructions to cited upper bounds, plus improved lower bounds for 41 further pairs and matches to four known exact values, all at computational cost below $30 per instance.

Significance. If the constructions are correct, the work closes three open exact cases and tightens many others with verifiable graphs, while demonstrating an inexpensive, reproducible search method for extremal combinatorial objects. The explicit constructions and reported generation algorithms constitute a concrete, auditable contribution beyond heuristic claims.

major comments (2)
  1. [Results section] Results section (constructions for Z(11,21,3,3), Z(11,22,3,3), Z(12,22,3,3)): the exact values rest on the generated graphs being K_{3,3}-free and achieving the stated edge counts. The manuscript describes the reward function and states that constructions are supplied, yet provides neither the source code for the subgraph-isomorphism checker nor a standalone, machine-readable verification script; independent confirmation therefore requires re-implementing the full pipeline, which is load-bearing for the headline claims.
  2. [Section 3] Section 3 (OpenEvolve algorithm): the reward signal is tailored to penalize K_{3,3} subgraphs, but the precise implementation details (e.g., how multiple edges or bipartite partitions are handled in the checker) are summarized rather than fully specified with pseudocode or reference implementation. This leaves a small but non-zero risk of silent counting errors that could produce an invalid lower bound coincidentally matching a cited upper bound.
minor comments (3)
  1. [Table 1] Table 1 (summary of new bounds): the column headers for 'lower bound' and 'upper bound' should explicitly note the source of each upper bound (citation and year) to allow immediate cross-checking.
  2. [Figure 2] Figure 2 (evolutionary loop diagram): the caption does not indicate whether the LLM prompt templates are fixed across runs or adapted; adding this detail would improve reproducibility.
  3. [Abstract] The abstract states 'we report the generation algorithms produced'; these should be collected in an appendix or supplementary file with line numbers for direct inspection.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and for identifying specific points that strengthen the verifiability of our results. We address each major comment below and will incorporate the requested clarifications and materials in the revised manuscript.

read point-by-point responses

  1. Referee: [Results section] Results section (constructions for Z(11,21,3,3), Z(11,22,3,3), Z(12,22,3,3)): the exact values rest on the generated graphs being K_{3,3}-free and achieving the stated edge counts. The manuscript describes the reward function and states that constructions are supplied, yet provides neither the source code for the subgraph-isomorphism checker nor a standalone, machine-readable verification script; independent confirmation therefore requires re-implementing the full pipeline, which is load-bearing for the headline claims.

    Authors: We agree that explicit verification aids independent confirmation. The manuscript already supplies the complete edge lists for the three exact constructions (and all other reported graphs) in machine-readable form, which can be checked for K_{3,3}-freeness and edge count with any correct bipartite subgraph detector. Nevertheless, to remove any implementation burden, we will add a standalone Python verification script to the supplementary materials and the OpenEvolve repository. The script will read the provided adjacency lists, confirm bipartiteness, count edges, and exhaustively test for K_{3,3} subgraphs using a standard enumeration routine. This addition will be included in the revision. revision: yes

  2. Referee: [Section 3] Section 3 (OpenEvolve algorithm): the reward signal is tailored to penalize K_{3,3} subgraphs, but the precise implementation details (e.g., how multiple edges or bipartite partitions are handled in the checker) are summarized rather than fully specified with pseudocode or reference implementation. This leaves a small but non-zero risk of silent counting errors that could produce an invalid lower bound coincidentally matching a cited upper bound.

    Authors: We accept that the current description of the checker is concise. In the revision we will expand Section 3 with explicit pseudocode for the K_{3,3}-detection routine used inside the reward function. The pseudocode will detail: (i) enforcement of the fixed bipartite partition (no intra-part edges are ever generated or counted), (ii) prevention of multiple edges between the same pair of vertices, and (iii) the exact enumeration procedure that returns both the presence of any K_{3,3} and the edge count. We will also point readers to the corresponding open-source implementation in the OpenEvolve repository, which contains the identical checker code. These changes eliminate the possibility of silent discrepancies. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit constructions yield falsifiable lower bounds

full rationale

The paper reports lower bounds and exact values for Zarankiewicz numbers obtained by running an LLM-guided evolutionary search (OpenEvolve) that outputs explicit bipartite graphs. These graphs are presented as constructions achieving stated edge counts while remaining K_{3,3}-free; the claims are therefore externally verifiable by independent subgraph-isomorphism checks on the supplied adjacency data. Upper bounds are taken from prior literature without self-citation chains. No equations, fitted parameters, or self-referential definitions appear that would reduce the numerical results to the search procedure by construction. The method description is transparent but does not force the specific extremal values reported.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard definitions of bipartite graphs and forbidden subgraphs with no free parameters, no invented mathematical entities, and no ad-hoc axioms beyond basic graph theory.

axioms (2)
  • standard math Zarankiewicz number Z(m,n,s,t) is the maximum edges in an m-by-n bipartite graph with no K_{s,t} subgraph
    Standard definition in extremal graph theory invoked throughout the abstract and results section
  • standard math Bipartite graphs are 2-colorable with no odd cycles
    Basic property used implicitly when constructing and verifying the graphs

pith-pipeline@v0.9.0 · 5569 in / 1467 out tokens · 55337 ms · 2026-05-09T18:59:01.410550+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

26 extracted references · 9 canonical work pages

  1. [1]

    Claude 3.7 Sonnet and Claude Code

    Anthropic. Claude 3.7 Sonnet and Claude Code. https://www.anthropic.com/news/ claude-3-7-sonnet, 2025. Accessed: 2026-04-29

    2025

  2. [2]

    Introducing Claude Opus 4.6

    Anthropic. Introducing Claude Opus 4.6. https://www.anthropic.com/news/ claude-opus-4-6, 2026. Accessed: 2026-04-29

    2026

  3. [3]

    Ellenberg, Adam Zsolt Wagner, and Geordie Williamson

    François Charton, Jordan S. Ellenberg, Adam Zsolt Wagner, and Geordie Williamson. Pat- ternBoost: Constructions in mathematics with a little help from AI, 2024. URL https: //arxiv.org/abs/2411.00566

    work page arXiv 2024

  4. [4]

    Collins, Alexander W

    Alex F. Collins, Alexander W. N. Riasanovsky, John C. Wallace, and Stanislaw P. Radziszowski. Zarankiewicz numbers and bipartite ramsey numbers. 2018

    2018

  5. [5]

    Some remarks on the zarankiewicz problem

    David Conlon. Some remarks on the zarankiewicz problem. Preprint. URL https://www. its.caltech.edu/~dconlon/zarankiewicz.pdf. Accessed 1 May 2026

    2026

  6. [6]

    Improved upper bounds on Zarankiewicz numbers

    Sara Davies, Peter Gill, and Daniel Horsley. Improved upper bounds on Zarankiewicz numbers. Discrete Mathematics, 349(5):114924, 2026. doi: 10.1016/j.disc.2025.114924

    work page doi:10.1016/j.disc.2025.114924 2026

  7. [7]

    Spectrally indistin- guishable pseudorandom graphs, 2025

    Arthur Forey, Javier Fresán, Emmanuel Kowalski, and Yuval Wigderson. Spectrally indistin- guishable pseudorandom graphs, 2025

    2025

  8. [8]

    Henning, and Ortrud R

    Wayne Goddard, Michael A. Henning, and Ortrud R. Oellermann. Bipartite ramsey numbers and zarankiewicz numbers.Discrete Mathematics, 219(1):85–95, 2000

    2000

  9. [9]

    Gemini 2.0 Flash

    Google. Gemini 2.0 Flash. https://cloud.google.com/vertex-ai/generative-ai/ docs/models/gemini/2-0-flash, 2025. Accessed: 2026-04-29

    2025

  10. [10]

    Thomas P. Hayes. Separating the k-party communication complexity hierarchy: An application of the zarankiewicz problem.Discrete Mathematics & Theoretical Computer Science, 13(4): 15–22, 2011. doi: 10.46298/dmtcs.546

    work page doi:10.46298/dmtcs.546 2011

  11. [11]

    Complexity of linear boolean operators.F oundations and Trends in Theoretical Computer Science, 9(1):1–123, 2013

    Stasys Jukna and Igor Sergeev. Complexity of linear boolean operators.F oundations and Trends in Theoretical Computer Science, 9(1):1–123, 2013

    2013

  12. [12]

    On a problem of

    T. K˝ovári, V . T. Sós, and P. Turán. On a problem of k. zarankiewicz.Colloquium Mathematicum, 3(1):50–57, 1954. doi: 10.4064/cm-3-1-50-57

    work page doi:10.4064/cm-3-1-50-57 1954

  13. [13]

    Network oblivious trans- fer

    Ranjit Kumaresan, Srinivasan Raghuraman, and Adam Sealfon. Network oblivious trans- fer. In Matthew Robshaw and Jonathan Katz, editors,Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, Au- gust 14-18, 2016, Proceedings, Part II, Lecture Notes in Computer Science, pages 366–396. Springer, 2016. ...

    work page doi:10.1007/978-3-662-53008-5 2016

  14. [14]

    Reinforced generation of com- binatorial structures: Applications to complexity theory, 2025

    Ansh Nagda, Prabhakar Raghavan, and Abhradeep Thakurta. Reinforced generation of com- binatorial structures: Applications to complexity theory, 2025. URL https://arxiv.org/ abs/2509.18057

    work page arXiv 2025

  15. [15]

    Reinforced generation of combi- natorial structures: Ramsey numbers, 2026

    Ansh Nagda, Prabhakar Raghavan, and Abhradeep Thakurta. Reinforced generation of combi- natorial structures: Ramsey numbers, 2026

    2026

  16. [16]

    Alexander Novikov, Ngân V˜u, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algor...

    2025

  17. [17]

    A problem of zarankiewicz.Journal of Combinatorial Theory, Series A, 18(2): 187–198, 1975

    Steven Roman. A problem of zarankiewicz.Journal of Combinatorial Theory, Series A, 18(2): 187–198, 1975. doi: 10.1016/0097-3165(75)90007-2

    work page doi:10.1016/0097-3165(75)90007-2 1975

  18. [18]

    Openevolve: an open-source evolutionary coding agent, 2025

    Asankhaya Sharma. Openevolve: an open-source evolutionary coding agent, 2025. URL https://github.com/algorithmicsuperintelligence/openevolve

    2025

  19. [19]

    A survey of zarankiewicz problems in geometry, 2025

    Shakhar Smorodinsky. A survey of zarankiewicz problems in geometry, 2025

    2025

  20. [20]

    An attack on Zarankiewicz’s problem through SAT solving, 2022

    Jeremy Jierui Tan. An attack on Zarankiewicz’s problem through SAT solving, 2022

    2022

  21. [21]

    Grapharena: Evaluating and exploring large language models on graph computation

    Jianheng Tang, Qifan Zhang, Yuhan Li, Nuo Chen, and Jia Li. Grapharena: Evaluating and exploring large language models on graph computation. InInternational Conference on Learn- ing Representations, 2025. URL https://proceedings.iclr.cc/paper_files/paper/ 2025/hash/77fa8253adfc8b33209639f3e9985741-Abstract-Conference.html

    2025

  22. [22]

    On an extremal problem in graph theory.Matematikai és Fizikai Lapok, 48:436–452, 1941

    Pál Turán. On an extremal problem in graph theory.Matematikai és Fizikai Lapok, 48:436–452, 1941

    1941

  23. [23]

    GraphEval36K: Benchmarking coding and reasoning capabilities of large language models on graph datasets

    Qiming Wu, Zichen Chen, Will Corcoran, Misha Sra, and Ambuj Singh. GraphEval36K: Benchmarking coding and reasoning capabilities of large language models on graph datasets. InFindings of the Association for Computational Linguistics: NAACL 2025, pages 8110– 8132, Albuquerque, New Mexico, April 2025. Association for Computational Linguis- tics. doi: 10.1865...

    work page doi:10.18653/v1/2025.findings-naacl.452 2025

  24. [24]

    Learning to discover at test time.arXiv preprint arXiv:2601.16175, 2026

    Mert Yuksekgonul, Daniel Koceja, Xinhao Li, Federico Bianchi, Jed McCaleb, Xiaolong Wang, Jan Kautz, Yejin Choi, James Zou, Carlos Guestrin, and Yu Sun. Learning to discover at test time, 2026. URLhttps://arxiv.org/abs/2601.16175

    work page arXiv 2026

  25. [25]

    Zarankiewicz

    K. Zarankiewicz. Problem p 101.Colloquium Mathematicum, 2:301, 1951

    1951

  26. [26]

    __main__

    Yufei Zhao.Graph Theory and Additive Combinatorics: Exploring Structure and Randomness. Cambridge University Press, 2023. A Successful Search Algorithms Algorithm 2: Search algorithm establishing for the first time that the previously known upper bound forZ(11,21,3,3)is tight. import numpy as np def construct_graphs(): M, N = 11, 21 def is_valid(G): for i...

    2023