Membership conjecture for graph matrices in the copositive hierarchy

From papers

Let GG be a graph with stability number α(G)\alpha(G), and let AGA_G, II, and JJ denote its adjacency, identity, and all-ones matrices, respectively. Define

MG=α(G)(AG+I)J.M_G=\alpha(G)(A_G+I)-J.

By the Motzkin–Straus theorem, MGM_G is copositive. Graph-matrix hierarchy membership conjecture. For every graph GG,

MGr0Kn(r).M_G\in\bigcup_{r\geq 0}{\mathcal K}_n^{(r)}.

This weaker conjecture asks whether every graph matrix eventually appears in the sum-of-squares copositive hierarchy. The source states that it remains open, and notes that even this eventual membership is not known in general.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Monique Laurent and Luis Felipe Vargas, “On the Exactness of Sum-of-Squares Approximations for the Cone of 55 Copositive Matrices”, arXiv:2205.05381 (2022).

Solutions 0

No solutions have been posted yet.