The Setting
Take an -vertex instance of uniform sparsest cut and its Goemans-Linial relaxation. How large can the ratio between the sparsest-cut optimum and the relaxation value grow with when the relaxation value is positive?
Cuts and the Goemans-Linial Relaxation
On an -element vertex set , a capacity function is a symmetric, nonnegative real matrix with zero diagonal.✦
The sparsity of a non-empty proper subset of with respect to a capacity function on an -element vertex set is the ratio: (1)✦
The sparsest-cut value of a capacity function on an -element vertex set is the infimum of the cut sparsity (1) over all non-empty proper subsets of : (2)✦
A negative-type semimetric on an -element vertex set is a real-valued function on that satisfies the triangle inequality for all and is realized as squared Euclidean distances for some vectors in Euclidean space .✦
When vertices are indexed by , a feasible semimetric on is a negative-type semimetric whose sum over unordered pairs satisfies .✦
Relative to a capacity function on , the Goemans-Linial relaxation value is the infimum of the weighted sum over unordered pairs across all feasible semimetrics on : (3)✦
The Claim
Theorem 1. There exist a constant , a sequence of integers () with , and capacity functions on vertices with for all , such that for all sufficiently large , (4)✦
What Is Checked
The bound (4) is stated for sequences of capacity functions on vertices with and , relating the sparsest-cut value (2) defined by (1) to the Goemans-Linial relaxation value (3) over feasible negative-type semimetrics.