Edge-length preserving embeddings of graphs between normed spaces
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913340251439104 |
|---|---|
| author | Dewar, Sean Kastis, Eleftherios Kitson, Derek Sims, William |
| author_facet | Dewar, Sean Kastis, Eleftherios Kitson, Derek Sims, William |
| contents | The concept of graph flattenability, initially formalized by Belk and Connelly and later expanded by Sitharam and Willoughby, extends the question of embedding finite metric spaces into a given normed space. A finite simple graph $G=(V,E)$ is said to be $(X,Y)$-flattenable if any set of induced edge lengths from an embedding of $G$ into a normed space $Y$ can also be realised by an embedding of $G$ into a normed space $X$. This property, being minor-closed, can be characterized by a finite list of forbidden minors. Following the establishment of fundamental results about $(X,Y)$-flattenability, we identify sufficient conditions under which it implies independence with respect to the associated rigidity matroids for $X$ and $Y$. We show that the spaces $\ell_2$ and $\ell_\infty$ serve as two natural extreme spaces of flattenability and discuss $(X, \ell_p )$-flattenability for varying $p$. We provide a complete characterization of $(X,Y)$-flattenable graphs for the specific case when $X$ is 2-dimensional and $Y$ is infinite-dimensional. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_02189 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Edge-length preserving embeddings of graphs between normed spaces Dewar, Sean Kastis, Eleftherios Kitson, Derek Sims, William Metric Geometry Combinatorics 05C10 (Primary) 52A21, 52C25 (Secondary) The concept of graph flattenability, initially formalized by Belk and Connelly and later expanded by Sitharam and Willoughby, extends the question of embedding finite metric spaces into a given normed space. A finite simple graph $G=(V,E)$ is said to be $(X,Y)$-flattenable if any set of induced edge lengths from an embedding of $G$ into a normed space $Y$ can also be realised by an embedding of $G$ into a normed space $X$. This property, being minor-closed, can be characterized by a finite list of forbidden minors. Following the establishment of fundamental results about $(X,Y)$-flattenability, we identify sufficient conditions under which it implies independence with respect to the associated rigidity matroids for $X$ and $Y$. We show that the spaces $\ell_2$ and $\ell_\infty$ serve as two natural extreme spaces of flattenability and discuss $(X, \ell_p )$-flattenability for varying $p$. We provide a complete characterization of $(X,Y)$-flattenable graphs for the specific case when $X$ is 2-dimensional and $Y$ is infinite-dimensional. |
| title | Edge-length preserving embeddings of graphs between normed spaces |
| topic | Metric Geometry Combinatorics 05C10 (Primary) 52A21, 52C25 (Secondary) |
| url | https://arxiv.org/abs/2405.02189 |