A universal threshold for geometric embeddings of trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908971813568512 |
|---|---|
| author | Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos |
| author_facet | Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos |
| contents | A graph $G=(V,E)$ is geometrically embeddable into a normed space $X$ when there is a mapping $ζ: V\to X$ such that $\|ζ(v)-ζ(w)\|_X\leqslant 1$ if and only if $\{v,w\}\in E$, for all distinct $v,w\in V$. Our result is the following universal threshold for the embeddability of trees. Let $Δ\geqslant 3$, and let $N$ be sufficiently large in terms of $Δ$. Every $N$--vertex tree of maximal degree at most $Δ$ is embeddable into any normed space of dimension at least $64\,\frac{\log N}{\log\log N}$, and complete trees are non-embeddable into any normed space of dimension less than $\frac{1}{2}\,\frac{\log N}{\log\log N}$. In striking contrast, spectral expanders and random graphs are known to be non-embeddable in sublogarithmic dimension. Our result is based on a randomized embedding whose analysis utilizes the recent breakthroughs on Bourgain's slicing problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_15212 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A universal threshold for geometric embeddings of trees Altschuler, Dylan J. Dodos, Pandelis Tikhomirov, Konstantin Tyros, Konstantinos Combinatorics Functional Analysis Metric Geometry Probability A graph $G=(V,E)$ is geometrically embeddable into a normed space $X$ when there is a mapping $ζ: V\to X$ such that $\|ζ(v)-ζ(w)\|_X\leqslant 1$ if and only if $\{v,w\}\in E$, for all distinct $v,w\in V$. Our result is the following universal threshold for the embeddability of trees. Let $Δ\geqslant 3$, and let $N$ be sufficiently large in terms of $Δ$. Every $N$--vertex tree of maximal degree at most $Δ$ is embeddable into any normed space of dimension at least $64\,\frac{\log N}{\log\log N}$, and complete trees are non-embeddable into any normed space of dimension less than $\frac{1}{2}\,\frac{\log N}{\log\log N}$. In striking contrast, spectral expanders and random graphs are known to be non-embeddable in sublogarithmic dimension. Our result is based on a randomized embedding whose analysis utilizes the recent breakthroughs on Bourgain's slicing problem. |
| title | A universal threshold for geometric embeddings of trees |
| topic | Combinatorics Functional Analysis Metric Geometry Probability |
| url | https://arxiv.org/abs/2504.15212 |