http://openproblemgarden.org/op/turan_number_of_a_finite_family Comments for "Turán number of a finite family." en http://openproblemgarden.org/op/turan_number_of_a_finite_family <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/erdos">Erdos</a>; <a href="/category/simonovits_miklos">Simonovits</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>Given a finite family <img class="teximage" src="/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png" alt="$ {\cal F} $" /> of graphs and an integer <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />, the Turán number <img class="teximage" src="/files/tex/5550e4fdfc798709238dde5cb8429b983762320c.png" alt="$ ex(n,{\cal F}) $" /> of <img class="teximage" src="/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png" alt="$ {\cal F} $" /> is the largest integer <img class="teximage" src="/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png" alt="$ m $" /> such that there exists a graph on <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> vertices with <img class="teximage" src="/files/tex/ddaab6dc091926fb1da549195000491cefae85c1.png" alt="$ m $" /> edges which contains no member of <img class="teximage" src="/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png" alt="$ {\cal F} $" /> as a subgraph.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For every finite family <img class="teximage" src="/files/tex/f3941009edea56b027602b3a3e226da998b78e0a.png" alt="$ {\cal F} $" /> of graphs there exists an <img class="teximage" src="/files/tex/1b6109e0bcc06d36efed4d6b15e1ff4e529f533c.png" alt="$ F\in {\cal F} $" /> such that <img class="teximage" src="/files/tex/05fdebcd6442863bb0866ecaf1c43a1a9eada77c.png" alt="$ ex(n, F ) = O(ex(n, {\cal F})) $" /> .</p> </div> </tr></td> </table> </td> </tr> </table> Erdos, Paul Simonovits, Miklos Graph Theory http://openproblemgarden.org/op/turan_number_of_a_finite_family#comment Tue, 05 Mar 2013 02:39:20 +0100 fhavet 46706 at http://openproblemgarden.org