The maximal-gamma conjecture for minimal graphs

From papers

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 GK^+2,1G \in \hat{\mathcal{K}}_{\ell+2,\ell-1} and aeˉ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.

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

No solutions have been posted yet.