The clique-rank bound conjecture for stretched-clique classes

About 1 year old · traced to

Let ℓ\ell be a positive integer. Let Kℓ+2,ℓ−1\mathcal{K}_{\ell+2,\ell-1} be the specified graph class, let ω(G)\omega(G) denote the clique number of GG, and let r+(G)r_+(G) denote its Lovász–Schrijver positive-semidefinite rank.

Clique-rank bound conjecture. For every positive integer ℓ\ell, if G∈Kℓ+2,ℓ−1G \in \mathcal{K}_{\ell+2,\ell-1} and ω(G)≥4\omega(G) \geq 4, then

r+(G)≤ℓ−1.r_+(G) \leq \ell-1.

The paper verifies the analogous phenomenon for the examined 4-minimal setting by showing that relevant graphs with clique number at least four have rank at most three. The extension to every positive integer ℓ\ell is conjectural.

References

Primary source

Yu Hin Au and Levent Tunçel, “A Computational Search for Minimal Obstruction Graphs for the Lovász–Schrijver SDP Hierarchy”, arXiv:2505.24735 (2026).

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.