The Zarankiewicz number z(13,15;3,4)

Primarily AI-generated textHuman understanding: all partsmath.CO — Combinatorics

Contributed by Will Howe, Grant Huffman, Jensen Kohlmeyer ↗, Liam Kruer

Version 1 / Nov 16, 2026 / CC BY 4.0

Abstract

We establish z(13,15;3,4)=114z(13,15;3,4)=114: a 13×1513\times15 binary matrix with 115115 ones necessarily contains an all-one submatrix on three rows and four columns. The lower bound is attained by a previously published construction of Rosero. For the upper bound, we exclude dense eight-row column neighborhoods by a finite classification and a complete extension check. The resulting local inequality reduces a hypothetical counterexample to 6,0196{,}019 pairs of degree sequences. Each pair is excluded by an exact integer certificate for a system of neighborhood-type equations. The proof is computer-assisted; its mathematical reductions, finite search domains, classification representatives, and certificate conditions are given explicitly.

Author comments: Added a public, version-specific archive containing all 15 checked SAT refutations and CNF inputs, all 82 five-row extension inputs and outputs, and all 6,019 exact integer dual certificates, with generators and checking instructions. The manuscript now links release v1 and commit 10385847932cd2b61e25cb4e7d039633d108455b. The computational material was regenerated and independently checked on November 16, 2026.

Provenance statement

OpenAI Codex was used for mathematical exploration, finite-case verification, and manuscript preparation. The TeX source for this deposit was reconstructed from the authors’ supplied PDF using Codex and compared against that PDF. A companion Lean formalization was supplied with the manuscript. The computational supporting files for this revision were regenerated from the manuscript’s explicit constraints and representatives and the supplied Lean certificate data, then checked with drat-trim and independent Python integer computations.
AI provenance filesai-provenance.txt · 1 KB

Tools used

OpenAI
Codex
Lean
Lean

References

  1. A. F. Collins, A. W. N. Riasanovsky, J. C. Wallace, and S. P. Radziszowski, Zarankiewicz numbers and bipartite Ramsey numbers , arXiv:1604.01257 [math.CO], 2016. doi:10.48550/arXiv.1604.01257 (https://doi.org/10.48550/arXiv.1604.01257).arXivDOI
  2. R. K. Guy, A many-facetted problem of Zarankiewicz , in The Many Facets of Graph Theory (G. Chartrand and S. F. Kapoor, eds.), Lecture Notes in Mathematics, vol. 110, Springer, Berlin, 1969, pp. 129--148. doi:10.1007/BFb0060112 (https://doi.org/10.1007/BFb0060112).DOI
  3. OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences , entry A006625, https://oeis.org/A006625, accessed November 9, 2026.link
  4. E. Rosero, Zarankiewicz numbers z(m,n;3,4)z(m,n;3,4): SAT witnesses and DRAT-certified exact values (OEIS A006615 and A006625) , Zenodo, 2026. doi:10.5281/zenodo.21814869 (https://doi.org/10.5281/zenodo.21814869).DOI

Version history

  1. v1 · 12 pagesSubmitted by Jensen KohlmeyerAdded a public, version-specific archive containing all 15 checked SAT refutations and CNF inputs, all 82 five-row extension inputs and outputs, and all 6,019 exact integer dual certificates, with generators and checking instructions. The manuscript now links release v1 and commit 10385847932cd2b61e25cb4e7d039633d108455b. The computational material was regenerated and independently checked on November 16, 2026.CurrentNov 16, 2026