The Setting
Take vertices indexed by , equipped with a negative-type semimetric whose average pairwise distance is strictly positive, while every map from into a finite-dimensional space whose pairwise distances are at most those of has its average pairwise distance bounded by a common constant. The question is how the ratio between this average distance and the upper bound over all contractions constrains the uniform sparsest-cut value and Goemans-Linial semidefinite programming (SDP) relaxation value of a suitable capacity instance on under unit demands.
Definitions
A capacity function on vertices is a nonnegative symmetric real matrix with zero diagonal and entries for .✦
The sparsity of a non-empty proper subset under a capacity function on vertices is the ratio (1) The sparsest-cut value of a capacity function on vertices is the infimum of the cut sparsity (1) over all non-empty proper cuts: (2)
A negative-type semimetric on vertices is a real-valued function on pairs of vertices that satisfies the triangle inequality for all and admits vectors giving as squared Euclidean distances: (3)✦
The sum over unordered pairs of a real-valued function on pairs of vertices is the sum .✦ A feasible SDP metric on vertices is a negative-type semimetric on whose sum over unordered pairs satisfies .✦ The Goemans-Linial relaxation value of a capacity function on vertices is the infimum of the capacity-weighted sum over unordered pairs among all feasible SDP metrics on : (4)✦
Finite Packing Duality
Given finite sets and , a matrix , and a vector , the packing cone is the subset of consisting of all pairs for which some vector with for every satisfies (5)✦
Whenever and are finite sets, , and has nonnegative entries and strictly positive column sums for every , (6)✦
On a finite set , every continuous linear functional admits and such that for all , (7)✦
Take finite sets and , a matrix with for every , a nonnegative vector , a vector , and a real number with for all . Suppose further that satisfies for every vector with for all and for all . Then there exists such that (8)✦
The Claim
Theorem 1. Let be an integer, let be a negative-type semimetric on , and let be real numbers. Suppose that , and that for every finite set , with on , every map satisfying for all obeys . Then there exists a capacity function on such that (9)✦
In the paper, the result reads: for any semimetric on with that satisfies the triangle inequalities and is a squared Hilbert distance, and any satisfying and for every map into a finite-dimensional space with for all , there exist nonnegative capacities on unordered pairs of distinct vertices, forming , such that, with demand exactly one on every pair, and .
What Is Checked
Cut-cone duality (9) is stated over an integer , negative-type semimetrics on with pairwise sum and finite-dimensional contraction bounds, capacity functions , cut sparsities, , sums over unordered pairs, feasible SDP metrics, and , whereas the finite-duality claims (8), (6), and (7) are stated over finite sets and , matrices , weight vectors , real vectors on , packing cones , and continuous linear functionals on .