OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1.1: There exist c>0c > 0 and instances on nj→∞n_j \to \infty vertices with positive relaxation value and integrality ratio eventually at least clog⁡nj/(log⁡log⁡nj)3c\sqrt{\log n_j}/(\log\log n_j)^3

Uniform sparsest cut has an unbounded Goemans-Linial integrality gap.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take an nn-vertex instance of uniform sparsest cut and its Goemans-Linial relaxation. How large can the ratio between the sparsest-cut optimum and the relaxation value grow with nn when the relaxation value is positive?

Cuts and the Goemans-Linial Relaxation

On an nn-element vertex set V={1,…,n}V = \{1, \dots, n\}, a capacity function C=(cij)i,j∈VC = (c_{ij})_{i,j \in V} is a symmetric, nonnegative real matrix with zero diagonal.✦

The sparsity ΦC(B)\Phi_C(B) of a non-empty proper subset BB of VV with respect to a capacity function C=(cij)C = (c_{ij}) on an nn-element vertex set V={1,…,n}V = \{1, \dots, n\} is the ratio: ΦC(B)=∑i∈B,j∉Bcij|B|(n−|B|).\Phi_C(B) = \frac{\sum_{i \in B,\, j \notin B} c_{ij}}{|B|(n - |B|)}.(1)✦

The sparsest-cut value OPT(C)\mathrm{OPT}(C) of a capacity function CC on an nn-element vertex set VV is the infimum of the cut sparsity (1) over all non-empty proper subsets of VV: OPT(C)=inf⁡{ΦC(B):B⊆V,B≠∅,B≠V}.\mathrm{OPT}(C) = \inf \{ \Phi_C(B) : B \subseteq V,\; B \neq \emptyset,\; B \neq V \}.(2)✦

A negative-type semimetric dd on an nn-element vertex set V={1,…,n}V = \{1, \dots, n\} is a real-valued function on V×VV \times V that satisfies the triangle inequality d(i,k)≤d(i,j)+d(j,k)d(i,k) \le d(i,j) + d(j,k) for all i,j,k∈Vi,j,k \in V and is realized as squared Euclidean distances d(i,j)=∥xi−xj∥2d(i,j) = \|x_i - x_j\|^2 for some vectors x1,…,xnx_1, \dots, x_n in Euclidean space ℝn\mathbb{R}^n.✦

When vertices are indexed by V={1,…,n}V = \{1, \dots, n\}, a feasible semimetric dd on VV is a negative-type semimetric whose sum over unordered pairs satisfies ∑1≤i<j≤nd(i,j)=1\sum_{1 \le i < j \le n} d(i,j) = 1.✦

Relative to a capacity function C=(cij)C = (c_{ij}) on V={1,…,n}V = \{1, \dots, n\}, the Goemans-Linial relaxation value GL(C)\mathrm{GL}(C) is the infimum of the weighted sum over unordered pairs across all feasible semimetrics dd on VV: GL(C)=inf⁡{∑1≤i<j≤ncijd(i,j):d is a feasible semimetric on V}.\mathrm{GL}(C) = \inf \left\{ \sum_{1 \le i < j \le n} c_{ij}\, d(i,j) : d \text{ is a feasible semimetric on } V \right\}.(3)✦

The Claim

Theorem 1. There exist a constant c>0c > 0, a sequence of integers nj≥2n_j \ge 2 (j≥0j \ge 0) with nj→∞n_j \to \infty, and capacity functions C(j)C^{(j)} on njn_j vertices with GL(C(j))>0\mathrm{GL}(C^{(j)}) > 0 for all jj, such that for all sufficiently large jj, OPT(C(j))GL(C(j))≥clog⁡nj(log⁡log⁡nj)3.\frac{\mathrm{OPT}(C^{(j)})}{\mathrm{GL}(C^{(j)})} \ge \frac{c\sqrt{\log n_j}}{(\log\log n_j)^3}.(4)✦

What Is Checked

The bound (4) is stated for sequences of capacity functions C(j)C^{(j)} on nj≥2n_j \ge 2 vertices with nj→∞n_j \to \infty and GL(C(j))>0\mathrm{GL}(C^{(j)}) > 0, relating the sparsest-cut value (2) defined by (1) to the Goemans-Linial relaxation value (3) over feasible negative-type semimetrics.