The Setting
In constructing integrality gaps for the Goemans-Linial relaxation of uniform sparsest cut, one seeks a finite negative-type semimetric, meaning a symmetric distance on a finite set that satisfies all triangle inequalities and admits a squared Euclidean realization . Given families of directions in for a large positive integer , one forms a finite vertex set from rounded projections of points in . The central problem is to convert an approximate inner-product realization on these vertices into a negative-type semimetric whose macroscopic distances match a rescaled Euclidean metric on , while controlling steps between adjacent labels, vertex cardinality, diameter, weighted average squared distance, and average contraction.
Direction Families and Chart Operators
For a nonnegative integer , a real inner-product space , an -tuple , and vectors , the empirical covariance is the real number defined by (1), and the empirical sine transform is the vector defined by (2): (1)✦ (2)✦ Given a real inner-product space , a nonnegative integer , a real threshold , and a vector , the bad projection set is the subset of consisting of all -tuples satisfying for some .✦ For any subset of an ambient space and any -tuple , the number of bad samples is the nonnegative integer counting indices with .✦
Given a positive integer , set and . A direction family in dimension is a collection of vectors for and , with -th subfamily , satisfying five conditions: every vector obeys ; distinct vectors and () in the same subfamily are nonparallel ( for all ); every unit vector satisfies for each ; every with satisfies for each ; and every unit vector obeys .✦ A pivoted direction family in dimension is a direction family in dimension satisfying in addition for all , , and .✦
Let be a real inner-product space and a nonnegative integer; the chart operator of an -tuple is the continuous linear map into -dimensional Euclidean space with -th component for each and each .✦ Given any continuous linear map between real inner-product spaces and a real constant satisfying for all , the Gram operator is the bijective continuous linear map obtained by composing the adjoint with ✦, and the left pseudoinverse is the continuous linear map .✦
For a positive integer and a direction family in dimension , the scaled direction family of is the collection of normalized vectors for and , with -th subfamily and chart operator .✦ The frame lower bound constant for is the real number ✦, and the chart pseudoinverse at chart index is the left pseudoinverse of .✦
Rounded Charts and Macro Constants
For a positive integer and a real number , the cube of radius in is the subset .✦ Given a real inner-product space , an -tuple , and a real grid scale , the integer chart label of is the vector with -th coordinate ✦, and a point is regular for at scale if for every and every integer .✦ For nonnegative integers and , an -tuple of -tuples in , and a scale , the rounded chart vertex set is the set of all pairs with and for which some is regular for at scale and satisfies .✦ The rounded chart coordinate of is the vector (with norm) whose -th entry is , and the chart index of is the integer .✦
For a real number and a nonnegative integer , the inverse power of to is the real number .✦ Given a positive integer and a direction family in dimension , set the grid scale and the angle error scale ; the source vertex set is the set ✦, and for each and each regular for at scale , the chart vertex is the pair .✦
The profile function is the function defined by ✦, and the profile constant is the real number given by (3): (3)✦ For nonnegative integers and real numbers , the macro cost function is defined by (4): (4)✦ For a positive integer , the macro cost error is the real number given by (5): (5)✦
The source metric constant is the real number ✦, and the diameter constant is the real number .✦ Let be the smooth bump function centered at with inner radius and outer radius ✦, let the standard mollifier be the normalization of with respect to Lebesgue measure✦, and let the mollifier derivative integral be the real number .✦ For a positive integer , the contraction weight function is the real number ✦, and the contraction constant is the real number given by (6): (6)✦
The Claim
Theorem 1. Suppose and are finite index sets, is a set, is a real inner-product space, and is a real normed space. Given maps , , , and , together with real numbers , , , and , set for . Assume that for all , one has and , and that whenever . Then there exists an embedding into Euclidean space indexed by satisfying (7) for all : (7)✦
Let be an integer satisfying , and let be a pivoted direction family in dimension . Then there exists a map into Euclidean space indexed by satisfying (8) for all : (8)✦
Let be an integer, let be a pivoted direction family in dimension , and let satisfy the second inequality of (8) for all . Then for all chart indices and all points regular at scale for and respectively, (9) holds: (9)✦
If , is a pivoted direction family in dimension , and two vertices and in satisfy at some index and for all , then their rounded chart coordinates satisfy (10): (10)✦
When and is a pivoted direction family in dimension , the cardinality of satisfies (11): (11)✦
Let be an integer satisfying and , and let be a pivoted direction family in dimension . Then there exist a map and weights satisfying (12) for all , every finite set , and every map with for all : (12)✦
In the paper, the result reads: there exists a negative-type semimetric on comparing with within , with adjacent label jump bound , size bound , diameter bound , and average distance at least , where stands for the paper’s , for its , and for its constants .
What Is Checked
The metric repair bound (7) is stated over arbitrary finite index sets and , a set , real inner-product spaces and , and real parameters , , , and , while the remaining claims (8) through (12) are stated over the source vertex set , rounded chart coordinates , chart pseudoinverses , and the profile, macro, and contraction constants for a pivoted direction family in dimension (with in (10), in (11), in (9), additionally in (8), and in (12)). For the chart constructions, every positive integer has a strictly positive frame lower bound constant ✦, and every pivoted direction family in dimension satisfies the frame energy lower bound for all and all .