De Klerk–Pasechnik conjecture on the copositive hierarchy for the stability number

From papers

Let GG be a non-empty graph with vertex set V=[n]V=[n], adjacency matrix AGA_G, stability number 4α(G)44\alpha(G)4, and associated matrix MG=α(G)(AG+I)JM_G=\alpha(G)(A_G+I)-J. Let fGf_G be the quartic form associated with MGM_G, and let Kn(r)\mathcal{K}_n^{(r)} denote the rr-th sum-of-squares cone in the hierarchy. The hierarchy is defined by

θ(r)(G):=min{tt(AG+I)JKn(r)}.\theta^{(r)}(G):=\min\left\{t\mid t(A_G+I)-J\in \mathcal{K}_n^{(r)}\right\}.

De Klerk–Pasechnik conjecture. For every non-empty graph GG,

(i=1nxi2)α(G)1fGΣ.\left(\sum_{i=1}^n x_i^2\right)^{\alpha(G)-1}f_G\in \Sigma.

Equivalently, MGKn(α(G)1)M_G\in\mathcal{K}_n^{(\alpha(G)-1)}, or θ(α(G)1)(G)=α(G)\theta^{(\alpha(G)-1)}(G)=\alpha(G). Reznick certification implies that the hierarchy converges to α(G)\alpha(G) as rr\to\infty, but it remains open whether α(G)1\alpha(G)-1 steps always suffice.

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

Markus Schweighofer and Luis Felipe Vargas, “Sum-of-squares certificates for copositivity via test states”, arXiv:2310.12853 (2023).

Additional references

2 papers in this index state this conjecture (2021–2023). The statement above is taken from the most recent of them; the others are arXiv:2103.01574.

Solutions 0

No solutions have been posted yet.