Membership conjecture for graph matrices in the copositive hierarchy
Let be a graph with stability number , and let , , and denote its adjacency, identity, and all-ones matrices, respectively. Define
By the Motzkin–Straus theorem, is copositive. Graph-matrix hierarchy membership conjecture. For every graph ,
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.
References
- 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).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.