A contribution to the Zarankiewicz problem

Given positive integers m,n,s,t, let z(m,n,s,t)z(m,n,s,t) be the maximum number of ones in a (0,1)(0,1) matrix of size m×nm×n that does not contain an all ones submatrix of size s×ts×t. We show that if s⩾2s⩾2 and t⩾2,t⩾2, then for every k=0,…,s-2,k=0,…,s-2,z(m,n,s,t)⩽(s-k-1)1/tnm1-1/t+kn+(t-1)m1+k/t.z(m,n,s,t)⩽(s-k-1)1/tnm1-1/t+kn+(t-1)m1+k/t.This generic bound implies the known bounds of Kövari, Sós and Turán, and of Füredi. As a consequence, we also obtain the following results:Let GG be a graph of nn vertices and e(G)e(G) edges, and let μμ be the spectral radius of its adjacency matrix. If GG does not contain a complete bipartite subgraph Ks,t,Ks,t, then the following bounds holdμ⩽(s-t+1)1/tn1-1/t+(t-1)n1-2/t+t-2,μ⩽(s-t+1)1/tn1-1/t+(t-1)n1-2/t+t-2,ande(G)<12(s-t+1)1/tn2-1/t+12(t-1)n2-2/t+12(t-2)n.