The maximal-gamma conjecture for minimal graphs

About 1 year old · traced to

Let ℓ\ell be a positive integer, let GG be an ℓ\ell-minimal graph, let aa be the vector used in the definition of γℓ−1(G,a)\gamma_{\ell-1}(G,a), and let eˉ\bar{e} denote the all-ones edge vector. Let K^ℓ+2,ℓ−1\hat{\mathcal{K}}_{\ell+2,\ell-1} denote the specified class of sparse stretched cliques.

Maximal-gamma conjecture. For every positive integer ℓ\ell, the maximum value of γℓ−1(G,a)\gamma_{\ell-1}(G,a) among ℓ\ell-minimal graphs is attained by a sparse stretched clique G∈K^ℓ+2,ℓ−1G \in \hat{\mathcal{K}}_{\ell+2,\ell-1} and a≔eˉa \coloneqq \bar{e}.

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.

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.