Source-linked AI summary
Five improved lower bounds for Zarankiewicz numbers z(m,n;3,3)
Abhishek Saurabh
TL;DR
The note addresses limited exact knowledge of Zarankiewicz numbers for s = t = 3 by constructing and verifying explicit K3,3-free matrices. It reports five improved lower bounds, with two obtained by monotone padding, and provides independently checkable witnesses and verification materials.
Problem
Exact values for s = t = 3 are known only in a limited range, so many relevant cells remain represented by lower and upper bounds.
Method
The note uses kicked-greedy local search to find fixed-shape 0/1 matrices, then verifies them by exhaustive row-triple/column-triple inspection and independent implementations.
Results
The note establishes five improved lower bounds: three from explicit matrices and two from monotone padding.
Takeaways & Limitations
Each of the five bounds is backed by an explicit witness that readers can verify exactly and cheaply.
Takeaways & Limitations
The wall-clock-budgeted stochastic search is not bit-reproducible from a seed alone, so rerunning it is not claimed to reproduce the matrices.
Abstract
from arXiv · showhide
We record five improved lower bounds for Zarankiewicz numbers with s = t = 3: z(13,19;3,3) >= 118, z(14,19;3,3) >= 126, z(16,18;3,3) >= 136, z(14,20;3,3) >= 126, z(16,19;3,3) >= 136. The first three are certified by explicit K_{3,3}-free 0/1 matrices; the last two follow from the second and third by monotone padding. Compared with the lower bounds compiled in Figure 2 of arXiv:2605.01120, namely 114, 121, 130, 125 and 132, the improvements are +4, +5, +6, +1 and +4 respectively. The three matrices were produced by a kicked-greedy local search operated autonomously by a discovery system and were verified exactly, by exhaustive inspection of every 3x3 row/column triple, in several mutually independent implementations; they were also re-verified independently by the authors of arXiv:2605.01120 using their own verifier in July 2026. All three witnesses are printed in full in Appendix A and accompany this note as machine-readable ancillary files together with standalone, dependency-free verifiers.
1. Introduction
For s = t = 3, exact Zarankiewicz values are known only in a limited range, so current knowledge consists largely of computational lower bounds and theoretical or exhaustive upper bounds. This note makes a narrow contribution by improving five lower bounds with explicit, cheaply verifiable witnesses.
- Exact values for s = t = 3 are known only in a limited range, leaving a table of lower and upper bounds.
- Computer search produces most lower bounds, while counting, optimization, exhaustive, and SAT-based methods produce upper bounds.
- The compilation in Figure 2 of [2] supplies the previous lower bounds improved by this note.
- The note reports five improved lower bounds, each supported by an explicit witness verifiable in under a second on a laptop.
- The contribution makes no claim of novelty for the standard kicked-greedy local search and no claim about upper bounds.
2. The bounds
The note establishes three lower bounds using explicit K3,3-free 0/1 matrices and derives two more by monotone padding. Together, these give improved bounds in five cells.
- The bounds: z(13, 19; 3, 3) ≥118, z(14, 19; 3, 3) ≥126, and z(16, 18; 3, 3) ≥136.The three displayed matrices have the stated numbers of 1s and contain no all-ones 3 × 3 submatrix.
- The bounds: The three primary witnesses are checked by inspecting every row-triple/column-triple pair.The stated check counts are 277,134, 352,716, and 456,960 for the three matrices, respectively.
- The bounds: Monotone padding gives z(14, 20; 3, 3) ≥126 and z(16, 19; 3, 3) ≥136 from the preceding bounds.Appending an all-zero column preserves the number of 1s and cannot create an all-ones forbidden submatrix.
- The bounds: Corollary 3 is bookkeeping rather than search because the padded cells inherit bounds from smaller cells.
3. Method
The witnesses were found by kicked-greedy local search over fixed-shape 0/1 matrices and verified exactly by multiple independent implementations. The search is not claimed to be bit-reproducible from a seed alone, but the explicit matrices remain cheaply verifiable.
- Search: Kicked-greedy local search alternates greedy saturation with randomized kicks that delete a small set of 1s before re-saturating.
- Search: K3,3-freeness is enforced as a hard constraint, so every recorded intermediate state is a valid witness.The objective is the exact count of 1s rather than a penalized surrogate.
- Search: NOVA selected target cells, ran searches, and packaged results, while the underlying mathematical search method remained standard.
- Provenance: The individual runs used fixed seeds and wall-clock budgets, with recorded dates and kick counts for two of the three cells.
- Verification and scope: The search is not bit-reproducible from a seed alone, but the claims concern explicit matrices that can be verified exactly and cheaply.
- Verification and scope: Verification recomputed 1-counts and exhaustively enumerated row-triple/column-triple pairs using several code-independent implementations.The authors of [2] independently re-verified the matrices with their own verifier in July 2026.
4. Summary of the five cells
Table 1 collects five improved lower bounds for z(m, n; 3, 3), with three supplied by Theorem 1 and two obtained by padding.
- Summary of the five cells: +4, +5, +6, +1 and +4 are the improvements over the previous lower bounds for the five listed cells.The previous lower bounds are compiled in Figure 2 of [2].
- Summary of the five cells: The (16,18) witness has row sums consisting of eight 9s and eight 8s, with column sums (92, 88, 76, 62).The exponents in the profile denote multiplicities.
- Summary of the five cells: A fourth witness gives z(13,17;3,3) ≥ 110, matching the upper bound and yielding the exact value reported elsewhere.The note records this only as contextual chronology, not as one of its five claimed results.
Appendix A. The witness matrices
Appendix A presents the witness matrices as row-wise bitstrings, including the two padded constructions for the enlarged cells.
- Appendix A. The witness matrices: Each matrix is printed as one row per line, using a left-to-right string of n characters from {0, 1}.The same bitstring representation appears in the ancillary files and JSON.
- Appendix A. The witness matrices: The 14 × 20 witness is A14×19 with one appended 0 in every row.This supplies the padded construction for z(14,20;3,3) ≥ 126.
- Appendix A. The witness matrices: The 16 × 19 witness is A16×18 with one appended 0 in every row.This supplies the padded construction for z(16,19;3,3) ≥ 136.
Appendix B. Verification recipe
Appendix B describes standalone Python verifiers that recompute each witness’s shape, weight, and K_{3,3}-freeness from its embedded matrix.
- Appendix B. Verification recipe: Each verifier checks the matrix shape and confirms every entry belongs to {0, 1}.These are the first two checks performed by every script.
- Appendix B. Verification recipe: The complete verification requires only Python 3, the standard library, and no third-party packages, network access, or build step.A manual transcription and implementation of the same checks is also possible.
- Appendix B. Verification recipe: The scripts recompute the number of 1s and reject any discrepancy with the recorded threshold.The count is derived from the matrix rather than trusted from a label.
- Appendix B. Verification recipe: Every triple of rows and triple of columns is inspected, and verification fails if any resulting 3×3 submatrix is all-ones.This directly checks the K_{3,3}-free condition.
- Appendix B. Verification recipe: The padded-witness verifiers additionally remove the appended all-zero column and re-verify the underlying witness.This checks the padding lemma rather than assuming it.
- Appendix B. Verification recipe: The searched-witness scripts use stricter internal thresholds of 115, 124 and 132 than the published lower bounds 114, 121 and 130.Passing these thresholds implies passing the published bounds.