OctoInformBeta

OpenAI preprint, September 2026 · §6. Exactly uniform demands

Lemma 6.1: And bounded Goemans-Linial value for a negative-type semimetric on n≥2n \ge 2 vertices with positive average distance and ℓ1\ell_1 contraction bounds

Cut-cone duality gives capacities with sparsity at least one.

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 n≥2n \ge 2 vertices indexed by [n]={1,…,n}[n] = \{1, \dots, n\}, equipped with a negative-type semimetric dd whose average pairwise distance is strictly positive, while every map from [n][n] into a finite-dimensional ℓ1\ell_1 space whose pairwise ℓ1\ell_1 distances are at most those of dd has its average pairwise ℓ1\ell_1 distance bounded by a common constant. The question is how the ratio between this average distance and the upper bound over all ℓ1\ell_1 contractions constrains the uniform sparsest-cut value and Goemans-Linial semidefinite programming (SDP) relaxation value of a suitable capacity instance on [n][n] under unit demands.

Definitions

A capacity function CC on nn vertices [n][n] is a nonnegative symmetric n×nn \times n real matrix with zero diagonal and entries cijc_{ij} for i,j∈[n]i, j \in [n].✦

The sparsity ϕC(B)\phi_C(B) of a non-empty proper subset B⊊[n]B \subsetneq [n] under a capacity function CC on nn vertices [n][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 nn vertices [n][n] is the infimum of the cut sparsity (1) over all non-empty proper cuts: OPT(C)=inf⁡{ϕC(B):∅≠B⊊[n]}.\mathrm{OPT}(C) = \inf \{\phi_C(B) : \emptyset \neq B \subsetneq [n]\}.(2)

A negative-type semimetric dd on nn vertices [n][n] is a real-valued function on pairs of vertices 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∈[n]i, j, k \in [n] and admits vectors x1,…,xn∈ℝnx_1, \dots, x_n \in \mathbb{R}^n giving dd as squared Euclidean distances: d(i,j)=∥xi−xj∥2for all i,j∈[n].d(i, j) = \|x_i - x_j\|^2 \qquad \text{for all } i, j \in [n].(3)✦

The sum over unordered pairs of a real-valued function ff on pairs of nn vertices [n][n] is the sum ∑i<jf(i,j)\sum_{i < j} f(i, j).✦ A feasible SDP metric dd on nn vertices [n][n] is a negative-type semimetric on [n][n] whose sum over unordered pairs satisfies ∑i<jd(i,j)=1\sum_{i < j} d(i, j) = 1.✦ The Goemans-Linial relaxation value GL(C)\mathrm{GL}(C) of a capacity function CC on nn vertices [n][n] is the infimum of the capacity-weighted sum over unordered pairs among all feasible SDP metrics dd on [n][n]: GL(C)=inf⁡{∑i<jcijd(i,j):d is a feasible SDP metric on [n]}.\mathrm{GL}(C) = \inf \left\{ \sum_{i < j} c_{ij}\, d(i, j) : d \text{ is a feasible SDP metric on } [n] \right\}.(4)✦

Finite Packing Duality

Given finite sets EE and KK, a matrix A∈ℝE×KA \in \mathbb{R}^{E \times K}, and a vector w∈ℝKw \in \mathbb{R}^K, the packing cone P(A,w)P(A, w) is the subset of ℝE×ℝ\mathbb{R}^E \times \mathbb{R} consisting of all pairs (y,γ)(y, \gamma) for which some vector t∈ℝKt \in \mathbb{R}^K with tk≥0t_k \ge 0 for every k∈Kk \in K satisfies ∑k∈KAektk≤yefor all e∈Eandγ≤∑k∈Kwktk.\sum_{k \in K} A_{ek} t_k \le y_e \quad \text{for all } e \in E \qquad \text{and} \qquad \gamma \le \sum_{k \in K} w_k t_k.(5)✦

Whenever EE and KK are finite sets, w∈ℝKw \in \mathbb{R}^K, and A∈ℝE×KA \in \mathbb{R}^{E \times K} has nonnegative entries Aek≥0A_{ek} \ge 0 and strictly positive column sums ∑e∈EAek>0\sum_{e \in E} A_{ek} > 0 for every k∈Kk \in K, P(A,w) is closed in ℝE×ℝ.P(A, w) \text{ is closed in } \mathbb{R}^E \times \mathbb{R}.(6)✦

On a finite set EE, every continuous linear functional f:ℝE×ℝ→ℝf : \mathbb{R}^E \times \mathbb{R} \to \mathbb{R} admits c∈ℝEc \in \mathbb{R}^E and q∈ℝq \in \mathbb{R} such that for all (y,γ)∈ℝE×ℝ(y, \gamma) \in \mathbb{R}^E \times \mathbb{R}, f(y,γ)=∑e∈Eceye+qγ.f(y, \gamma) = \sum_{e \in E} c_e y_e + q \gamma.(7)✦

Take finite sets EE and KK, a matrix A∈{0,1}E×KA \in \{0, 1\}^{E \times K} with ∑e∈EAek>0\sum_{e \in E} A_{ek} > 0 for every k∈Kk \in K, a nonnegative vector y∈ℝEy \in \mathbb{R}^E, a vector w∈ℝKw \in \mathbb{R}^K, and a real number W≥0W \ge 0 with wk≤Ww_k \le W for all k∈Kk \in K. Suppose further that β≥0\beta \ge 0 satisfies ∑k∈Kwktk≤β\sum_{k \in K} w_k t_k \le \beta for every vector t∈ℝKt \in \mathbb{R}^K with tk≥0t_k \ge 0 for all k∈Kk \in K and ∑k∈KAektk≤ye\sum_{k \in K} A_{ek} t_k \le y_e for all e∈Ee \in E. Then there exists c∈ℝEc \in \mathbb{R}^E such that ce≥0for all e∈E,wk≤∑e∈EAekcefor all k∈K,∑e∈Eceye≤β.\begin{aligned} c_e &\ge 0 \quad \text{for all } e \in E, \qquad w_k \le \sum_{e \in E} A_{ek} c_e \quad \text{for all } k \in K, \\ \sum_{e \in E} c_e y_e &\le \beta. \end{aligned}(8)✦

The Claim

Theorem 1. Let n≥2n \ge 2 be an integer, let dd be a negative-type semimetric on [n][n], and let a,b>0a, b > 0 be real numbers. Suppose that ∑i,j∈[n]d(i,j)≥n2a\sum_{i, j \in [n]} d(i, j) \ge n^2 a, and that for every finite set KK, with ∥u∥1=∑k∈K|uk|\|u\|_1 = \sum_{k \in K} |u_k| on ℝK\mathbb{R}^K, every map F:[n]→ℝKF : [n] \to \mathbb{R}^K satisfying ∥F(i)−F(j)∥1≤d(i,j)\|F(i) - F(j)\|_1 \le d(i, j) for all i,j∈[n]i, j \in [n] obeys ∑i,j∈[n]∥F(i)−F(j)∥1≤n2b\sum_{i, j \in [n]} \|F(i) - F(j)\|_1 \le n^2 b. Then there exists a capacity function CC on [n][n] such that OPT(C)≥1and0<GL(C)≤ba.\mathrm{OPT}(C) \ge 1 \qquad \text{and} \qquad 0 < \mathrm{GL}(C) \le \frac{b}{a}.(9)✦

In the paper, the result reads: for any semimetric dd on [n][n] with n≥2n \ge 2 that satisfies the triangle inequalities and is a squared Hilbert distance, and any a,b>0a, b > 0 satisfying n−2∑i,j=1nd(i,j)≥an^{-2} \sum_{i,j=1}^n d(i, j) \ge a and n−2∑i,j=1n∥F(i)−F(j)∥1≤bn^{-2} \sum_{i,j=1}^n \|F(i) - F(j)\|_1 \le b for every map FF into a finite-dimensional ℓ1\ell_1 space with ∥F(i)−F(j)∥1≤d(i,j)\|F(i) - F(j)\|_1 \le d(i, j) for all i,ji, j, there exist nonnegative capacities cijc_{ij} on unordered pairs of distinct vertices, forming CC, such that, with demand exactly one on every pair, OPT(C)≥1\mathrm{OPT}(C) \ge 1 and 0<GL(C)≤b/a0 < \mathrm{GL}(C) \le b / a.

What Is Checked

Cut-cone duality (9) is stated over an integer n≥2n \ge 2, negative-type semimetrics on [n][n] with pairwise sum and finite-dimensional ℓ1\ell_1 contraction bounds, capacity functions CC, cut sparsities, OPT(C)\mathrm{OPT}(C), sums over unordered pairs, feasible SDP metrics, and GL(C)\mathrm{GL}(C), whereas the finite-duality claims (8), (6), and (7) are stated over finite sets EE and KK, matrices A∈ℝE×KA \in \mathbb{R}^{E \times K}, weight vectors w∈ℝKw \in \mathbb{R}^K, real vectors on EE, packing cones P(A,w)P(A, w), and continuous linear functionals on ℝE×ℝ\mathbb{R}^E \times \mathbb{R}.