Sign up ×

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?

share|cite|improve this question
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

3 Answers 3

up vote 8 down vote accepted

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.

share|cite|improve this answer

To add to Konrad's answer:

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.

share|cite|improve this answer

The wikipedia article says that For generalized bipartite graphs H the Erdos-Stone theorem yields ex(n,H) = o(n^2) "and for general bipartite graphs little more is known" see

so as far as I can see you are right that this problem is still open.

share|cite|improve this answer
The Wikipedia article doesn't help much. I know that "little more is known." I want to know what little is known today. :-) – Rune Nov 10 '09 at 13:59

Your Answer


