The enumeration conjecture for 3-minimal graphs
The enumeration conjecture for 3-minimal graphs
A 3-minimal graph is a graph whose relevant Lovász–Schrijver semidefinite-programming hierarchy obstruction has minimal rank three. Two graphs are considered the same when they are isomorphic.
Enumeration conjecture. There are exactly non-isomorphic -minimal graphs.
The computational search found 49 such graphs and provides evidence that the displayed list is complete, but the statement is presented as a conjecture rather than an established theorem.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.