The Setting
Take a finite vertex set equipped with a probability distribution and a map into a normed space whose squared distances satisfy the triangle inequality. In the Goemans-Linial relaxation of uniform sparsest cut, all pairs of vertices carry equal demand, whereas a measure-supported construction weights pairs of vertices by . Replicating each vertex in proportion to turns the weighted problem into an unweighted uniform-demand instance on a finite set of copies. The question is how closely the resulting copy proportions track in distance, and how squared-distance averages and -contraction bounds transfer to the replicated vertices.
Negative-type Semimetrics
A negative-type semimetric (metric of negative type) on vertices is a real-valued function on pairs of vertices that satisfies the triangle inequality for all vertices , and for which there exists a map from the vertices into -dimensional Euclidean space such that equals the squared Euclidean distance for all vertices .✦
Vertex Replication
Given a finite set , a nonnegative integer , and real weights , the copy count of a vertex is the positive integer (1)✦ The replicated vertex set associated with and , formed from the multiplicities (1), is the finite set of pairs (2)✦
The total copy count of the replicated vertex set is the cardinality .✦ Given a bijection between and , the copy-to-vertex map sends each index to the vertex of its corresponding pair .✦ The replicated distribution is the function assigning to each .✦
Size and Distribution Bounds
When is a probability distribution on , so that for all and , the total copy count satisfies (3)✦ If in addition , then the distance between the replicated distribution and obeys (4)✦
The product expectation bound states that if are probability distributions on , , and satisfies for all , then (5)✦
The source uniform size bound states that whenever integers and satisfy and , (6)✦
The Claim
Theorem 1. Let be a finite set, let be an integer, and let be a probability distribution on ( for all and ). Let be a map into a normed space satisfying for all . Suppose with satisfy for all and , and suppose that for every finite set and every map obeying for all , one has . Taking the total copy count and copy-to-vertex map for and , and setting for and , the function is a negative-type semimetric on and the bounds (7)✦ hold, the second inequality for every finite set and every map satisfying for all .
What Is Checked
The vertex replication construction (1) and (2), the replication transfer estimate (7), and the bounds (4), (5), (3), and (6) are stated over any finite set , nonnegative integer (positive in (4) and (7)), probability distributions on , bounded real functions on , integers and , and maps into a normed space obeying the squared-distance triangle inequality with diameter bound and average and -contraction bounds and .