Home » Author index

Atserias, Albert


Logic » Finite Model Theory

Vertex Cover Integrality Gap ★★

Author(s): Atserias

Conjecture   For every $ \varepsilon > 0 $ there is $ \delta > 0 $ such that, for every large $ n $, there are $ n $-vertex graphs $ G $ and $ H $ such that $ G \equiv_{\delta n}^{\mathrm{C}} H $ and $ \mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H) $.

Keywords: counting quantifiers; FMT12-LesHouches

Posted by dberwanger
updated October 2nd, 2012
add new comment
Syndicate content