New results on the Zarankiewicz problem (Q2643330)

The Zarankiewicz problem asks how many edges can be added to a bipartite graph \(K(m,n)\) while avoiding a complete bipartite subgraph \(K(s,t)\). The maximum number of edges is denoted by \(z(m,n;s,t)\). In the paper are found exact values of the function \(z(m,n;s,t)\) for special values of parameters and also corresponding extremal graphs are characterized. First, it is proved that \(z(m,n;s,t) = mn-(m+n-s-t+1)\) if \(\max \{m,n\} \leq s+t-1\). The next results deal with the case \(s=t\). It is proved that if \(2\leq t \leq m \leq 2t\) then \(z(m, 2t; t, t)=m\cdot 2t - (2m-t +1)\), and if \(2\leq t \leq m \leq n\) and \(2t < n \leq 3t -1\) then \(z(m, n; t, t)=m\cdot n - (2m + n-3t +1)\).