On ${\mathrm{\ell }}_1$ embeddings of finite metric spaces, and sphere-of-influence graphs

We introduce the {\em pair-cut cone $PCU{T}_n$} of metrics on sets with $n\ge 3$ elements, that correspond to linear combinations with non-negative coefficients of the cut-metrics resulting from cuts that are pairs. Given a metric, we fully characterize membership in the pair-cut cone in terms of quantities computed from the metric directly. We also prove a new result by which a metric $d$ that satisfies a system of inequalities, lies in the (full) cut cone of metrics, making it ${\mathrm{\ell }}_1$-embeddable into Euclidean space. We give applications of our results to the ${\mathrm{\ell }}_1$-embeddability of simple graphs into Euclidean space as {\em sphere-of-influence graphs}. We exhibit an example of a simple graph that admits no such ${\mathrm{\ell }}_1$-metric in the pair-cut cone.