![](/files/happy5.png)
Atserias, Albert
Vertex Cover Integrality Gap ★★
Author(s): Atserias
Conjecture For every
there is
such that, for every large
, there are
-vertex graphs
and
such that
and
.
![$ \varepsilon > 0 $](/files/tex/5100aa83a735c347ff2a904d4fc00eb99293313b.png)
![$ \delta > 0 $](/files/tex/7f1f08ff9938cb9a6981c1f1e563b40b7c34396a.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ n $](/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ G \equiv_{\delta n}^{\mathrm{C}} H $](/files/tex/bde71bc721de861f937e9c0d2e1c9c1d1ee7a71b.png)
![$ \mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H) $](/files/tex/1e471324d6f347bdb5fb4e462749473752a10170.png)
Keywords: counting quantifiers; FMT12-LesHouches
![Syndicate content Syndicate content](/misc/feed.png)
Author(s): Atserias
Keywords: counting quantifiers; FMT12-LesHouches