On the Lovász Theta function for independent sets in sparse graphs

We consider the maximum independent set problem on sparse graphs with maximum degree d. We show that the Lovász ϑ-function based semidefinite program (SDP) has an integrality gap of O(d/log³/² d), improving on the previous best result of O(d/log d). This improvement is based on a new Ramsey-theoretic bound on the independence number of Kr-free graphs for large values of r. We also show that for stronger SDPs, namely, those obtained using polylog(d) levels of the SA⁺ semidefinite hierarchy, the integrality gap reduces to O(d/log² d). This matches the best unique-games-based hardness result up to lower-order poly(log log d) factors. Finally, we give an algorithmic version of this SA⁺-based integrality gap result, albeit using d levels of SA⁺, via a coloring algorithm of Johansson.