Gvozdenović–Laurent bound for the copositive stability-number hierarchy

Let G=(V,E)G=(V,E) be a graph, let ϑ(r)(G)\vartheta^{(r)}(G) be its order-rr copositive hierarchy bound, and let SS^\perp denote the vertices adjacent to or equal to a stable set SS. For every stable set SVS\subseteq V with S=r|S|=r, the graph GSG\setminus S^\perp is obtained by deleting SS^\perp. The Gvozdenović–Laurent bound. For every r1r\geq1,

ϑ(r)(G)r+maxSV, S stable, S=rϑ(0)(GS).\vartheta^{(r)}(G)\leq r+\max_{S\subseteq V,\ S\text{ stable},\ |S|=r}\vartheta^{(0)}(G\setminus S^\perp).

The source states that this conjecture implies the main convergence conjecture. Its general validity is not established in the supplied text.

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).

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.