On $\ell_1$ embeddings of finite metric spaces, and sphere-of-influence graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909973269708800 |
|---|---|
| author | Jabuka, Stanislav Mirbagheri, Ehsan |
| author_facet | Jabuka, Stanislav Mirbagheri, Ehsan |
| contents | We introduce the {\em pair-cut cone $PCUT_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 $\ell_1$-embeddable into Euclidean space.
We give applications of our results to the $\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 $\ell_1$-metric in the pair-cut cone. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_18975 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On $\ell_1$ embeddings of finite metric spaces, and sphere-of-influence graphs Jabuka, Stanislav Mirbagheri, Ehsan Metric Geometry Combinatorics 05C12, 05C50 We introduce the {\em pair-cut cone $PCUT_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 $\ell_1$-embeddable into Euclidean space. We give applications of our results to the $\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 $\ell_1$-metric in the pair-cut cone. |
| title | On $\ell_1$ embeddings of finite metric spaces, and sphere-of-influence graphs |
| topic | Metric Geometry Combinatorics 05C12, 05C50 |
| url | https://arxiv.org/abs/2512.18975 |