The sparsest minimal-graph conjecture

For a positive integer \ell, let an \ell-minimal graph mean a graph that is minimal at Lovász–Schrijver rank \ell. Let K^+2,1\hat{\mathcal{K}}_{\ell+2,\ell-1} denote the specified class of sparse stretched cliques.

Sparsest minimal-graph conjecture. For every positive integer \ell, a sparsest \ell-minimal graph is a sparse stretched clique in K^+2,1\hat{\mathcal{K}}_{\ell+2,\ell-1}.

The conjecture generalizes the observed structure of the sparsest 4-minimal graphs, all 40 of which were found to be sparse stretched cliques in K^6,3\hat{\mathcal{K}}_{6,3}. Its validity for arbitrary positive integer \ell remains open.

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.