Finite-convergence conjecture for the copositive stability-number hierarchy

From papers

Let GG be a graph, let MGM_G be its graph matrix, let FG(x)=(x2)TMGx2F_G(x)=(x^{\circ2})^TM_Gx^{\circ2}, and let

Kn(r)={MSn:(i=1nxi2)r(x2)TMx2Σ}.\mathcal K_n^{(r)}=\{M\in\mathcal S^n:(\sum_{i=1}^n x_i^2)^r(x^{\circ2})^TMx^{\circ2}\in\Sigma\}.

Define ϑ(r)(G)=min{t:t(AG+I)JKn(r)}\vartheta^{(r)}(G)=\min\{t:t(A_G+I)-J\in\mathcal K_n^{(r)}\}. The finite-convergence conjecture. For every graph GG, there exists rNr\in\mathbb N such that MGKn(r)M_G\in\mathcal K_n^{(r)}, equivalently (i=1nxi2)rFGΣ(\sum_{i=1}^n x_i^2)^rF_G\in\Sigma, equivalently ϑ(r)(G)=α(G)\vartheta^{(r)}(G)=\alpha(G), or equivalently ϑ-rank(G)<\vartheta\text{-rank}(G)<\infty. This weaker conjecture asks only for finite convergence at some order and is explicitly stated to remain open.

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, “Exactness of Parrilo's conic approximations for copositive matrices and associated low order bounds for the stability number of a graph”, arXiv:2109.12876 (2021).

Solutions 0

No solutions have been posted yet.