Question

In Chung and Graham's "Erdős on Graphs: His legacy of unsolved problems," they discuss several open problems concerning Turán numbers for bipartite graphs.

There is a construction which gives graphs on $n$ vertices with $C n^{5/3}$ edges, with no $K_{3,3}$ subgraphs, and at the time of the writing of this book there was no better lower bounds on the Turán number of $K_{4,4}$.

Is it known whether $$\lim_{n\to \infty} \frac{ \mbox{ex}\left(n ; K_{4,4}\right) }{n^{5/3}} = \infty ? $$

(Here $\mbox{ex}(n ; H)$ is the maximum number of edges for an $n$-vertex graph with no subgraphs isomorphic to $H$.)

Answer 1

Here is a near answer. In Turan Numbers of Bipartite Graphs and Related Ramsey-Type Questions, Alon, Krivelevich, and Sudakov prove that $ex(n; K_{s,t}) \leq O(n^{2-1/s})$. They note that this bound is tight for all values of $s \geq 2$.

That is, by previous results, if $t > (s-1)!$, then the Turan number of $K_{s,t}$ is in fact $\Theta (n^{2-1/s})$. Therefore, if we replace $K_{4,4}$ by $K_{4,7}$, then the answer to your question is yes.