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

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

2009-11-10T04:07:33Z

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?

Answer by Kristal Cantwell for Erdős–Stone theorem type edge density estimates for bipartite graphs?

2009-11-10T05:50:48Z

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

http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem

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

Answer by Konrad Swanepoel for Erdős–Stone theorem type edge density estimates for bipartite graphs?

2009-11-10T20:53:49Z

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.

Answer by Boris Bukh for Erdős–Stone theorem type edge density estimates for bipartite graphs?

2009-11-10T22:10:17Z

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.