The sparsest minimal-graph conjecture
The sparsest minimal-graph conjecture
For a positive integer , let an -minimal graph mean a graph that is minimal at Lovász–Schrijver rank . Let denote the specified class of sparse stretched cliques.
Sparsest minimal-graph conjecture. For every positive integer , a sparsest -minimal graph is a sparse stretched clique in .
The conjecture generalizes the observed structure of the sparsest 4-minimal graphs, all 40 of which were found to be sparse stretched cliques in . Its validity for arbitrary positive integer 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.