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

About 5 years old · traced to

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 S⊥S^\perp denote the vertices adjacent to or equal to a stable set SS. For every stable set S⊆VS\subseteq V with ∣S∣=r|S|=r, the graph G∖S⊥G\setminus S^\perp is obtained by deleting S⊥S^\perp. The Gvozdenović–Laurent bound. For every r≥1r\geq1,

ϑ(r)(G)≤r+max⁡S⊆V, S stable, ∣S∣=rϑ(0)(G∖S⊥).\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.

References

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.