New results on the Zarankiewicz problem

Let (X,Y)(X,Y) denote a bipartite graph with classes X and Y   such that |X|=m|X|=m and |Y|=n|Y|=n. A complete bipartite subgraph with s vertices in X and t vertices in Y   is denoted by K(s,t)K(s,t). The Zarankiewicz problem consists in finding the maximum number of edges, denoted by z(m,n;s,t)z(m,n;s,t), of a bipartite graph (X,Y)(X,Y) with |X|=m|X|=m and |Y|=n|Y|=n without a complete bipartite K(s,t)K(s,t) as a subgraph. First, we prove that z(m,n;s,t)=mn-(m+n-s-t+1)z(m,n;s,t)=mn-(m+n-s-t+1) if max{m,n}⩽s+t-1max{m,n}⩽s+t-1. Then we characterize the family Z(m,n;s,t)Z(m,n;s,t) of extremal graphs for the values of parameters described above. Finally, we study the s=ts=t case. We give the exact value of z(m,n;t,t)z(m,n;t,t) if 2t⩽n⩽3t-12t⩽n⩽3t-1 and we characterize the extremal graphs if either n=2tn=2t or both 2t