This lecture revolves around a central open question, relevant to the computation of the stability number \(\alpha (G)\) of a graph \(G=([n],E)\) in discrete optimization, to the cone \(\text{COP}_n\) of copositive matrices, and to the cone \(\Sigma \) of sums of squares of polynomials. Consider the matrix \(M_G=\alpha (G)(I+A_G)-J\), where \(A_G\) is the adjacency matrix of \(G\) and \(J\) is the all-ones matrix, and the associated polynomial \(p_G=(x^{\circ 2})^T M_G x^{\circ 2}\) in the squared variables \(x^{\circ 2}=(x_1^2,\ldots ,x_n^2)\). As is well-known the matrix \(M_G\) is copositive and thus the polynomial \(p_G\) is globally nonnegative on \(\mathbb R^n\). The question is whether there exists a positivity certificate in the form \((\sum _{i=1}^nx_i^2)^r p_G \in \Sigma \) for some integer \(r\in \mathbb N\). De Klerk and Pasechnik (2002) conjecture that the answer is positive, in fact already for \(r=\alpha (G)-1\).

Following Parrilo (2000) let \(\mathcal K^{(r)}_n\) consist of all symmetric matrices \(M\) for which the associated polynomial \((\sum _{i=1}^nx_i^2)^r (x^{\circ 2})^T M x^{\circ 2}\) is a sum of squares. These cones form an inner approximation hierarchy of \(\text{COP}_n\) and they are known to cover its full interior: \[ \text{int}(\text{COP}_n) \subseteq \bigcup _{r\ge 0} \mathcal K^{(r)}_n\subseteq \text{COP}_n. \] The above open question thus asks whether any graph matrix \(M_G\) belongs to some cone \(\mathcal K^{(r)}_n\), a nontrivial question since any \(M_G\) lies on the boundary of \(\text{COP}_n\). As one of our new results we show that the answer is positive for the class of graphs that do not have any \(\alpha \)-critical edge, which corresponds to the case when \(p_G\) has finitely many zeros on the unit sphere.

It is known that any \(4\times 4\) copositive matrix belongs to \(\mathcal K^{(0)}_4\), the dual of the cone of doubly-nonnegative matrices. We show that the union of the cones \(\mathcal K^{(r)} _n\) does not cover \(\text{COP}_n\) if \(n\ge 6\). However it remains open what is the situation for \(n=5\). What we can show is that the Horn matrix \(M_{C_5}\) plays a crucial role: it remains only to settle whether any positive diagonal scaling of the Horn matrix belongs to some cone \(\mathcal K^{(r)}_5\).

We will discuss old and new results around the above questions and related ones, which display a nice interplay between graph structure, optimization, copositive matrices, and real algebraic geometry.

This is based on joint works [1, 2, 3] with Luis Felipe Vargas (CWI, Amsterdam).

References