OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Uniform sparsest cut and the Goemans-Linial relaxation: Cut sparsity for capacities on nn vertices and minimization over normalized negative-type semimetrics

Uniform sparsest cut and the Goemans-Linial relaxation.

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 a nonnegative integer nn and an ordered set [n][n] of nn vertices equipped with pairwise capacities. The uniform sparsest-cut problem and its Goemans-Linial semidefinite programming (SDP) relaxation compare bipartitions of [n][n] with negative-type semimetrics on [n][n]. The question is how small the relaxation value can be relative to the combinatorial optimum.

The Definition

Definition 1. A capacity function C=(cij)i,j∈[n]C = (c_{ij})_{i, j \in [n]} on [n][n] is a real n×nn \times n matrix satisfying cij≥0,cij=cji,cii=0for all i,j∈[n].c_{ij} \ge 0, \qquad c_{ij} = c_{ji}, \qquad c_{ii} = 0 \qquad \text{for all } i, j \in [n].(1)✦

Given any function f:[n]×[n]→ℝf \colon [n] \times [n] \to \mathbb{R}, the sum over unordered pairs ∑i<jf(i,j)\sum_{i < j} f(i, j) is the real number ∑i<jf(i,j)=∑i∈[n]∑j∈[n]i<jf(i,j).\sum_{i < j} f(i, j) = \sum_{i \in [n]} \sum_{\substack{j \in [n] \\ i < j}} f(i, j).(2)✦

For a capacity function CC satisfying (1) and a nonempty proper subset B⊊[n]B \subsetneq [n], the uniform sparsest-cut ratio ΦC(B)\Phi_C(B) is the real number Φ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|)}.(3)✦

The uniform sparsest-cut value OPT(C)\mathrm{OPT}(C) of a capacity function CC on [n][n] is the real number defined from (3) by OPT(C)=inf⁡{ΦC(B):∅⊊B⊊[n]}.\mathrm{OPT}(C) = \inf \{ \Phi_C(B) : \emptyset \subsetneq B \subsetneq [n] \}.(4)✦

In nn-dimensional Euclidean space ℝn\mathbb{R}^n with norm ∥⋅∥\|\cdot\|, a negative-type semimetric dd on [n][n] is a function d:[n]×[n]→ℝd \colon [n] \times [n] \to \mathbb{R} for which there exist vectors xi∈ℝnx_i \in \mathbb{R}^n (i∈[n]i \in [n]) satisfying d(i,j)=∥xi−xj∥2andd(i,k)≤d(i,j)+d(j,k)for all i,j,k∈[n].d(i, j) = \|x_i - x_j\|^2 \quad \text{and} \quad d(i, k) \le d(i, j) + d(j, k) \qquad \text{for all } i, j, k \in [n].(5)✦

A feasible SDP metric dd on [n][n] is a negative-type semimetric (5) whose sum (2) satisfies ∑i<jd(i,j)=1.\sum_{i < j} d(i, j) = 1.(6)✦

Associated to each capacity function CC on [n][n], the Goemans-Linial relaxation value GL(C)\mathrm{GL}(C) is the real number defined from (2) and (6) by GL(C)=inf⁡{∑i<jcijd(i,j):d is a feasible SDP metric on [n]}.\mathrm{GL}(C) = \inf \Bigl\{ \sum_{i < j} c_{ij} d(i, j) : d \text{ is a feasible SDP metric on } [n] \Bigr\}.(7)✦

What Is Checked

The definitions (1) through (7) are stated over a nonnegative integer nn, real-valued functions on [n]×[n][n] \times [n], vertex subsets B⊆[n]B \subseteq [n], capacity matrices CC in (3), (4), and (7), and vectors in nn-dimensional Euclidean space ℝn\mathbb{R}^n.