The Zarankiewicz problem via Chow forms ∗

The well-known Zarankiewicz problem [Za] is to determine the least positive integer Z(m, n, r, s) such that each m × n 0-1 matrix containing Z(m, n, r, s) ones has an r × s submatrix consisting entirely of ones. In graph-theoretic language, this is equivalent to finding the least positive integer Z(m, n, r, s) such that each bipartite graph on m black vertices and n white vertices with Z(m, n, r, s) edges has a complete bipartite subgraph on r black vertices and s white vertices. A complete solution of the Zarankiewicz problem has not been given. While exact values of Z(m, n, r, s) are known for certain infinite subsets of m, n, r and s, only asymptotic bounds are known in the general case; for example, see Čulík [Č], Füredi [F], Guy [G], Hartmann, Mycielski and Ryll-Nardzewski [HMR], Hyltén-Cavallius [HC], Irving [I], Kövári, Sós and Turán [KST], Mörs [M], Reiman [Re], Roman [Ro], Znám [Zn]. Even the case r = s = 2 has not been answered in general. Here we quote some known facts about this case: Hartmann, Mycielski and Ryll-Nardzewski [HMR] proved the asymptotic bounds c1n 4/3 < Z(n, n, 2, 2) < c2n 3/2 for some constants c1 ∼ = 3 4 and c2 ∼ = 2. Kövári, Sós and Turán [KST] proved that Z(n, n, 2, 2) ≤ 2n + n 3/2, lim n→ ∞ n −3/2 Z(m, n, 2, 2) = 1. Moreover, when p is a prime integer, [KST] proved that Z(p2 + p, p2, 2, 2) = p2 (p + 1) + 1. Hyltén-Cavallius [HC] proved that Z(m, n, 2, 2) ≤