Five improved lower bounds for Zarankiewicz numbers z(m,n;3,3)

• Exact values for s = t = 3 are known only in a limited range, leaving a table of lower and upper bounds.Source: §1 · p. 1
• Computer search produces most lower bounds, while counting, optimization, exhaustive, and SAT-based methods produce upper bounds.Source: §1 · p. 1
• The compilation in Figure 2 of [2] supplies the previous lower bounds improved by this note.Source: §1 · p. 2
• The note reports five improved lower bounds, each supported by an explicit witness verifiable in under a second on a laptop.Source: §1 · p. 2
• The contribution makes no claim of novelty for the standard kicked-greedy local search and no claim about upper bounds.Source: §1 · p. 2

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.Source: §2 · p. 2
• 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.Source: §2 · p. 2
• 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.Source: §2 · p. 2
• Corollary 3 is bookkeeping rather than search because the padded cells inherit bounds from smaller cells.Source: §2 · p. 2

Search

• Kicked-greedy local search alternates greedy saturation with randomized kicks that delete a small set of 1s before re-saturating.Source: §3 · p. 3
• 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.Source: §3 · p. 3
• NOVA selected target cells, ran searches, and packaged results, while the underlying mathematical search method remained standard.Source: §3 · p. 3

Provenance

• The individual runs used fixed seeds and wall-clock budgets, with recorded dates and kick counts for two of the three cells.Source: §3 · p. 3

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.Source: §3 · p. 3
• 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.Source: §3 · p. 3

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].Source: §4 · p. 3
• 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.Source: §4 · p. 3
• 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.Source: §4 · p. 4

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.Source: Appendix A · p. 4
• 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.Source: The padded witnesses · p. 5
• 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.Source: The padded witnesses · p. 5

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.Source: Appendix B · p. 5
• 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.Source: Appendix B · pp. 5–6
• 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.Source: Appendix B · p. 5
• 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.Source: Appendix B · p. 5
• 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.Source: Appendix B · p. 5
• 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.Source: Appendix B · pp. 5–6