Erdős–Stone theorem type edge density estimates for bipartite graphs? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T20:23:32Z http://mathoverflow.net/feeds/question/4810 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/4810/erdsstone-theorem-type-edge-density-estimates-for-bipartite-graphs Erdős–Stone theorem type edge density estimates for bipartite graphs? Rune 2009-11-10T04:07:33Z 2009-11-10T22:10:17Z <p>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.</p> <p>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.</p> <p>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:</p> <p>"if $|E| \geq 100k|V|^{1+1/k}$ then G contains a $C_{2l}$ for every $l$ in $[k, n^{1/k}]$."</p> <p>So can someone point me to the best known results now for bipartite cyclic graphs?</p> http://mathoverflow.net/questions/4810/erdsstone-theorem-type-edge-density-estimates-for-bipartite-graphs/4820#4820 Answer by Kristal Cantwell for Erdős–Stone theorem type edge density estimates for bipartite graphs? Kristal Cantwell 2009-11-10T05:50:48Z 2009-11-10T05:50:48Z <p>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</p> <p><a href="http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone%5Ftheorem" rel="nofollow">http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Stone_theorem</a></p> <p>so as far as I can see you are right that this problem is still open.</p> http://mathoverflow.net/questions/4810/erdsstone-theorem-type-edge-density-estimates-for-bipartite-graphs/4923#4923 Answer by Konrad Swanepoel for Erdős–Stone theorem type edge density estimates for bipartite graphs? Konrad Swanepoel 2009-11-10T20:53:49Z 2009-11-10T20:53:49Z <p>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 <em>complete</em> bipartite graphs $K_{m,n}$.</p> <p>Erdös, Rényi, Sós (1954) showed that $$ex(n,K_{2,2}) \sim \frac{1}{2}n^{3/2}.$$</p> <p>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}}.$$</p> <p>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}}.$$</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/4810/erdsstone-theorem-type-edge-density-estimates-for-bipartite-graphs/4933#4933 Answer by Boris Bukh for Erdős–Stone theorem type edge density estimates for bipartite graphs? Boris Bukh 2009-11-10T22:10:17Z 2009-11-10T22:10:17Z <p>To add to Konrad's answer:</p> <p>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 <a href="http://www.ams.org/mathscinet-getitem?mr=1284775" rel="nofollow">Lazebnik and Woldar</a> 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 <a href="http://www.math.ucla.edu/~bsudakov/dependent-random-choice.pdf" rel="nofollow">survey on dependent random choice</a> by Fox and Sudakov.</p>