an online database of Zarankiewicz numbers. home; recent; tables; submit; theorems & references

Bound for z(27,27)

The following proof is modelled on DybizbaƄski, Dzido, and Radziszowski's proof that z(17,17) $\le 74$. [DDR13, p. 8] We denote row $i$, column $j$ and their weights as $R_i$, $C_j$, $r_i$ and $c_j$ respectively. We say $R_i$ intersects $C_j$ if $A_{i,j} = 1$, and $R_i$ intersects $R_k$ if $A_{i,j} = A_{k,j} = 1$ for some $j$.

Suppose there is $27{\times}27$ rectangle-free matrix with $w(A) = 148$. Without loss of generality $R_1$ is a row of least weight, so that $r_1 \le \left\lfloor 148/27 \right\rfloor = 5$. Let $A'$ be the $26{\times}27$ matrix formed by deleting $R_1$ from $A$, so that $w(A') \ge 143$. $A'$ has minimum column weight $c' \le \left\lfloor (148-r_1)/27 \right\rfloor = 5$.

As z(26,26) $= 138$, every $r_i + c_j - A_{i,j} \ge 10$, otherwise deleting $R_i$ and $C_j$ would give a $26{\times}26$ matrix of weight greater than $138$ by the inclusion/exclusion principle. It follows that $r_1 + c' \ge 10$, so $r_1 = c' = 5$, and hence $A_{1,j} = 1$ implies $c_j \ge 6$. Without loss of generality $A_{1,1},\ldots,A_{1,5} = 1$, so by the rectangle-free property $C_1,\ldots,C_5$ each intersect only in $R_1$. Therefore either every $c_1,\ldots,c_5 = 6$, or one has weight $7$.

If e.g. $c_1 = 7$ and $c_2,\ldots,c_5 = 6$, then the $22$ remaining columns intersect each of $C_1,\ldots,C_5$ in at most one row, so they each have weight $5$, giving a total weight of $7 + 4 \cdot 6 + 22 \cdot 5 = 141$; a contradiction. So $c_1,\ldots,c_5 = 6$, and there are $1 + 5 \cdot 5 = 26$ rows including $R_1$ which intersect some of $C_1,\ldots,C_5$, leaving without loss of generality only $R_{27}$ intersecting none of them.

Now, each of the $22$ columns $C_j$ with $j \ge 6$ by assumption does not intersect $R_1$, by the rectangle-free property intersects each $C_1,\ldots,C_5$ at most once, and may intersect $R_{27}$, giving $c_j \le 6$. We also have every $c_j \ge 5$, and $\sum_{j=1}^{27} c_j = w(A) = 148$, so there must be $14$ columns of weight $5$ and $13$ columns of weight $6$ (including $C_1,\ldots,C_5$). Therefore at least $8$ other columns intersect $R_{27}$, giving $r_{27} \ge 8$.

However, this is a contradiction, as the same argument on the transpose shows that $5 \le r_i \le 6$ for every $i$. Therefore $z(27,27) \le 147$.

upper bound = 147, submitted by Andrew Kay on April 26th, 2016 (link)