TC-01: EUROPT Fellow 2021 Lecture
Room: Fermat
Chair(s): Miguel F. Anjos, Giancarlo Bigi

Copositivity, sums of squares of polynomials and graphs
Monique Laurent
We investigate a hierarchy of semidefinite bounds for the stability number alpha(G) of a graph G, that are based on its continuous copositive programming formulation: alpha(G) = min {t: t(I+A_G)-J \in COP(n)}. Here, n is the number of vertices, A_G is the adjacency matrix, J is the all-ones matrix, and COP(n) is the copositive cone, which consists of the symmetric matrices M for which the polynomial p_M = sum_{i,j=1}^n M_{ij}x_i^2 x_j^2 is nonnegative over R^n. By replacing the copositive cone COP(n) by its inner conic approximations K^r, consisting of the matrices M for which the polynomial |x|^{2r}p_M is a sum of squares, we obtain the bounds theta^{r}(G), known to converge asymptotically to alpha(G). De Klerk and Pasechnik (2002) conjectured that finite convergence takes place at order r=alpha(G)-1. However, even the weaker conjecture asking whether equality holds for some r is still open. We discuss old and new results around these questions and the cones K^r, which display a nice interplay between graph structure, polynomial optimization and real algebraic geometry. Based on joint work with Luis Felipe Vargas (CWI, Amsterdam).