New Exact Values and Improved Lower Bounds for Zarankiewicz Numbers z(m,n;3)
Abstract
We present 44 new exact values and 31 improved lower bounds for the Zarankiewicz number z(m,n;3), the maximum number of ones in an m×n binary matrix containing no 3×3 all-ones submatrix. Our results extend the known table from m ≤ 9 to m ≤ 14 for exact values, and provide new lower bounds up to m = 18. In particular, we establish z(17,17;3) ≥ 138, contributing a new lower bound for the 15th term of OEIS sequence A001198 (Zarankiewicz's problem k 3 (n)), which previously had 14 known terms ending at z(16;3) = 129. All constructions and proofs are certified.
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Topology and Set Theory
Analytic Number Theory Research
Publication details
- Journal / source
- SSRN Electronic Journal
- Publisher
- Elsevier BV
- Publication date
- 1 January 2026
- Language
- EN
- Document type
- Preprint