Threshold functions for the bipartite Turán property (Q1378511)

Summary: Let \(G_2(n)\) denote a bipartite graph with \(n\) vertices in each color class, and let \(z(n,t)\) be the bipartite Turán number, representing the maximum possible number of edges in \(G_2(n)\) if it does not contain a copy of the complete bipartite subgraph \(K(t,t)\). It is then clear that \(\zeta(n,t)=n^2-z(n,t)\) denotes the minimum number of zeros in an \(n\times n\) zero-one matrix that does not contain a \(t\times t\) submatrix consisting of all ones. We are interested in the behaviour of \(z(n,t)\) when both \(t\) and \(n\) go to infinity. The case \(2\leq t\ll n^{1/5}\) has been treated elsewhere; here we use a different method to consider the overlapping case \(\log n\ll t\ll n^{1/3}\). Fill an \(n \times n\) matrix randomly with \(z\) ones and \(\zeta=n^2-z\) zeros. Then, we prove that the asymptotic probability that there are no \(t \times t\) submatrices with all ones is zero or one, according as \(z\geq(t/ne)^{2/t}\exp\{a_n/t^2\}\) or \(z\leq(t/ne)^{2/t}\exp\{(\log t-b_n)/t^2\}\), where \(a_n\) tends to infinity at a specified rate, and \(b_n\to\infty\) is arbitrary. The proof employs the extended Janson exponential inequalities.