Finite-convergence conjecture for the theta hierarchy of a graph

At least 4 years old · documented by

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 r∈N.\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.

References

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

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.