The maximal-gamma conjecture for minimal graphs
The maximal-gamma conjecture for minimal graphs
Let be a positive integer, let be an -minimal graph, let be the vector used in the definition of , and let denote the all-ones edge vector. Let denote the specified class of sparse stretched cliques.
Maximal-gamma conjecture. For every positive integer , the maximum value of among -minimal graphs is attained by a sparse stretched clique and .
The observed 4-minimal examples motivate this conjecture, which predicts both the extremal graph class and the maximizing vector. No general proof or disproof is supplied in the source.
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.