http://openproblemgarden.org/op/nearly_spanning_regular_subgraphs Comments for "Nearly spanning regular subgraphs" en http://openproblemgarden.org/op/nearly_spanning_regular_subgraphs <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/alon">Alon</a>; <a href="/category/mubayi_dhruv">Mubayi</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/graph_theory">Graph Theory</a> » <a href="/category/basic_graph_theory">Basic G.T.</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For every <img class="teximage" src="/files/tex/9347bd4719a266c10e0c73946c70533f2b4266a2.png" alt="$ \epsilon &gt; 0 $" /> and every positive integer <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />, there exists <img class="teximage" src="/files/tex/db5402d669245c54e19a91ddcff575973e28c243.png" alt="$ r_0 = r_0(\epsilon,k) $" /> so that every simple <img class="teximage" src="/files/tex/535dee6c3b72bcc4d571239ed00be162ee1e6fbe.png" alt="$ r $" />-regular graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> with <img class="teximage" src="/files/tex/a0a00ac7aea9a9f3036fbe5546201edb3c16e8fa.png" alt="$ r \ge r_0 $" /> has a <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-regular subgraph <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> with <img class="teximage" src="/files/tex/d1aa8f81bdb2c1c340902bd11eadc4173d757e30.png" alt="$ |V(H)| \ge (1- \epsilon) |V(G)| $" />. </div> </tr></td> </table> </td> </tr> </table> Alon, Noga Mubayi, Dhruv regular subgraph Graph Theory Basic Graph Theory http://openproblemgarden.org/op/nearly_spanning_regular_subgraphs#comment Thu, 22 May 2008 11:15:35 +0200 mdevos 801 at http://openproblemgarden.org