On the half-half case of the Zarankiewicz problem
type: Item
instance of: scholarly article
title: On the half-half case of the Zarankiewicz problem
zbMATH Open document ID: 0990.05019
DOI: 10.1016/S0012-365X(01)00237-0
author: J. Griggs
author: Chih-Chang Ho
published in: Discrete Mathematics
publication date: 2002-05-28T00:00:00Z
review text: 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.\)
Mathematics Subject Classification ID: 05B20
Mathematics Subject Classification ID: 15B36
zbMATH DE Number: 1746279
zbMATH Keywords: \((0,1)\)-matrices
zbMATH Keywords: lower and upper bounds for the number of zero entries in a matrix
zbMATH Keywords: the Zarankiewicz problem
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00237-0
OpenAlex ID: W2065088888
Wikidata QID: Q127977050
description: scientific article; zbMATH DE number 1746279