Ratio bound (Lovász number) versus inertia bound

Abstract

Matthew Kwan and Yuval Wigderson showed that for an infinite family of graphs, the Lovász number gives an upper bound of $O(n^{3/4})$ for the size of an independent set (where $n$ is the number of vertices), while the weighted inertia bound cannot do better than $\Omega (n)$. Here we point out that there is an infinite family of graphs for which the Lovász number is $\Omega (n^{3/4})$, while the unweighted inertia bound is $O(n^{1/2})$.

arXiv comment4 pages. I do not plan to publish this note/example