Since I started in November, I have been reading some relevant literature on approximations of the Stability Number of a graph via SDP relaxations. Last week, as a part of the Polynomial Optimization Reading Group (at CWI), I presented the talk: Approximations for the Stability Number. Specifically, I presented some results about the de Klerk Pasechnik Hierarchy. Some relevant literature is:

• Semidefinite Approximations for the Stability Number of a Graph via Sum of Squares. M.Laurent, N. Gvozdenovic. SIAM Journal of Optimization, 2006
• Approximating the stability number of a graph via copositive programming. De Klerk, E.Pasechnik. SIAM Journal of Optimization, 2006

I would like to share with you one proof (slighly changed) of a stronger version of the Polya Theorem presented by M. Laurent, E. de Klerk and P. Parrilo in “A PTAS for the minimization of polynomials of fixed degree over the simplex” Theoretical Computer Science: The journal of the EATCS.. 2006 This result allows us to prove some bounds for the de Klerk Pasechnik hierarchy as will be shown in the next post in this blog.