WorksMathematics
The Zarankiewicz number z(13,15;3,4)
Abstract
We establish : a binary matrix with ones necessarily contains an all-one submatrix on three rows and four columns. The lower bound is attained by a previously published construction of Rosero. For the upper bound, we exclude dense eight-row column neighborhoods by a finite classification and a complete extension check. The resulting local inequality reduces a hypothetical counterexample to pairs of degree sequences. Each pair is excluded by an exact integer certificate for a system of neighborhood-type equations. The proof is computer-assisted; its mathematical reductions, finite search domains, classification representatives, and certificate conditions are given explicitly.
Statement and notation
Place dots at intersections of thirteen horizontal rows and fifteen vertical columns. Require that every choice of three rows and four columns leaves at least one of their twelve intersections empty. How many dots can be placed? We prove that the answer is 114.
For positive integers , , , , let denote the largest number of ones in an binary matrix that contains no all-one submatrix on distinct rows and distinct columns. The selected rows and columns need not be consecutive. The order of the two parts matters: throughout this paper the forbidden submatrix has three rows and four columns.
Theorem 1.1. The exact value of the oriented Zarankiewicz number is
The general matrix problem appears in Guy’s treatment of the Zarankiewicz problem [2]. In the notation of OEIS A006625 [3], Theorem 1.1 gives . The construction establishing the lower bound is due to Rosero [4]; the upper bound is the result proved here.
If is a binary matrix, write for its number of ones and for the support of its th row, where . The avoidance condition is equivalent to
Two matrices are equivalent if one is obtained from the other by independent row and column permutations. This equivalence preserves all avoidance and extension questions considered below.
A superscript in a degree sequence indicates multiplicity; for example, means seven entries equal to eight and one entry equal to seven.
The proof has two finite components. First, a classification of matrices with 63 ones, together with extension checks, improves one local neighborhood bound from 64 to 62. Second, exact linear infeasibility certificates exclude every remaining pair of global degree sequences. These computations enter as explicit finite lemmas; the surrounding implications are proved below.
A construction with 114 ones
The following matrix is Rosero’s 114-one construction [4]:
Here each string is one row and its digits are the matrix entries in column order. Twelve rows have weight nine and one has weight six, so . Direct intersection of the triples of displayed rows gives
Consequently satisfies (1), proving .
Figure 1. The 114 occupied intersections of (2). Filled circles denote ones; open circles denote zeros. Every three rows have at most three filled columns in common. The construction is due to Rosero [4].
Smaller matrices and column neighborhoods
We use the following bounds, denoted by :
Thus . For these are the bounds in Table 4 of Collins, Riasanovsky, Wallace, and Radziszowski [1]. The same table states uniqueness, up to equivalence, of the matrix with 64 ones and no all-one submatrix.
| Support size | 1 | 2 | 3–7 | 8–12 | 13–19 | 20–29 | 30–38 |
| Cases | 3758 | 535 | 311 | 448 | 630 | 285 | 52 |
Table 4. Exact dual certificates, grouped by number of nonzero multipliers.
For completeness, the smaller values in (3) follow from elementary counting. If are column degrees of a matrix avoiding an all-one submatrix, then
For the area bound suffices. For , at most two columns have degree three, giving at most 30 ones. For , the inequality for gives at most ones. For , use for to obtain .
We next describe the unique 64-one matrix. Index its rows by . Its first eight columns have zero sets
Its other six columns have one sets
Call the resulting matrix . Its first eight columns have weight five and its last six have weight four, so . Each row has weight eight. Intersecting its 56 triples of row supports verifies that it avoids an all-one submatrix. By the cited uniqueness theorem, every 64-one matrix with this property is equivalent to . Alternatively, the fact that all its row degrees must be eight follows from : deletion of any row leaves at most 56 ones.
Lemma 3.1 (Column-neighborhood reduction). Let be a matrix satisfying (1). Choose a column and any rows whose entries in column are one. On deleting column from these rows, the resulting matrix contains no all-one submatrix.
Proof. Three rows and three columns of ones in the smaller matrix, together with column , would give three rows and four columns of ones in . □
When , write the smaller matrix as . After permuting columns, the eight corresponding rows of form , obtained by adjoining an all-one column. The other five rows of are unrestricted in this last column. In particular, every extension search below allows both possible entries there.
The 63-one classification
Call an avoiding matrix maximal if changing any zero to one creates an all-one submatrix. If is , , and avoids this submatrix, deleting a row shows that every row degree is at least 63 − 56 = 7. Its degree sequence is therefore obtained by adding a partition of seven to . There are fifteen possibilities, listed in Table 1.
| Row degrees | Equivalence classes | Ordered forms |
| 10 | 1521 | |
| 2 | 37 | |
| 3 | 14 | |
| 1 | 9 | |
| 0 | 0 | |
| 0 | 0 | |
| 1 | 4 | |
| 0 | 0 | |
| 0 | 0 | |
| 0 | 0 | |
| 0 | 0 | |
| 0 | 0 | |
| 0 | 0 | |
| 0 | 0 | |
| 0 | 0 | |
| Total | 17 | 1585 |
Table 1. The complete maximal 63-one classification. The last column counts distinct labeled forms satisfying both lexicographic orders specified in the proof.
If the degree sequence is and is not maximal, adding one permissible entry gives a matrix equivalent to . Thus is equivalent to a one-entry deletion of . Every other degree sequence has an entry greater than eight. No matrix with such a sequence can be extended to 64 ones, since all rows in a 64-one avoiding matrix have degree eight. Such a matrix is automatically maximal.
Lemma 4.1 (Finite classification). Up to equivalence, the maximal matrices with 63 ones and no all-one submatrix are exactly the seventeen matrices in Appendix A. Their degree sequences and class counts are given in Table 1.
Finite verification of Lemma 4.1. Here are the exact constraints and the completeness argument used for the classification. Fix a nonincreasing degree sequence in Table 1. A candidate is a binary array satisfying
Require columns to be nonincreasing in lexicographic order, and impose the same order on rows within each group of equal row degrees. These restrictions preserve at least one representative of every equivalence class: a lexicographically greatest row-major array in the finite permutation orbit satisfies both orders.
For , also require every zero in row eight to be blocked. Explicitly, whenever , there must be distinct such that
This is exactly the condition that adding the entry creates an all-one submatrix. A zero in any other row cannot be added, since the resulting 64-one matrix would have a row of degree nine. Thus (9) is equivalent to maximality here.
The constraints were checked as finite Boolean systems. To specify their encoding without a cardinality convention, an exact row degree is expressed by
For (8), use the disjunction of the nine negated entries for each . Lexicographic comparisons use prefix-equality variables. Condition (9) uses indicators for the three-entry products and for the choice of the pair ; the indicated sum is required to be at least two.
For each displayed representative, permute rows within equal-degree groups, sort the columns, and retain the forms whose rows also have the required order. Excluding every such form is expressed by the clause
The fifteen resulting residual systems are all unsatisfiable. This finite calculation was certified by propositional refutations, checked against the above constraints. Direct checks of the representatives give (7), (8), maximality, and disjoint orbits. The ordered-form counts are those in Table 1. Since any missing class would supply a satisfying assignment of a residual system, none is omitted.
Five-row extensions
For an avoiding matrix , put , where is its th row support. Define
This set is determined by testing the subsets of . Let and . Any five-row extension with at least 115 ones requires five members of with total weight at least . A member of weight below cannot occur in such an extension and may be deleted from the list.
Order the remaining list as in nonincreasing weight, breaking ties by the binary word. The following recursion specifies the complete extension test. Its state consists of a list of chosen new rows, a smallest permitted index , and the current weight . Put .
If , accept precisely when .
For each , stop the loop if .
Otherwise, proceed with only if
Recurse at .
The same index is retained, so repeated new rows are allowed. They are rejected only if the actual intersection conditions fail. The recursion accepts if one branch accepts and rejects otherwise.
Lemma 5.1 (Complete extension test). The recursion accepts if and only if extends by five rows to a matrix satisfying (1) with at least 115 ones.
Proof. Three old rows satisfy (1), since their intersection in has size at most two. Two old rows and one new row are checked by (10). One old row and two new rows, and three new rows, are exactly the two tests in step (iii). Thus an accepted list gives a valid extension.
Conversely, order the five rows of any valid extension by their indices in the list. A row deleted by the weight cutoff could not reach the target even if each of the other four rows had weight . At every state along the branch representing this extension, the remaining rows have weight at most the current list entry. Hence the weight bound in step (ii) cannot discard that branch. The intersection tests also pass, so the branch accepts. □
Lemma 5.2 (Dense neighborhoods do not extend). If is an avoiding matrix with , then has no avoiding five-row extension with at least 115 ones.
Finite verification. If , the uniqueness theorem gives . If , Section 4 gives either a maximal representative or a one-entry deletion of . Apply the complete recursion above to these finite lists. Its output is rejection in all cases, as summarized in Table 2.
| Base matrix or family | Bases tested | Target | Accepted |
| 1 | 43 | 0 | |
| One-entry deletions of | 64 | 44 | 0 |
| 10 | 44 | 0 | |
| 2 | 44 | 0 | |
| 3 | 44 | 0 | |
| 1 | 44 | 0 | |
| 1 | 44 | 0 |
Table 2. Exhaustive extension tests. All rows allow both values in the adjoined column. The 64 deletions are tested separately, without assuming they are inequivalent.
As a further description of the 64-one case, the individual-row test gives when , with exactly four possibilities of weight nine, and when . Thus a row containing the adjoined position would limit the total new weight to . With that position absent, total weight at least 43 requires five weight-nine rows, four weight-nine rows and a row of weight at least seven, or three weight-nine rows and two weight-eight rows. Repetition of a weight-nine row fails an intersection test, and the remaining cases are rejected by the same recursion. □
Corollary 5.3 (Improved local bound). Define
In a 115-one matrix satisfying (1), any rows incident with a fixed column contain at most ones outside that column.
Proof. Lemma 3.1 and (3) give the bound unless . In that case the smaller matrix has at most 64 ones, and Lemma 5.2 excludes 63 and 64. This also applies to any eight-row subset of a larger column neighborhood. □
Global degree sequences
Suppose a counterexample has exactly 115 ones. Let its row degrees be and its column degrees . Then
Indeed, every triple of rows occurs in at most three column neighborhoods, proving (13). For each column , Corollary 5.3 gives
Summing over columns gives (14).
At fixed sum 115, the least possible row moment is
To see this, replacing two integer degrees by strictly decreases the sum of . Hence the minimizing sequence has two eights and eleven nines.
Lemma 6.1 (Finite list of degree pairs). There are 750 nondecreasing column-degree sequences in satisfying (12), (13), and . Together with all nondecreasing row-degree sequences in satisfying (12) and (14), they give exactly 6,019 pairs. In these pairs, every row degree lies in and every column degree in .
Finite enumeration. For a nondecreasing list of length , remaining sum , previous entry , and maximum permitted entry , choose the next entry from
Recurse with ; discard a state if or . Accept an empty list precisely when . For columns begin with , accumulating and ; discard as soon as the former exceeds 858, and require the latter to be at least 904 at completion. For each accepted column list, generate rows from , accumulating and discarding whenever the sum exceeds the corresponding column bound. All accumulated moment costs are nonnegative, so these prunings are valid. Evaluation gives the stated counts. The initial degree domains include zero; the narrower ranges in the statement are outputs, not assumptions.
Neighborhood types and exact certificates
Fix a pair of sequences in Lemma 6.1. Let be the number of rows of degree and the number of columns of degree . Write
These are sets of positive degrees by the finite enumeration.
| Column sequences | Row sequences per column | Pairs | |
| 904 | 48 | 1 | 48 |
| 905 | 41 | 1 | 41 |
| 906 | 70 | 3 | 210 |
| 907 | 64 | 3 | 192 |
| 908 | 93 | 5 | 465 |
| 909 | 78 | 5 | 390 |
| 910 | 98 | 8 | 784 |
| 911 | 64 | 8 | 512 |
| 912 | 85 | 14 | 1190 |
| 913 | 37 | 14 | 518 |
| 914 | 43 | 21 | 903 |
| 915 | 13 | 21 | 273 |
| 916 | 12 | 30 | 360 |
| 917 | 3 | 30 | 90 |
| 918 | 1 | 43 | 43 |
| Total | 750 | 6019 |
Table 3. Degree enumeration grouped by the value .
Definition 7.1. For , a row type is an integer vector satisfying
Let denote its finite set of possibilities. For , a column type is an integer vector satisfying
with the following additional requirement. Sort the multiset containing copies of as . Require
Let denote the resulting finite set.
Lemma 7.2. The neighborhood of every degree- row has a type in , and the neighborhood of every degree- column has a type in .
Proof. For a fixed row, each pair of the other twelve rows shares at most three of its incident columns. Thus
which gives (17); the availability constraints and degree sum are immediate. For a fixed column, Corollary 5.3 bounds the sum of over each -element subset of its neighbors. The largest such sum is the prefix of length in nonincreasing order. This is exactly (19). □
Associate a nonnegative variable with every and a nonnegative variable with every . Counting vertices of each degree and counting incidences in two ways gives the equations
An actual matrix provides nonnegative integer values of these variables. It therefore provides a nonnegative real solution as well.
Lemma 7.3 (Certificate criterion). Suppose numbers , , satisfy
Proof. Multiply (20), (21), and (22) by , , and , respectively, and add. The left side is nonnegative by (23) and (24), while the right side is negative by (25). □
Lemma 7.4 (Finite degree obstruction). For each of the 6,019 degree pairs in Lemma 6.1, there exist integer multipliers satisfying (23)–(25).
Exact finite verification. For each degree pair, the sets in Definition 7.1 are enumerated over their stated integer boxes, retaining precisely the vectors that satisfy the displayed sums and prefix bounds. Integer multipliers are then checked by evaluating the left sides of (23) and (24) for every retained vector and the integer sum in (25). All 6,019 cases pass these tests. No approximate inequality is used: the checked conditions are coefficientwise nonnegativity and a strictly negative integer. The largest absolute multiplier in these certificates is 3334. Table 4 records their support sizes.
Here is a nontrivial example with all its multipliers displayed. Take
In increasing degree order, let
The nonnegative coefficients can also be seen directly. For a degree-eight row, seven neighbors of degrees eight or nine would contribute at least to (17), since only one degree-eight column is available. Thus , as required by its coefficient . A degree-ten row has at most seven neighbors of degrees six or seven, so , as required by its coefficient . Degree-nine rows have coefficient zero.
For a degree-eight column, the full prefix bound gives , so its coefficient is nonnegative. For a degree-nine column, would make its largest eight weights at least 64, which is impossible. The smallest weight is therefore seven, and the eight-element prefix bound gives . Hence its coefficient is nonnegative. Degree-six and degree-seven columns have coefficient zero. Finally, the right side is
Thus even this degree pair cannot occur. The same finite coefficient test, with the corresponding integer multipliers, excludes each of the enumerated pairs. □
Proof of Theorem 1.1. Section 2 gives the lower bound 114. Suppose an avoiding matrix had at least 115 ones. Delete ones, if needed, to obtain exactly 115; deleting ones cannot create a forbidden submatrix. Corollary 5.3 then applies, so its degree sequences belong to the list in Lemma 6.1. By Lemma 7.2, the matrix gives a nonnegative solution of (20)–(22). Lemma 7.4 and the certificate criterion rule out such a solution. This contradiction proves the upper bound 114. □
Computational proof files
The complete computational material for the upper bound is publicly available in computational proof archive, release v1. The corresponding version-specific source tree is fixed at commit 10385847932cd2b61e25cb4e7d039633d108455b. The archive includes all fifteen residual SAT inputs and their complete DRAT refutations, the five-row extension inputs and outputs for all 82 bases in Table 2, and all 6,019 integer dual certificates together with their degree sequences. It also supplies the input generators, exact verification scripts, dependency versions, and checking instructions.
These files were regenerated on November 16, 2026 from the constraints and representatives displayed in this paper and the integer certificate data in the supplied companion Lean file. The regeneration reproduces the 1,585 ordered forms in Table 1, all fifteen unsatisfiable residual systems, all 82 rejected extension tests, and the degree and certificate counts in Tables 3 and 4. Each DRAT refutation was independently checked with drat-trim. The dual certificates were checked with exact Python integer arithmetic over every admissible type.
The archive’s README.md gives a single verification command that checks file hashes, regenerates the SAT inputs, checks the refutations, reruns the extension searches, and verifies every dual certificate. The included companion Zarankiewicz1315.lean retains its supplied toolchain and dependency information. The recorded archive checks concern the computational components listed above. The release ZIP has SHA-256
07f3d6338b4597eb65bba0bd688fc29bf2919a91647d594ff2f8eff1b39979ff.
Acknowledgment of AI assistance
OpenAI Codex was used for mathematical exploration, finite-case verification, and preparation of this manuscript.
References
Appendix A. The seventeen maximal representatives
The matrices below are the representatives in Lemma 4.1. Each displayed binary string is one row, with columns read from left to right. The labels correspond to the families in Table 2. These matrices are used only as bases; the all-one fifteenth column is adjoined when applying the extension test.
Email address: [email protected]
Email address: [email protected]
Email address: [email protected]
Email address: [email protected]
References
- [1]A. F. Collins, A. W. N. Riasanovsky, J. C. Wallace, and S. P. Radziszowski, Zarankiewicz numbers and bipartite Ramsey numbers, arXiv:1604.01257 [math.CO], 2016. doi:10.48550/arXiv.1604.01257.DOI
- [2]R. K. Guy, A many-facetted problem of Zarankiewicz, in The Many Facets of Graph Theory (G. Chartrand and S. F. Kapoor, eds.), Lecture Notes in Mathematics, vol. 110, Springer, Berlin, 1969, pp. 129–148. doi:10.1007/BFb0060112.DOI
- [3]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, entry A006625, https://oeis.org/A006625, accessed November 9, 2026.
- [4]E. Rosero, Zarankiewicz numbers z(m,n;3,4). SAT witnesses and DRAT-certified exact values (OEIS A006615 and A006625), Zenodo, 2026. doi:10.5281/zenodo.21814869.DOI
