Lower bound for Turán number for \(K_{4,4}\)

Please see The Turan number of \( K_{r, r}\) for additional information about this problem and its background. This is a special case of the Zarankiewicz problem[1]. The Zarankiewicz problem in general is the following:

Problem

What is the largest integer \(m\) such that there is a graph \(G\) on \(n\) vertices with \(m\) edges such that \(K_{r, r}\) is not a subgraph of \(G\)? We denote this integer \(m\) by \(t(n, K_{r, r})\)?

For \( t(n,K_{4,4})\), it is only known that \( t(n,K_{4,4}) \geq t(n,K_{3,3}) \geq c n^{5/3}\).

Problem

Is it true that\[ \frac{t(n,K_{4,4})}{n^{5/3}} \rightarrow \infty ?\]

The best known lower bound for \( t(n,K_{r,r})\) is of the order \( O( n^{2-2/(r+1)})\), which can be proved by the following deletion method[2] from probabilistic combinatorics.

Suppose that we consider a random subgraph \( G\) in which each edge is chosen with probability \( \rho\). The expected number of \( K_{r, r}\) in \( G\) is \( \rho^{r^2} \binom{n}{2r} \binom{2r}{r}\). For each copy of \( K_{r, r}\), we delete an edge. Then the remaining graph contains no \( K_{r, r}\) and has at least

\begin{equation*} \rho \binom{n}{2} - \rho^{r^2} \binom{n}{2r} \binom{2r}{r} > \frac 1 2 \rho \binom{n}{2} \end{equation*}

edges if \( \rho \leq n^{-2/(r+1)}\). This implies that \( t(n,K_{r,r}) \geq c n^{2-2/(r+1)}\).


Bibliography
1 K. Zarankiewicz, Problem P 101, Colloq. Math. 2 (1951), 116-131.

2 P. Erdös and J. H. Spencer, Probabilistic Methods in Combinatorics, Probability and Mathematical Statistics, Vol. 17, Academic Press, New York, 1974.