On the half-half case of the Zarankiewicz problem
Let \(f(m,n)\) denote the minimum number of zero entries in a \(2m \times 2n\) \((0,1)\)-matrix \(A\) that contains no \(m \times n\) submatrix of ones. For this special case of the Zarankiewicz problem, \textit{J. R. Griggs} and \textit{J. Ouyang} [Eur. J. Comb. 18, No. 7, 751-761 (1997; Zbl 0887.05037)] showed that \(2n+m+1 \leq f(m,n) \leq 2n+2m-\text{ gcd}(m,n)+1\) whenever \(m \leq n.\) In this paper, the authors prove that \(\lim_{m \to \infty} (f(m,m+1)/m) = 3.\) They do so by determining the actual value of \(f(m,km+1)\) for arbitrary \(k\) und \(m.\) Moreover, the values of \(f(m,n)\) are given explicitly for \(m \leq 7\) and \(n \leq 20.\)
lower and upper bounds for the number of zero entries in a matrix
scientific article; zbMATH DE number 1746279