Contributions to the problem of Zarankiewicz

Let G2(n) denote a bipartite graph with n vertices in each color class, and let z(n;t) be the bipartite Turan number, representing the maximum possible number of edges in G2(n) ifitisnotto contain a copy of the complete bipartite subgraph K(t;t). It is then clear that (n;t)=n 2 −z(n;t) denotes the smallest possible number of zeros in an n×n zero–one matrix that does not contain a t×t submatrix consisting of all ones. We investigate the behaviour of z(n;t) when n goes to in nity (and perhaps t →∞as well). The case t=o(n 1=3);t�logn has been considered by Godbole et al. [Electron. J. Combin. 4 (1997) 14pp], and we focus here on the overlapping case 26t�n 1=5. Fill an n×n matrix randomly with z ones and n 2 −z = zeros. Then, we prove that if t →∞, the asymptotic probability that there are no t×t submatrices with all ones is one or zero, according as z = n 2−2=t t 2=