The K_i Cover Problem with Semidefinite Programming

The K_i cover problem is a generalization of the stable set problem to avoid
larger cliques. Motivated by the Lovasz theta relaxation of the stable set
polytope, we apply the related theta body relaxation of an algebraic variety
to the K_i cover polytope. We show that for certain families of facets, the
approximation is exact. For the triangle free problem (i=3), we prove a slow
convergence result, and a bound on the integrality gap.

This is joint work with Joao Gouveia.