http://openproblemgarden.org/op/vertex_cover_integrality_gap Comments for "Vertex Cover Integrality Gap" en http://openproblemgarden.org/op/vertex_cover_integrality_gap <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/atserias_albert">Atserias</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/logic">Logic</a> » <a href="/category/finite_model_theory">Finite Model Theory</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/5100aa83a735c347ff2a904d4fc00eb99293313b.png" alt="$ \varepsilon &gt; 0 $" /> there is <img class="teximage" src="/files/tex/7f1f08ff9938cb9a6981c1f1e563b40b7c34396a.png" alt="$ \delta &gt; 0 $" /> such that, for every large <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />, there are <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" />-vertex graphs <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> and <img class="teximage" src="/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png" alt="$ H $" /> such that <img class="teximage" src="/files/tex/bde71bc721de861f937e9c0d2e1c9c1d1ee7a71b.png" alt="$ G \equiv_{\delta n}^{\mathrm{C}} H $" /> and <img class="teximage" src="/files/tex/1e471324d6f347bdb5fb4e462749473752a10170.png" alt="$ \mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H) $" />. </div> </tr></td> </table> </td> </tr> </table> Atserias, Albert counting quantifiers FMT12-LesHouches Logic Finite Model Theory http://openproblemgarden.org/op/vertex_cover_integrality_gap#comment Tue, 02 Oct 2012 14:24:35 +0200 dberwanger 38188 at http://openproblemgarden.org