The clique-rank bound conjecture for stretched-clique classes

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 GK+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.

Sources & referencesView supporting material

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.