# Erdős–Stone theorem type edge density estimates for bipartite graphs?

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?

-
Do you want birpartite graphs or bipartite cyclic graphs? I would think that bipartite cyclic graphs would be the same as even cycles and the result of Bondy and Simonovits would work. –  Kristal Cantwell Nov 10 '09 at 4:55
Sorry cyclic means containing a cycle as opposed to forests so they are not necessarily cycles. –  Kristal Cantwell Nov 10 '09 at 5:19
Right. Since forests are easy, the only remaining case is bipartite graphs with cycles. Out of which the cycle graphs are probably covered by the result of Bondy/Simonovits. –  Rune Nov 10 '09 at 13:54

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.

-

No construction is known for $K_{4,4}$. Neither there is a construction for $C_{2k}$ for k other than 2,3,5. There is a construction by Lazebnik and Woldar that beats the probabilistic for $C_{2k}$, though. There are some non-trivial upper bounds on bipartite graphs of bounded degree and (more generally) of bounded degeneracy. These upper bounds (and some references) can be found in the survey on dependent random choice by Fox and Sudakov.