The sparsest minimal-graph conjecture

About 1 year old · traced to

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.

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.