de Klerk–Pasechnik conjecture

The 2002 conjecture asserts that the relevant semidefinite hierarchy reaches the graph’s stability number after $\alpha(G)-1$ steps, namely $\vartheta^{(\alpha(G)-1)}(G)=\alpha(G)$ for every graph $G$. Earlier literature treated the bound as open, especially when $\alpha(G)\ge 9$.

Known results

• The conjecture is known for perfect graphs, cycles, complements of cycles, and graphs with $\alpha(G)\le 8$.
• Finite convergence for every graph has been proved, but without the specific $\alpha(G)-1$ bound.
• Related copositive and sum-of-squares hierarchies include graph families requiring at least $\alpha(G)-1$ levels.

September 2026 claimed proof

A September 2026 arXiv preprint claims an explicit sum-of-squares certificate proving the de Klerk–Pasechnik conjecture, together with further certificates for Hoffman–Pereira matrices. This would settle the conjecture, but the retrieved sources identify the result as an unrefereed claim and provide no independent verification.

Current status (as of September 2026): A preprint claims the conjecture is proved, but verification is absent; before that claim, only finite convergence and restricted cases were settled.