The problem of Zarankiewicz is a central problem in extremal graph theory. It asks for the maximum number of edges \(\operatorname{ex}(n,K_{k,k})\)  in a bipartite graph on \(n\)  vertices, where each side of the bipartition contains \(n/2\)  vertices and which does not contain the complete bipartite graph \(K_{k,k}\)  as a subgraph. In 1954, Kővári, Sós, and Turán [1]} proved that this number of edges is at most \(c_{k}n^{2 - \frac{1}{k}}\) , for some positive constant \(c_{k}\)  which depends only on \(k\) . Classical constructions of Reiman and Brown show that this bound is tight for \(k=2,3\)  (see [2]}).
However, the Zarankiewicz problem for \(k \ge 4\)  remains one of the most challenging unsolved
problems in combinatorics. The best lower bound for \(k=4\)  simply comes from the Brown construction [3]}, namely
\(\operatorname{ex}(n,K_{4,4}) \ge \operatorname{ex}(n,K_{3,3}) = \Omega \left(n^{5/3}\right).\) 
