February 12, 2013, 4:00pm
James Pfeiffer, Department of Mathematics, University of Washington
The K_i Cover Problem with Semidefinite Programming
Abstract: 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.