The Erdős–Stone theorem theory says that the densest graph not containing a graph H (which has chromatic number r) has number of edges equal to $(r-2)/(r-1) {n \choose 2}$ asymptotically.


However, this doesn't say much for bipartite graphs (since r=2). I wanted to know what are the best results known for the densest graphs not containing a particular bipartite graph H. I'm guessing this problem is still open and hasn't been completely resolved.


This problem is easy if H is a forest, since every graph with $|E| > k|V|$ contains every forest on k vertices as a subgraph. For even cycles, I know there is a result of Bondy and Simonovits which says:


"if $|E| \geq 100k|V|^{1+1/k}$ then G contains a $C\_{2l}$ for every $l$ in $[k, n^{1/k}]$."


So can someone point me to the best known results now for bipartite cyclic graphs?



Erdős–Stone theorem type edge density estimates for bipartite graphs?
Let $ex(n, H)$ denote the maximum number of edges of a graph on $n$ vertices not containing a copy of $H$. The exact bounds are difficult already if you forbid *complete* bipartite graphs $K\_{m,n}$.


Erdös, Rényi, Sós (1954) showed that $$ex(n,K\_{2,2}) \sim \frac{1}{2}n^{3/2}.$$


According to the classical Kövári-Sós-Turán Theorem (1954), $$ex(n,K\_{t,s}) \leq c\_{s,t} n^{2-\frac{1}{t}}$$ for $s\geq t\geq 2$,
while a random construction gives the lower bound $$ex(n,K\_{t,s})\geq cn^{2-\frac{s+t-2}{st-1}}.$$


Brown (1966) showed Kövári-Sós-Turán is tight for $s=t=3$: $$ex(n,K\_{3,3}) \geq cn^{2-\frac{1}{3}},$$ and Füredi (1996) proved that the constant in Brown's construction is optimal, giving $$ex(n,K\_{3,3}) \sim \frac{1}{2}n^{2-\frac{1}{3}}.$$


Alon, Kollár, Rónyai, Szabó (1995, 1999) showed that for each $t\geq 2$ there exists $c\_t>0$ such that for all $s\geq(t-1)!+1$,
$$ex(n,K\_{t,s}) \geq c\_tn^{2-\frac{1}{t}},$$ thus matching Kövári-Sós-Turán asymptotically.


I'm not sure if a construction matching Kövári-Sós-Turán has been found for the case $K\_{4,4}$. There must also be more known than what is mentioned here. But as you can see, somewhat more than a just a little more is known, although the gaps in our knowledge are still huge here.


