On the half-half case of the Zarankiewicz problem

DOI10.1016/S0012-365X(01)00237-0MaRDI QIDQ1598845zbMATH OpenOpenAlexWikidataFDO

Authors J. Griggs, Chih-Chang Ho

Publication date 28 May 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(01)00237-0

zbMATH Keywords

\((0,1)\)-matriceslower and upper bounds for the number of zero entries in a matrixthe Zarankiewicz problem

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Matrices of integers (15B36)

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.\)

Recommendations

• (0, 1)-matrices with no half-half submatrix of ones
• Some remarks on the Zarankiewicz problem
• New results on the Zarankiewicz problem
• A contribution to the Zarankiewicz problem
• scientific article; zbMATH DE number 1795865

Cited in

(7)

• (0, 1)-matrices with no half-half submatrix of ones
• New results on the Zarankiewicz problem
• Extremal <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>K</mml:mi><mml:mrow><mml:mo stretchy="false">(</mml:mo><mml:mi>s</mml:mi><mml:mo>,</mml:mo><mml:mi>t</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:msub></mml:math>-free bipartite graphs
• scientific article; zbMATH DE number 1795865 (Why is no real title available?)
• Some remarks on the Zarankiewicz problem
• Topological minors in bipartite graphs
• Zarankiewicz numbers near the triple system threshold

This page was built for publication: On the half-half case of the Zarankiewicz problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1598845)