Research · Papers · Exact answers in open problems · ML-091
Partial degree-cube search wall for Zarankiewicz number z(16,17;3)
z(16,17;3) ∈ {132, 133} undecided; d = 17..11 refuted with DRAT, 8 of 46 row-2 sub-cubes at d ∈ {9, 10} undecided at 7200 s
Published 2026-09-06
For everyone
Plain summary
The Zarankiewicz problem asks for the maximum number of connections between two separate groups of items without forming a complete grid of a given size. For groups of sizes 16 and 17 avoiding a 3-by-3 grid, the answer is either 132 or 133. Logic solvers cannot test the 133-connection case all at once. Splitting the search by the connection count of the densest row ruled out all cases from 17 down to 11 connections with verified proofs. Eight sub-cases with 10 and 9 connections timed out at two hours each. Across 105 verified refutations, no valid 133-connection grid appeared, which points to 132 as the likely answer, though the question remains open.
Result
The Zarankiewicz value z(16,17;3) ∈ {132, 133} remains undecided. Monolithic SAT runs on kissat and CaDiCaL across three symmetry-breaking modes return UNKNOWN at 3600 s.
Under degree-cube decomposition ordered by maximum row degree d, all sub-cubes for d = 17..11 are refuted with verified DRAT certificates. For d ∈ {9, 10}, 8 of 46 row-2 sub-cubes remain undecided at a 7200 s timeout per sub-cube.
Setting and definitions
The Zarankiewicz number z(m,n;k) is the maximum number of 1s in an m × n binary matrix containing no k × k submatrix of all 1s, or the maximum edge count of a bipartite graph on parts of sizes m and n avoiding K(k,k).
The target problem tests whether a 16 × 17 binary incidence matrix with weight 133 avoids a 3 × 3 all-ones submatrix. Degree-cube decomposition partitions the search space by the Hamming weight d of the highest-weight row, then branches on the weights and assignments of subsequent rows (row-2 and row-3 sub-cubes). All refutations are certified via DRAT and checked with drat-trim.
Method
Monolithic kissat and CaDiCaL runs across three symmetry-breaking encodings timed out at 3600 s.
Degree-cube decomposition partitioned candidate 133-weight matrices by maximum row degree d. All cases with d = 17..11 were refuted and certified in DRAT (MF-186). For d ∈ {9, 10}, branching through row-2 generated 46 sub-cubes, leaving 8 unresolved at 7200 s each.
Refutation cost grew by roughly 3.2x per unit decrease of d. DRAT proofs ran 1 GB to 20 GB per refuted sub-cube, with drat-trim verification taking about 0.8x of solver runtime.
Splitting the 8 surviving sub-cubes on row-3 assignments yielded 354 child sub-cubes, with 43 verified at wrap-up. Across 105 completed refutations, no satisfying assignment occurred. Artifacts reside in frontier/zarankiewicz/long/status.json, PROGRESS.box.log, proofs/, and lane WALL.md.
Discussion
The value z(16,17;3) remains open between 132 and 133, and the entry is LIVE-PARKED while row-3 child branches complete.
Single-row degree-cube branching hits a wall at d ∈ {9, 10} under the 3.2x per-degree cost scaling. The absence of satisfying assignments across 105 verified refutations points to z(16,17;3) = 132, but confirming that bound requires finishing the remaining row-3 branches.
For everyone — the takeaway
What this means
Finding z(16,17;3) pushes the limits of automated search on bipartite networks. Because solvers choke on the entire 16-by-17 grid at once, the search must be split row by row. While 8 out of 46 second-row patterns timed out at two hours, all 105 completed sub-problems proved impossible. The true maximum is almost certainly 132, but confirming it requires finishing the remaining third-row splits.
Attribution and prior art
Sources: Afrasyab 2026 · Hou 2026
Register references
- Entry: ML-091
- Refutation certificates: MF-186
- Receipts: box
frontier/zarankiewicz/long/status.json,PROGRESS.box.log,proofs/, laneWALL.md
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 3 of 3 receipt files bundled (4 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-06The result z(16,17;3) = 132 is not yet final: 253 subcases (71 % of the deepest level) remain undecided, including the known optimum (MF-186 addendum). Although (10,10,5) is closed, confirmation requires resolving all remaining leaves, independent cross-solver verification, and complete pipeline calibration on 14x17.
- 2026-09-06Row 2 is final at 62/70 resolved cases, leaving the theorem dependent on row 3, where 102/354 cases are verified, 252 remain, and the known optimum shape (9, 9, 5, 2, 2, 2, 3) remains undecided. A replay check verified 2/13 proofs with 0 failures, independently confirming the newly eliminated branch.
- 2026-09-06An independent check has verified the published lower bound z(14,17;3) >= 118. Full verification remains in progress as the refutation search for target 119 passes the halfway point, with 181 cases verified and 160 outstanding.