The Zarankiewicz number z(13,15;3,4)
Version 1 / Nov 16, 2026 / CC BY 4.0
Abstract
We establish : a binary matrix with 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 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.
Provenance statement
AI provenance filesai-provenance.txt · 1 KB
Tools used
- OpenAI
- Codex
- Lean
- Lean
References
- 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
- 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
- OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences , entry A006625, https://oeis.org/A006625, accessed November 9, 2026.link
- E. Rosero, Zarankiewicz numbers : 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
- 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