The Setting
An integrality gap construction for the Goemans-Linial relaxation of uniform sparsest cut requires a finite vertex set carrying a negative-type semimetric that admits no low-distortion embedding. Starting from a positive integer with direction families of vectors in , the construction discretizes points of an open cube off threshold hyperplanes into rounded integer labels to form a finite vertex set. An integral Hilbert kernel combining Gaussian and Fourier components with linear chart-extension weights then provides the positive semidefinite Gram structure on those vertices.
Direction Families and Kernel Ingredients
The empirical covariance of an -tuple of vectors () in a real inner-product space along is the real scalar defined in (1): (1)✦ Given a natural number , vectors in a real inner-product space , and , the empirical sine transform is the vector defined in (2): (2)✦
Given a real threshold , a natural number , and a vector in a real inner-product space , the bad projection set is the set of -tuples defined in (3): (3)✦ For an ambient space , a subset , a natural number , and an -tuple , the number of bad samples is the count defined in (4): (4)✦
In dimension with and , a direction family is a collection of vectors in (with -th subfamily ) satisfying the conditions (5) for all , all with , all , and all with and : (5)✦ A pivoted direction family of dimension is a direction family in whose coordinates satisfy for all , , and . For a direction family of dimension with vectors , the normalized directions of are the vectors in defined for and by .
The inverse power of a real number and a natural number is the scalar .✦
The circle embedding of real parameters and is the Euclidean plane vector defined in (6): (6)✦ For a finite index set , directions in a real inner-product space , real parameters , points , and real functions , the kernel pairing is the scalar defined in (7): (7)✦ Given a finite index set and an index set , directions and points in a real inner-product space , weight functions with , and real parameters , the kernel Gram matrix is the real matrix whose -entry is defined in (8): (8)
The Claim
Definition 1. Given a finite index set , directions in a real inner-product space , real parameters , points , and real functions , the Hilbert kernel is the real scalar defined in (9): (9)✦
Theorem 1. Let be a finite index set, let be an index set, let and be families of vectors in a real inner-product space , let be real functions on , and let satisfy . Then for all , the kernel Gram matrix equals the Hilbert kernel as in (10): (10)✦
Theorem 2. Suppose and are finite index sets, and are families of vectors in a real inner-product space , are real functions on , and satisfy , , and . Then the real symmetric matrix with -entry is positive semidefinite (), as stated in (11): (11)✦
Definition 2. Given natural numbers and , directions in a real inner-product space , continuous linear maps (, where carries the Euclidean norm), real scalars , a chart index , and a vector , the chart extension is the real-valued function defined in (12): (12)✦ For real normed spaces and and continuous linear maps and , the residual operator is the continuous linear operator defined in (13), where denotes the identity operator on : (13)✦
Definition 3. In Euclidean space of dimension , the cube of radius is the subset of defined in (14) (with base cube ): (14)✦ A point in a real inner-product space is regular with respect to vectors in and a scale if it avoids all threshold hyperplanes , as in (15): (15)✦ Relative to vectors in a real inner-product space and a scale , the integer label of a point is the integer vector whose -th coordinate () is defined in (16): (16)✦ Given natural numbers , , and , families of vectors in (with -th subfamily ), and a scale , the rounded chart vertex set is the set of pairs defined in (17): (17)✦ Given natural numbers , , and , vector families in , and a scale , the vertex coordinate map is the map assigning to each vertex the Euclidean vector whose -th coordinate () is defined in (18): (18)✦ For a pivoted direction family of dimension with normalized directions and threshold scale , the source vertex set is the rounded chart vertex set defined in (19): (19)✦ For a pivoted direction family of dimension with normalized directions and a chart index , the source vertex map is the map sending each point regular for to the vertex in defined in (20): (20)✦
What Is Checked
The Hilbert kernel together with its Gram-matrix and positive semidefiniteness statements is stated over a real inner-product space , a finite index set and an index set (finite for positive semidefiniteness), direction and point families and in , real weights , and parameters with (and for positive semidefiniteness), while the chart-extension and residual operators together with the rounded chart vertex constructions are stated over real normed and Euclidean spaces equipped with bounded linear maps, arbitrary direction vectors at scale , and a pivoted direction family of dimension specialized to normalized directions and .