betaFeedback

WorksMathematics

The Zarankiewicz number z(13,15;3,4)

Abstract

We establish z(13,15;3,4)=114z(13,15;3,4)=114: a 13×1513\times15 binary matrix with 115115 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 6,0196{,}019 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 mm, nn, ss, tt, let z(m,n;s,t)z(m,n;s,t) denote the largest number of ones in an m×nm \times n binary matrix that contains no all-one submatrix on ss distinct rows and tt 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

z(13,15;3,4)=114.z(13,15;3,4)=114.

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 a(13)=115a(13)=115. The construction establishing the lower bound is due to Rosero [4]; the upper bound is the result proved here.

If AA is a binary matrix, write ∣A∣|A| for its number of ones and Ai⊆[n]A_i \subseteq[n] for the support of its iith row, where [n]={1,…,n}[n]=\{1,\ldots,n\}. The avoidance condition is equivalent to

∣Ai∩Aj∩Ak∣≤3(i,j,k distinct).(1)|A_i \cap A_j \cap A_k| \le3 \qquad(i,j,k\text{ distinct}). \tag*{(1)}

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, (87,7)(8^7,7) means seven entries equal to eight and one entry equal to seven.

The proof has two finite components. First, a classification of 8×148 \times14 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]:

A0=(0110101100011111101101111001100010100101111110101110000111101100010110010100111100111010001011101001101011110001011011101111011100111000000111110011011110111100100101011111010010110001001011101011).(2)A_0=\left(\begin{array}{c} 0110101100011111\\ 101101111001100\\ 010100101111110\\ 101110000111101\\ 100010110010100\\ 111100111010001\\ 011101001101011\\ 110001011011101\\ 111011100111000\\ 000111110011011\\ 110111100100101\\ 011111010010110\\ 001001011101011 \end{array}\right). \tag*{(2)}

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 ∣A0∣=12⋅9+6=114\lvert A_0\rvert=12\cdot9+6=114. Direct intersection of the (133)=286\binom{13}{3}=286 triples of displayed rows gives

#{{i,j,k}:∣A0,i∩A0,j∩A0,k∣=r}={11,r=0,0,r=1,72,r=2,203,r=3.\#\{\{i,j,k\}:\lvert A_{0,i}\cap A_{0,j}\cap A_{0,k}\rvert=r\}= \begin{cases} 11,&r=0,\\ 0,&r=1,\\ 72,&r=2,\\ 203,&r=3. \end{cases}

Consequently A0A_0 satisfies (1), proving z(13,15;3,4)≥114z(13,15;3,4)\ge114.

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 Z(d)Z(d):

d012345678910111213Z(d)014283036445056647077849198(3)\begin{array}{c|cccccccccccccc} d & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ \hline Z(d) & 0 & 14 & 28 & 30 & 36 & 44 & 50 & 56 & 64 & 70 & 77 & 84 & 91 & 98 \tag*{(3)} \end{array}

Thus z(d,14;3,3)≤Z(d)z(d,14;3,3) \le Z(d). For 6≤d≤136 \le d \le13 these are the bounds in Table 4 of Collins, Riasanovsky, Wallace, and Radziszowski [1]. The same table states uniqueness, up to equivalence, of the 8×148 \times14 matrix with 64 ones and no all-one 3×33 \times3 submatrix.

Support size123–78–1213–1920–2930–38
Cases375853531144863028552

Table 4. Exact dual certificates, grouped by number of nonzero multipliers.

For completeness, the smaller values in (3) follow from elementary counting. If q1,…,q14q_1,\ldots,q_{14} are column degrees of a d×14d \times14 matrix avoiding an all-one 3×33 \times3 submatrix, then

∑j=114(qj3)≤2(d3).(4)\sum_{j=1}^{14} \binom{q_j}{3} \le2\binom{d}{3}. \tag*{(4)}

For d=0,1,2d=0,1,2 the area bound suffices. For d=3d=3, at most two columns have degree three, giving at most 30 ones. For d=4d=4, the inequality q≤2+(q3)q \le2+\binom{q}{3} for 0≤q≤40 \le q \le4 gives at most 28+8=3628+8=36 ones. For d=5d=5, use 3q≤8+(q3)3q \le8+\binom{q}{3} for 0≤q≤50 \le q \le5 to obtain 3∑qj≤112+20=1323\sum q_j \le112+20=132.

We next describe the unique 64-one matrix. Index its rows by Z/8Z\mathbb{Z}/8\mathbb{Z}. Its first eight columns have zero sets

{i,i+1,i+3},i∈Z/8Z.(5)\{i,i+1,i+3\}, \qquad i \in\mathbb{Z}/8\mathbb{Z}. \tag*{(5)}

Its other six columns have one sets

{a,a+4,b,b+4},0≤a<b≤3.(6)\{a,a+4,b,b+4\}, \qquad0 \le a < b \le3. \tag*{(6)}

Call the resulting matrix GG. Its first eight columns have weight five and its last six have weight four, so ∣G∣=64|G|=64. Each row has weight eight. Intersecting its 56 triples of row supports verifies that it avoids an all-one 3×33 \times3 submatrix. By the cited uniqueness theorem, every 64-one 8×148 \times14 matrix with this property is equivalent to GG. Alternatively, the fact that all its row degrees must be eight follows from Z(7)=56Z(7)=56: deletion of any row leaves at most 56 ones.

Lemma 3.1 (Column-neighborhood reduction). Let AA be a 13×1513 \times15 matrix satisfying (1). Choose a column cc and any kk rows whose entries in column cc are one. On deleting column cc from these rows, the resulting k×14k \times14 matrix contains no all-one 3×33 \times3 submatrix.

Proof. Three rows and three columns of ones in the smaller matrix, together with column cc, would give three rows and four columns of ones in AA. □

When k=8k=8, write the smaller matrix as BB. After permuting columns, the eight corresponding rows of AA form (B∣1)(B \mid1), obtained by adjoining an all-one column. The other five rows of AA 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 3×33 \times3 submatrix. If BB is 8×148 \times14, ∣B∣=63|B|=63, and BB 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 (78)(7^8). There are fifteen possibilities, listed in Table 1.

Row degreesEquivalence classesOrdered forms
(87,7)(8^7,7)101521
(9,85,72)(9,8^5,7^2)237
(92,83,73)(9^2,8^3,7^3)314
(10,84,73)(10,8^4,7^3)19
(93,8,74)(9^3,8,7^4)00
(10,9,82,74)(10,9,8^2,7^4)00
(10,92,75)(10,9^2,7^5)14
(11,83,74)(11,8^3,7^4)00
(102,8,75)(10^2,8,7^5)00
(11,9,8,75)(11,9,8,7^5)00
(11,10,76)(11,10,7^6)00
(12,82,75)(12,8^2,7^5)00
(12,9,76)(12,9,7^6)00
(13,8,76)(13,8,7^6)00
(14,77)(14,7^7)00
Total171585

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 (87,7)(8^7,7) and BB is not maximal, adding one permissible entry gives a matrix equivalent to GG. Thus BB is equivalent to a one-entry deletion of GG. 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 8×148 \times14 matrices with 63 ones and no all-one 3×33 \times3 submatrix are exactly the seventeen matrices B1,…,B17B_1,\ldots,B_{17} 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 p=(p1,…,p8)p=(p_1,\ldots,p_8) in Table 1. A candidate is a binary array x=(xic)x=(x_{ic}) satisfying

∑c=114xic=pi(1≤i≤8),(7)\sum_{c=1}^{14}x_{ic}=p_i \qquad(1\le i\le8), \tag*{(7)}
∑i∈I,c∈Jxic≤8(I∈([8]3), J∈([14]3)).(8)\sum_{\substack{i\in I,c\in J}}x_{ic}\le8 \qquad\left(I\in\binom{[8]}{3},\ J\in\binom{[14]}{3}\right). \tag*{(8)}

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 p=(87,7)p=(8^7,7), also require every zero in row eight to be blocked. Explicitly, whenever x8c=0x_{8c}=0, there must be distinct i,j∈[7]i,j\in[7] such that

xic=xjc=1,∑q=114x8qxiqxjq≥2.(9)x_{ic}=x_{jc}=1,\qquad\sum_{q=1}^{14}x_{8q}x_{iq}x_{jq}\ge2. \tag*{(9)}

This is exactly the condition that adding the entry (8,c)(8,c) creates an all-one 3×33\times3 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 pip_i is expressed by

⋁c∈S¬xic(∣S∣=pi+1),⋁c∈Txic(∣T∣=15−pi).\bigvee_{c\in S}\neg x_{ic}\quad(|S|=p_i+1),\qquad\bigvee_{c\in T}x_{ic}\quad(|T|=15-p_i).

For (8), use the disjunction of the nine negated entries for each I,JI,J. Lexicographic comparisons use prefix-equality variables. Condition (9) uses indicators for the three-entry products and for the choice of the pair i,ji,j; 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

⋁i,cℓic,ℓic={xic,the excluded entry is 0,¬xic,the excluded entry is 1.\bigvee_{i,c}\ell_{ic},\qquad \ell_{ic}= \begin{cases} x_{ic}, & \text{the excluded entry is 0},\\ \neg x_{ic}, & \text{the excluded entry is 1}. \end{cases}

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. □\square

Five-row extensions

For an 8×148 \times14 avoiding matrix BB, put bi=Bi∪{15}b_i=B_i\cup\{15\}, where Bi⊆[14]B_i\subseteq[14] is its iith row support. Define

V(B)={v⊆[15]:∣v∩bi∩bj∣≤3 for all i<j}.(10)\mathcal{V}(B)=\{v\subseteq[15]: |v\cap b_i\cap b_j|\leq3\text{ for all }i<j\}. \tag*{(10)}

This set is determined by testing the 2152^{15} subsets of [15][15]. Let M(B)=max⁡v∈V(B)∣v∣M(B)=\max_{v\in\mathcal{V}(B)}|v| and T(B)=115−(∣B∣+8)T(B)=115-(|B|+8). Any five-row extension with at least 115 ones requires five members of V(B)\mathcal{V}(B) with total weight at least T(B)T(B). A member of weight below T(B)−4M(B)T(B)-4M(B) cannot occur in such an extension and may be deleted from the list.

Order the remaining list as v1,…,vLv_1,\ldots,v_L in nonincreasing weight, breaking ties by the binary word. The following recursion specifies the complete extension test. Its state consists of a list SS of chosen new rows, a smallest permitted index qq, and the current weight w=∑u∈S∣u∣w=\sum_{u\in S}|u|. Put h=5−∣S∣h=5-|S|.

  1. If h=0h=0, accept precisely when w≥T(B)w\geq T(B).

  2. For each j≥qj\geq q, stop the loop if w+h∣vj∣<T(B)w+h|v_j|<T(B).

  3. Otherwise, proceed with vjv_j only if

    ∣vj∩u∩bi∣≤3(u∈S, 1≤i≤8),|v_j\cap u\cap b_i|\leq3\qquad(u\in S,\ 1\leq i\leq8),
    ∣vj∩u∩u′∣≤3(u,u′ from distinct positions of S).|v_j\cap u\cap u'|\leq3\qquad(u,u'\text{ from distinct positions of }S).

Recurse at (S∥vj,j,w+∣vj∣)(S\mathbin{\|}v_j,j,w+|v_j|).

The same index jj 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 (B∣1)(B\mid1) extends by five rows to a matrix satisfying (1) with at least 115 ones.

Proof. Three old rows satisfy (1), since their intersection in BB 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 M(B)M(B). 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 BB is an 8×148 \times14 avoiding matrix with ∣B∣∈{63,64}|B| \in\{63, 64\}, then (B∣1)(B \mid1) has no avoiding five-row extension with at least 115 ones.

Finite verification. If ∣B∣=64|B| = 64, the uniqueness theorem gives B≅GB \cong G. If ∣B∣=63|B| = 63, Section 4 gives either a maximal representative BiB_i or a one-entry deletion of GG. Apply the complete recursion above to these finite lists. Its output is rejection in all cases, as summarized in Table 2.

Base matrix or familyBases testedTarget T(B)T(B)Accepted
GG1430
One-entry deletions of GG64440
B1,…,B10B_1, \ldots, B_{10}10440
B11,B12B_{11}, B_{12}2440
B13,B14,B15B_{13}, B_{14}, B_{15}3440
B16B_{16}1440
B17B_{17}1440

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 ∣v∣≤9|v| \le9 when 15∉v15 \notin v, with exactly four possibilities of weight nine, and ∣v∣≤6|v| \le6 when 15∈v15 \in v. Thus a row containing the adjoined position would limit the total new weight to 6+4⋅9=426 + 4 \cdot9 = 42. 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

W(k)={62,k=8,Z(k),k≠8.(11)W(k) = \begin{cases} 62, & k = 8,\\ Z(k), & k \ne8. \end{cases} \tag*{(11)}

In a 115-one 13×1513 \times15 matrix satisfying (1), any kk rows incident with a fixed column contain at most W(k)W(k) ones outside that column.

Proof. Lemma 3.1 and (3) give the bound unless k=8k = 8. 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 AA has exactly 115 ones. Let its row degrees be a1,…,a13a_1,\ldots,a_{13} and its column degrees d1,…,d15d_1,\ldots,d_{15}. Then

∑i=113ai=∑j=115dj=115,(12)\sum_{i=1}^{13} a_i=\sum_{j=1}^{15}d_j=115, \tag*{(12)}
∑j=115(dj3)≤3(133)=858,(13)\sum_{j=1}^{15}\binom{d_j}{3}\le3\binom{13}{3}=858, \tag*{(13)}
∑i=113ai(ai−1)≤∑j=115W(dj).(14)\sum_{i=1}^{13}a_i(a_i-1)\le\sum_{j=1}^{15}W(d_j). \tag*{(14)}

Indeed, every triple of rows occurs in at most three column neighborhoods, proving (13). For each column jj, Corollary 5.3 gives

∑i:Aij=1(ai−1)≤W(dj).\sum_{i:A_{ij}=1}(a_i-1)\le W(d_j).

Summing over columns gives (14).

At fixed sum 115, the least possible row moment is

2⋅8⋅7+11⋅9⋅8=904.(15)2\cdot8\cdot7+11\cdot9\cdot8=904. \tag*{(15)}

To see this, replacing two integer degrees u<v−1u<v-1 by u+1,v−1u+1,v-1 strictly decreases the sum of a(a−1)a(a-1). 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 [0,13]15[0,13]^{15} satisfying (12), (13), and ∑jW(dj)≥904\sum_j W(d_j)\ge904. Together with all nondecreasing row-degree sequences in [0,15]13[0,15]^{13} satisfying (12) and (14), they give exactly 6,019 pairs. In these pairs, every row degree lies in [6,12][6,12] and every column degree in [2,12][2,12].

Finite enumeration. For a nondecreasing list of length ℓ\ell, remaining sum ss, previous entry bb, and maximum permitted entry DD, choose the next entry from

b≤v≤min⁡(D,⌊s/ℓ⌋).(16)b\le v\le\min(D,\lfloor s/\ell\rfloor). \tag*{(16)}

Recurse with (ℓ−1,s−v,v,D)(\ell-1,s-v,v,D); discard a state if s<ℓbs<\ell b or s>ℓDs>\ell D. Accept an empty list precisely when s=0s=0. For columns begin with (15,115,0,13)(15,115,0,13), accumulating (v3)\binom{v}{3} and W(v)W(v); 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 (13,115,0,15)(13,115,0,15), accumulating v(v−1)v(v-1) 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. □\square

Neighborhood types and exact certificates

Fix a pair of sequences in Lemma 6.1. Let NaN_a be the number of rows of degree aa and MdM_d the number of columns of degree dd. Write

R={a:Na>0},D={d:Md>0}.R=\{a:N_a>0\},\qquad D=\{d:M_d>0\}.

These are sets of positive degrees by the finite enumeration.

CCColumn sequencesRow sequences per columnPairs
90448148
90541141
906703210
907643192
908935465
909785390
910988784
911648512
91285141190
9133714518
9144321903
9151321273
9161230360
91733090
91814343
Total7506019

Table 3. Degree enumeration grouped by the value C=∑jW(dj)C = \sum_j W(d_j).

Definition 7.1. For a∈Ra \in R, a row type is an integer vector t=(td)d∈Dt = (t_d)_{d\in D} satisfying

0≤td≤Md,∑d∈Dtd=a,∑d∈Dtd(d−12)≤198.(17)0 \le t_d \le M_d,\qquad\sum_{d\in D} t_d = a,\qquad\sum_{d\in D} t_d \binom{d-1}{2} \le198. \tag*{(17)}

Let Ta\mathcal{T}_a denote its finite set of possibilities. For d∈Dd \in D, a column type is an integer vector u=(ua)a∈Ru = (u_a)_{a\in R} satisfying

0≤ua≤Na,∑a∈Rua=d,(18)0 \le u_a \le N_a,\qquad\sum_{a\in R} u_a = d, \tag*{(18)}

with the following additional requirement. Sort the multiset containing uau_a copies of a−1a-1 as w1≥⋯≥wdw_1 \ge\cdots\ge w_d. Require

∑i=1kwi≤W(k)(1≤k≤d).(19)\sum_{i=1}^{k} w_i \le W(k) \qquad(1 \le k \le d). \tag*{(19)}

Let Ud\mathcal{U}_d denote the resulting finite set.

Lemma 7.2. The neighborhood of every degree-aa row has a type in Ta\mathcal{T}_a, and the neighborhood of every degree-dd column has a type in Ud\mathcal{U}_d.

Proof. For a fixed row, each pair of the other twelve rows shares at most three of its incident columns. Thus

∑j:Aij=1(dj−12)≤3(122)=198,\sum_{j:A_{ij}=1} \binom{d_j-1}{2} \le3\binom{12}{2}=198,

which gives (17); the availability constraints and degree sum are immediate. For a fixed column, Corollary 5.3 bounds the sum of ai−1a_i-1 over each kk-element subset of its neighbors. The largest such sum is the prefix of length kk in nonincreasing order. This is exactly (19). □

Associate a nonnegative variable Ya,tY_{a,t} with every t∈Tat \in\mathcal{T}_a and a nonnegative variable Qd,uQ_{d,u} with every u∈Udu \in\mathcal{U}_d. Counting vertices of each degree and counting incidences in two ways gives the equations

∑t∈TaYa,t=Na(a∈R),(20)\sum_{t \in\mathcal{T}_a} Y_{a,t} = N_a \qquad(a \in R), \tag*{(20)}
∑u∈UdQd,u=Md(d∈D),(21)\sum_{u \in\mathcal{U}_d} Q_{d,u} = M_d \qquad(d \in D), \tag*{(21)}
∑t∈TatdYa,t−∑u∈UduaQd,u=0(a∈R, d∈D).(22)\sum_{t \in\mathcal{T}_a} t_d Y_{a,t} - \sum_{u \in\mathcal{U}_d} u_a Q_{d,u} = 0 \qquad(a \in R,\ d \in D). \tag*{(22)}

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 αa\alpha_a, βd\beta_d, γad\gamma_{ad} satisfy

αa+∑d∈Dγadtd≥0(a∈R, t∈Ta),(23)\alpha_a + \sum_{d \in D} \gamma_{ad}t_d \ge0 \qquad(a \in R,\ t \in\mathcal{T}_a), \tag*{(23)}
βd−∑a∈Rγadua≥0(d∈D, u∈Ud),(24)\beta_d - \sum_{a \in R} \gamma_{ad}u_a \ge0 \qquad(d \in D,\ u \in\mathcal{U}_d), \tag*{(24)}
∑a∈RαaNa+∑d∈DβdMd<0.(25)\sum_{a \in R} \alpha_a N_a + \sum_{d \in D} \beta_d M_d < 0. \tag*{(25)}

Then (20)–(22) have no nonnegative solution.

Proof. Multiply (20), (21), and (22) by αa\alpha_a, βd\beta_d, and γad\gamma_{ad}, 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

(ai)=(85,95,103),(dj)=(65,72,8,97).(a_i) = (8^5,9^5,10^3), \qquad(d_j) = (6^5,7^2,8,9^7).

In increasing degree order, let

(α8,α9,α10)=(6,0,−3),(\alpha_8,\alpha_9,\alpha_{10}) = (6,0,-3),
(β6,β7,β8,β9)=(0,0,−2,−3),(\beta_6,\beta_7,\beta_8,\beta_9) = (0,0,-2,-3),
(γad)a∈R,d∈D=(00−1−100000011).(26)(\gamma_{ad})_{a\in R,d\in D} = \begin{pmatrix} 0 & 0 & -1 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{pmatrix}. \tag*{(26)}

The nonnegative coefficients can also be seen directly. For a degree-eight row, seven neighbors of degrees eight or nine would contribute at least 21+6⋅28+10=19921+6\cdot28+10=199 to (17), since only one degree-eight column is available. Thus t8+t9≤6t_8+t_9\le6, as required by its coefficient 6−t8−t96-t_8-t_9. A degree-ten row has at most seven neighbors of degrees six or seven, so t8+t9≥3t_8+t_9\ge3, as required by its coefficient −3+t8+t9-3+t_8+t_9. Degree-nine rows have coefficient zero.

For a degree-eight column, the full prefix bound gives 64−u8+u10≤6264-u_8+u_{10}\le62, so its coefficient −2+u8−u10-2+u_8-u_{10} is nonnegative. For a degree-nine column, u8=0u_8=0 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 65−u8+u10≤6265-u_8+u_{10}\le62. Hence its coefficient −3+u8−u10-3+u_8-u_{10} is nonnegative. Degree-six and degree-seven columns have coefficient zero. Finally, the right side is

6⋅5−3⋅3−2⋅1−3⋅7=−2.6\cdot5-3\cdot3-2\cdot1-3\cdot7=-2.

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 13×1513\times15 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 8×148 \times14 bases; the all-one fifteenth column is adjoined when applying the extension test.

B1=(1111111100000011111000111000110001100110101010010110110110010011011011001011010111100001111010101100110001110101)B_1=\begin{pmatrix} 11111111000000\\ 11111000111000\\ 11000110011010\\ 10100101101101\\ 10010011011011\\ 00101101011110\\ 00011110101011\\ 00110001110101 \end{pmatrix}
B2=(1111111100000011110000111100110011011001101100000101111100111100011011001010111011100000101110110110011001110001)B_2=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001101100110\\ 11000001011111\\ 00111100011011\\ 00101011101110\\ 00001011101101\\ 10011001110001 \end{pmatrix}
B3=(1111111100000011110000111100110011001001001010001110101101011010010111001111011001100000011111110101001100011110)B_3=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001100100100\\ 10100011101011\\ 01011010010111\\ 00111101100110\\ 00000111111101\\ 01001100011110 \end{pmatrix}
B4=(1111111100000011110000111100110011001100111010001110101101101010010111001111011001100000011111110110010110010100)B_4=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001100110011\\ 10100011101011\\ 01101010010111\\ 00111101100110\\ 00000111111101\\ 10010110010100 \end{pmatrix}
B5=(1111111100000011110000111100110011001100101010001110101101101010010111001111011001100000011111110110010110010110)B_5=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001100110010\\ 10100011101011\\ 01101010010111\\ 00111101100110\\ 00000111111101\\ 10010110010110 \end{pmatrix}
B6=(1111111100000011110000111100110010001110111010111010011001000111010111001101011010110001101110110100110010100110)B_6=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001000111011\\ 10101110100110\\ 01000111010111\\ 00110101101011\\ 00011011101101\\ 00110010100110 \end{pmatrix}
B7=(1111111100000011110000111100110011001100111100001100111100111010101011001010101010110000111111110010010110010110)B_7=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001100110011\\ 11000011001111\\ 00111010101011\\ 00101010101011\\ 00001111111100\\ 10010110010110 \end{pmatrix}
B8=(1111111100000011110000111100110011001100111000101110111001000111101101001110100110110010101101011110100110010110)B_8=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001100110011\\ 10001011101110\\ 01000111101101\\ 00111010011011\\ 00101011010111\\ 10100110010110 \end{pmatrix}
B9=(1111111100000011110000111100110011001100111000101110111011000110101101001101100101110001110110110101011010101001)B_9=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001100110011\\ 10001011101110\\ 11000110101101\\ 00110110010111\\ 00011101101101\\ 01011010101001 \end{pmatrix}
B10=(1111111100000011110000111100110011001100111100001100111100111100000111001100111100110000111111110010101010101010)B_{10}=\begin{pmatrix} 11111111000000\\ 11110000111100\\ 11001100110011\\ 11000011001111\\ 00111100000111\\ 00110011110011\\ 00001111111100\\ 10101010101010 \end{pmatrix}
B11=(1111111100000011110000011110110011100110011010100101011101100101101101001110101010110101001101001100011101011100)B_{11}=\begin{pmatrix} 11111111000000\\ 11110000011110\\ 11001110011001\\ 10101001010111\\ 01100101101101\\ 00111010101011\\ 01010011010011\\ 00011101011100 \end{pmatrix}
B12=(1111111100000011111000011100110000111010101010010010111101010010101111000111011110010011001101001100101110001101)B_{12}=\begin{pmatrix} 11111111000000\\ 11111000011100\\ 11000011101010\\ 10100100101111\\ 01010010101111\\ 00011101111001\\ 00110011010011\\ 00101110001101 \end{pmatrix}
B13=(1111111100000011111000011110110001100111011010010110110101010011101011000101010101010010111010010100001110111010)B_{13}=\begin{pmatrix} 11111111000000\\ 11111000011110\\ 11000110011101\\ 10100101101101\\ 01010011101011\\ 00010101010101\\ 00101110100101\\ 00001110111010 \end{pmatrix}
B14=(1111111100000011111000011110110001100111000010111001011100101101110101100101001000111000101011001100011011001101)B_{14}=\begin{pmatrix} 11111111000000\\ 11111000011110\\ 11000110011100\\ 00101110010111\\ 00101101110101\\ 10010100100011\\ 10001010110011\\ 00011011001101 \end{pmatrix}
B15=(1111111100000011111000011110110000111011000011011001011100101101110101100101001000111000101011001100011011001101)B_{15}=\begin{pmatrix} 11111111000000\\ 11111000011110\\ 11000011101100\\ 00110110010111\\ 00101101110101\\ 10010100100011\\ 10001010110011\\ 00011011001101 \end{pmatrix}
B16=(1111111100000011111000001110110001111001010011010011110100001011111110101000101010111001000110011101010010110111)B_{16}=\begin{pmatrix} 11111111000000\\ 11111000001110\\ 11000111100101\\ 00110100111101\\ 00001011111110\\ 10100010101011\\ 10010001100111\\ 01010010110111 \end{pmatrix}
B17=(1111111100000011111100001110110000111111100011001100110100101010101011001001011001110001101001011100010101101101)B_{17}=\begin{pmatrix} 11111111000000\\ 11111100001110\\ 11000011111110\\ 00110011001101\\ 00101010101011\\ 00100101100111\\ 00011010010111\\ 00010101101101 \end{pmatrix}

Email address: [email protected]

Email address: [email protected]

Email address: [email protected]

Email address: [email protected]

References

  1. [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. [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. [3]OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, entry A006625, https://oeis.org/A006625, accessed November 9, 2026.
  4. [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

Paper details

vlnc:W_ya5b3zxs
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Mathematics

OpenAI Codex

View statement
Looking for related papers…
Contents