On ℓ 1 \ell_{1} embeddings of finite metric spaces, and sphere-of-influence graphs

Stanislav Jabuka, Ehsan Mirbagheri · 2025

Read On ℓ 1 \ell_{1} embeddings of finite metric spaces, and sphere-of-influence graphs by Stanislav Jabuka, Ehsan Mirbagheri (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-18975.txt.

Introduction

Stanislav Jabuka and Ehsan Mirbagheri study when a finite distance structure can be faithfully placed inside Euclidean space with the l1 metric. They introduce the pair-cut cone: metrics built from nonnegative combinations of cut metrics that split off pairs of points. Their paper, posted to arXiv in December 2025, fully characterizes membership in this cone using quantities computed directly from the metric. They also prove that a metric obeying a system of inequalities lies in the full cut cone, making it l1-embeddable.

The payoff is geometric. The results are applied to sphere-of-influence graphs, where vertices connect when neighborhoods overlap. They decide which graphs admit such embeddings. The authors also exhibit a simple graph admitting no l1 metric from the pair-cut cone at all. Negative examples like this one mark the true boundary of the theory, guiding network designers who model proximity with overlapping spheres.

Catalog record

CREATORStanislav Jabuka, Ehsan Mirbagheri
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-18975

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On ℓ 1 \ell_{1} embeddings of finite metric spaces, and sphere-of-influence graphs Stanislav Jabuka, Ehsan Mirbagheri Abstract . We introduce the pair-cut cone P ​ C ​ U ​ T n PCUT_{n} of metrics on sets with n ≥ 3 n\geq 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 d that satisfies a system of inequalities, lies in the (full) cut cone of metrics, making it ℓ 1 \ell_{1} -embeddable into Euclidean space. We give applications of our results to the ℓ 1 \ell_{1} -embeddability of simple graphs into Euclidean space as sphere-of-influence graphs . We exhibit an example of a simple graph that admits no such ℓ 1 \ell_{1} -metric in the pair-cut cone. 2020 Mathematics Subject Classification 05C12, 05C50 1. Introduction and Main Results This work concerns itself with two related problems. The first regards the question of when a metric space (V_{n},d) , with V_{n}=\{1,\dots,n\} , can isometrically be embedded into some Euclidean space equipped with the \ell_{1} -metric. The second considers simple graphs G and asks if they can be realized as sphere-of-influence graphs with respect to the \ell_{1} -metric in Euclidean space. While it is known that evey simple graph is the sphere-of-influence graph in some metric space, the realization question in the \ell_{1} -metric in Euclidean spaces, remains open. 1.1. \ell_{1} -embeddability and the pair-cut cone Let d be a semi-metric on the finite set V_{n}=\{1,\dots,n\} , with n\geq 3 . The question of whether (V_{n},d) admits an \ell_{1} -embedding into some Euclidean space \mathbb{R}^{m} has a long history with contributions by many authors, see for example [ 3 , 4 , 11 , 14 , 17 ] . \ell_{1} -embeddability is known to be equivalent to d belonging to the cut cone CUT_{n} , the positive cone spanned by cut-metrics \delta_{C}:V_{n}\times V_{n}\to\{0,1\} , which for a subset (or cut ) C\subset V_{n} are defined as \displaystyle\delta_{C}(i,j)=\left\{\begin{array}[]{cl}0&\quad;\quad|\{i,j\}\cap C|=0\text{ or }2,\cr&\cr 1&\quad;\quad|\{i,j\}\cap C|=1.\end{array}\right. We simultaneously view \delta_{C} as a semi-metric on V_{n} and as a vector in \mathbb{R}^{n\choose 2} . The latter space has dimension equal to the number of pairs in V_{n} , and with the lexicographic ordering of pairs, the \{i,j\} -th coordinate of the vector \delta_{C} equals \delta_{C}(\{i,j\}) . The problem of deciding whether d lies in CUT_{n} is known to be NP-complete [ 2 ] , and thus challenging. Many inequalities are known to obstruct a metric d from belonging to CUT_{n} , including for example the hypermetric inequalities and the null-type inequalities (cf. Section 6.1 in [ 11 ] ). Even more specialized inequalities can be found in [ 8 , 9 ] . Despite this wealth of obstructions, it remains difficult to decide if a metric d lies in the cut cone. We propose here the study of a simpler problem, that of determining whether a metric d belongs to the pair-cut cone PCUT_{n} , defined as the positive cone in \mathbb{R}^{n\choose 2} spanned by all {n\choose 2} cut-metrics \delta_{C} with |C|=2 , referred to as pair-cuts . Studying cut-metrics \delta_{C} associated to special cuts C\subset V_{n} rather than all possible cuts, is not a new idea. For example, in [ 10 ] , cuts of only even or odd type are studied. Similarly, in [ 7 ] , various types of cuts are considered, including equicuts, multicuts, equimulticuts, and balanced multicuts. Our approach of studying only pair-cuts is new, and we offer a complete characterization of membership in PCUT_{n} . Theorem 1.1 . For a metric d on V_{n} with n\geq 5 , define the trace Tr (d) of the metric d , and the star-trace s_{i} of a vertex i\in V_{n} as: (i) Tr (d)=\sum_{1\leq i<j\leq n}d(i,j) , (ii) s_{i}=\sum_{j\neq i}d(i,j) . Then d lies in the pair-cut cone PCUT_{n} if and only if (4) s_{i}+s_{j}\geq(n-4)\cdot d(i,j)+\frac{2}{n-2}\text{Tr}(d),\qquad\text{ for all pairs }\{i,j\}\subset V_{n}. To our knowledge, such a complete characterization of metrics belonging to the positive cone spanned by a specialized collection of cut-metrics is the first of its kind. The following corollary offers an easier to verify condition, one that is only necessary but generally not sufficient for d to lie in PCUT_{n} . Corollary 1.2 . If a metric d on V_{n} with n\geq 5 lies in the pair-cut cone PCUT_{n} , then (5) (n-2)s_{i}\geq\text{Tr}(d),\quad\text{ for all }i\in V_{n}. Applications of Theorem 1.1 and Corollary 1.2 , are given in Section 3 , specifically in Section 3.6 . We are able to prove Theorem 1.1 by a careful spectral analysis of a {n\choose 2}\times{n\choose 2} matrix S_{sq} that we call the square cut-matrix , and which is the underlying matrix of the linear system determining whether d lies in PCUT_{n} . More than just solving this linear system, we determine exactly when the unique solution has all non-negative coefficients. 1.2. \ell_{1} -embeddability and the cut cone Membership in the full cut cone CUT_{n} is likewise determined by searching for solutions to a linear system whose associated matrix S=S_{n} , which we call the full cut-matrix , has size \left(2^{n}-2\right)\times{n\choose 2} . The number 2^{n}-2 of rows of this matrix corresponds to the number of “non-trivial” cuts of V_{n} , that is all subsets of V_{n} other than the empty set and V_{n} itself. We were not able to prove an analogue of Theorem 1.1 in this general case. Nevertheless, we are able to offer this result. Theorem 1.3 . Let d be a metric on V_{n} with n\geq 5 . For a non-trivial cut C\subset V_{n} , define its star trace s_{C} as s_{C}=\sum_{i\in C,\,j\notin C}d(i,j) . If the inequality (6) s_{C}\geq\frac{|C|(n-|C|)}{{n\choose 2}+1}\cdot\text{Tr}(d) holds for every non-trivial cut C\subset V_{n} , then d\in CUT_{n} . Observe that if C=\{i\} , then s_{C}=s_{i} , the star trace of the i -th vertex i\in V_{n} , defined in Theorem 1.1 . This theorem is opposite in spirit to the many inequalities mentioned above (e.g. the hypermetric inequalities), which, if violated, obstruct a metric d from belonging to the cut cone CUT_{n} . In contrast, if a metric d satisfies the inequalities ( 6 ), that is sufficient for d to lie in CUT_{n} . 1.3. Sphere-of-Influence Graphs The second theme we explore is that of sphere-of-influence graphs , or SIGs for short. Given a simple graph G=(V_{n},E) with E the adjacency matrix of G (defined as the n\times n matrix with E_{i,j}=1 if the vertices i and j share an edge, and E_{i,j}=0 otherwise). A metric d on V_{n} is said to be a sphere-of-influence metric for G , or a SIG -metric for G , if the following constraints are satisfied: Firstly, define the radius of influence r_{i} of the vertex i\in V_{n} as r_{i}=\min_{j\neq i}d(i,j). Then d is a SIG -metric for G if for any pair \{i,j\}\subset V_{n} , we obtain (7) d(i,j)\left\{\begin{array}[]{ll}<r_{i}+r_{j},&\quad;\quad E_{i,j}=1,\cr\geq r_{i}+r_{j},&\quad;\quad E_{i,j}=0.\end{array}\right. We shall refer to ( 7 ) as the SIG -inequalities . It is not hard to show that SIG -metrics exist on every simple graph G

Read the complete text