Finite-convergence conjecture for the theta hierarchy of a graph

From papers

Let GG be a graph, let α(G)\alpha(G) denote its stability number, and let ϑ(r)(G)\vartheta^{(r)}(G) denote the level-rr semidefinite parameter in the theta hierarchy.

Finite-convergence conjecture. For any graph GG,

ϑ(r)(G)=α(G)for some rN.\vartheta^{(r)}(G)=\alpha(G)\quad\text{for some }r\in\mathbb{N}.

This is a weaker conjecture than the De Klerk–Pasechnik conjecture: it asks only for convergence at some finite level, without specifying the level. Finite convergence at any step is not known in general.

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, “Finite convergence of sum-of-squares hierarchies for the stability number of a graph”, arXiv:2103.01574 (2024).

Solutions 0

No solutions have been posted yet.