Large Goemans–Linial gaps for uniform sparsest cut
Status OpenLLM status Open unverified
Top Open Problems unknownunknown Not reported cataloguedOpenOpenStatement
Definitions and mathematical statement
Statement recorded in the supplied source.
Do unit-demand capacity instances on unbounded vertex counts n have Goemans–Linial semidefinite integrality gap at least $c\surd \log (n)/(\log $ $\log (n))^{3}$ for one absolute $c>0$, with positive relaxation value?Short English statement
Do unit-demand capacity instances on unbounded vertex counts n have Goemans–Linial semidefinite integrality gap at least $c\surd \log (n)/(\log $ $\log (n))^{3}$ for one absolute $c>0$, with positive relaxation value?Sources
- S1 Original question source or mathematical context. https://afonsobandeira.wordpress.com/2015/10/05/10l42pcheeger/.
- S2 OpenAI, manuscript citation page. Source of the formulation motivating this local problem. https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026/README.md.
Statement licence: CC-BY-4.0 · Source file
Contributions 1
OpenAI claim summary for CS-170
The result supplies the conclusion in this problem with its displayed hypotheses and quantifiers. The broader statements and applications in the manuscript are kept separate from the particular question above. The supporting result is manuscript 1 (family 117; 2026-09-24).
Large Goemans–Linial gaps for uniform sparsest cut
OpenAI's claim
OpenAI presents the following claims relevant to this question, with manuscript numbers following paper order in Sources. In manuscript 1 (family 117; 2026-09-24), the asserted result is that some growing uniform sparsest-cut instances have Goemans--Linial gaps at least $c\sqrt{\log n}/(\log\log n)^3$.Mathematical statement of the claimed result
Manuscript 1.
For nonnegative capacity instances with unit demand between every pair, write $\operatorname{OPT}(C)$ for minimum uniform cut sparsity and $\operatorname{GL}(C)$ for the Goemans--Linial negative-type metric relaxation. The claim gives an absolute $c>0$ and instances on $n_j\to\infty$ vertices, with positive relaxation value, such that \[ \frac{\operatorname{OPT}(C^{(j)})}{\operatorname{GL}(C^{(j)})} \ge c\frac{\sqrt{\log n_j}}{(\log\log n_j)^3} \] for every sufficiently large $j$. This is an integrality-gap sequence for exactly unit demands.Outline of the argument
For manuscript 1 (family 117; 2026-09-24), shared Hilbert features and rounded charts approximate a continuous parameter metric. Triangle defects are controlled both globally and within charts, and multiplicities replace the parameter law by exactly unit pair demands without losing the gap scale.Formal verification
For manuscript 1 (family 117; 2026-09-24), OpenAI lists Lean statements for this assertion: some growing uniform sparsest-cut instances have Goemans--Linial gaps at least $c\sqrt{\log n}/(\log\log n)^3$.The selected statement includes the clause used for this problem.
The linked family Comparator checks are UniformSparsestCut.lean.
Their named declarations include OAI.UniformSparsestCut.mainGap.
This site has not executed the Lean code. Described statement coverage is not an independent proof check.
Status caveat
The manuscripts were produced by an internal OpenAI model. OpenAI cautions that results without formalization can contain mistakes. This site has not independently checked the proofs; the label records the scope of OpenAI's claim.Sources
- OpenAI, Near-square-root logarithmic integrality gaps for uniform sparsest cut, 2026-09-24; citation key
OAI:Near-square-root-logarithmic-integrality-gaps-for-uniform-sparsest-cut-September-24-2026. PDF (GitHub); PDF (direct); Manuscript page and citation; Latest version; Statement source: thm:main. - Family 117: Lean scope.
- Comparator UniformSparsestCut.json.
- Comparator UniformSparsestCut.lean.
- OpenAI catalogue entry.