Ratio bound (Lovász number) versus inertia bound

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})$.

By Ferdinand Ihringer
Published 2023-12-15 04:12:27