We investigate a hierarchy of semidefinite bounds for the stability number $\alpha(G)$ of a graph $G$, based on its continuous copositive formulation:

where $n=|V_G|$, $A_G$ is the adjacency matrix of $G$ and $J$ is the all-ones matrix. Here, $COP_n$ is the copositive cone, consisting of the symmetric $n\times n$ matrices $M$ for which the polynomial $p_M=\sum_{i,j=1}^n M_{ij}x_i^2x_j^2$ is nonnegative over $R^n$. By replacing the copositive cone $COP_n$ by its inner approximation, consisting of the matrices $M$ for which the polynomial $(\sum_i x_i^2)^rp_M$ is a sum of squares, we obtain the bounds $\vartheta^{(r)}(G)$, known to converge $asymptotically$ to $\alpha(G)$. De Klerk and Pasechnik (2002) conjectured that $\vartheta^{(r)}(G)=\alpha(G)$ for any $r\ge \alpha(G)-1$, but even the weaker conjecture asking whether equality holds for $some$ $r$ is still open. We discuss old and new results around these questions, which display a nice interplay between graph structure, polynomial optimization and real algebraic geometry.

Joint work with Luis Felipe Vargas (CWI, Amsterdam).