Research · Papers · Exact answers in open problems · MF-186
Maximum row degree bound for 16×17 Zarankiewicz extremal matrices
If A ∈ {0,1}^{16×17} has 133 ones and no 3×3 all-ones submatrix, then max row degree of A is ≤ 10
Published 2026-09-06
For everyone
Plain summary
A zero-one matrix is a grid of numbers where every entry is either 0 or 1. A classic mathematical challenge, the Zarankiewicz problem, asks for the maximum number of 1s that can be placed in such a grid without creating any subgrid of a specified size made entirely of 1s. For a 16-by-17 grid avoiding 3-by-3 all-one submatrices, prior work from August 2026 narrowed the maximum total number of 1s down to either 132 or 133.
This result establishes a structural limit on any potential 133-one configuration: no single row can contain 11 or more 1s. Simple arithmetic arguments rule out rows with 13 to 17 ones, but they fail for rows with 11 or 12 ones. By translating the remaining configurations into propositional logic formulas and running automated theorem provers, every case with 11 or 12 ones in a row was proven impossible. These computer-generated proofs were independently verified, guaranteeing that any 133-one matrix must have row counts of 10 or fewer.
Result
Let A ∈ {0,1}^(16×17) be a zero-one matrix with exactly 133 ones that contains no 3×3 all-ones submatrix. Then the maximum row degree of A is at most 10.
Equivalently, if the Zarankiewicz number z(16,17;3) = 133, then any extremal matrix achieving this bound has all row degrees ≤ 10.
Setting and definitions
The Zarankiewicz number z(m,n;s,t) denotes the maximum number of ones in an m×n zero-one matrix containing no s×t submatrix consisting entirely of ones. Here, s = t = 3, m = 16, and n = 17, abbreviated as z(16,17;3).
The row degree of row i in A is the number of ones in row i. A matrix A is in row-degree-normal form if its rows are sorted in non-increasing order of degree, ties are broken lexicographically, and its columns are permuted so that the maximum-degree row has its ones aligned as a prefix 1^d 0^(17-d), where d is the maximum row degree.
Method
The result was established via an exhaustive decomposition across row-degree-normal form cubes for d = 17 down to d = 11:
- Soundness of the normal form decomposition is established by a strictly increasing potential argument, which was independently re-derived by the verifier.
- For d = 13..17, elementary double-counting bounds yield maximum matrix weight upper bounds of 131, 130, 132, 121, and 110 respectively. Because each bound is strictly less than 133, all d ≥ 13 are ruled out analytically without search.
- For d = 12 and d = 11, double-counting does not exclude total weight 133, representing the non-elementary core of the problem. These cases were split into SAT sub-cubes:
- d = 12: partitioned into 24 sub-cubes.
- d = 11: partitioned into 21 sub-cubes.
- All sub-cubes for d = 12 and d = 11 were solved to UNSAT. The solver generated DRAT proof certificates totaling up to 2.1 GB, which were checked and verified using drat-trim in runtimes up to 726 s.
Discussion
This result restricts the structure of hypothetical extremal configurations of weight 133, but it does not completely resolve whether z(16,17;3) is 132 or 133.
Two August-2026 papers left open whether z(16,17;3) ∈ {132, 133} (the register does not record the specific citations or authors of these papers). At the time this result was banked, the broader campaign to decide whether z(16,17;3) = 133 by exploring the remaining row degree cases (d = 10 and d = 9, followed by row-3 branching) was still actively running, with zero satisfying assignments encountered across any explored branch.
For everyone — the takeaway
What this means
Determining exact bounds for Zarankiewicz numbers is a central problem in extremal combinatorics, where direct searches quickly become intractable due to combinatorial explosion. For the 16-by-17 case avoiding 3-by-3 all-one patterns, researchers had narrowed the maximum weight to two possibilities: 132 or 133. This result proves that if a 133-weight solution exists, its ones must be distributed relatively evenly, with at most 10 ones in any single row. By definitively eliminating all asymmetric candidate matrices containing rows with 11 or more ones through certified proofs, this work substantially reduces the remaining search space required to determine the exact value of z(16,17;3).
Attribution and prior art
Prior art: Two papers from August 2026 left the exact value of z(16,17;3) in {132, 133} unresolved. Sources: Afrasyab 2026 · Hou 2026
Register references
- Entry ID: MF-186
- Candidates and proof receipts:
lanes/zarankiewicz-16-17-3/BANK-CANDIDATES.md(artifact ZAR-01),REPORT-LONG.md,VERIFY.md - Storage boxes and logs:
frontier/zarankiewicz/(containing cube CNFs, proofs, and drat-trim logs) andfrontier/zarankiewicz/long/(containing row-2 sub-cubes,cover.json,status.json, andPROGRESS.box.log) - Prior art: Two August-2026 papers leaving open z(16,17;3) ∈ {132, 133} (the register does not record specific author names or titles)
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 5 of 6 receipt files bundled (25 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.
- 2026-09-06An independent verification confirms the Zarankiewicz three-level cover is sound and complete with zero defects. Across 73,956 K33-free matrices and 380,800 clauses, the audit successfully reproduced all 9 first-row cubes (d >= ceil(133/16) = 9), 70 row-2 sub-cubes, and 354 row-3 children.