Metric dimension reduction modulus for superlogarithmic distortion
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909730077671424 |
|---|---|
| author | Altschuler, Dylan J. Tikhomirov, Konstantin |
| author_facet | Altschuler, Dylan J. Tikhomirov, Konstantin |
| contents | The metric dimension reduction modulus $k^α_n(\ell_\infty)$ is the smallest $k$ such that every $n$--point metric space can be embedded into some $k$-dimensional normed space, with bi--Lipschitz distortion at most $α$. Determining sharp asymptotics for $k^α_n(\ell_\infty)$ is a fundamental task in metric geometry, with $α=Θ(\log n)$ bearing particular interest. A line of advances over the past decades has led to an upper bound on $k^α_n(\ell_\infty)$ for $α= Ω(\log n)$, but a matching lower bound has remained open. We close this gap, establishing: for every fixed $β> 0$, $$ k^α_n(\ell_\infty) =Θ\bigg(\frac{\log n}{\log(\fracα{\log n}+1)}\bigg)\quad \mbox{for every $α\geq β\log n$}. $$ This resolves a question from Naor's 2018 ICM plenary lecture. Our result is obtained by characterizing the minimum dimension $d$ for which, with high probability, a random regular graph admits an $α$--embedding into some $d$--dimensional normed space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_02785 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Metric dimension reduction modulus for superlogarithmic distortion Altschuler, Dylan J. Tikhomirov, Konstantin Metric Geometry Combinatorics Functional Analysis The metric dimension reduction modulus $k^α_n(\ell_\infty)$ is the smallest $k$ such that every $n$--point metric space can be embedded into some $k$-dimensional normed space, with bi--Lipschitz distortion at most $α$. Determining sharp asymptotics for $k^α_n(\ell_\infty)$ is a fundamental task in metric geometry, with $α=Θ(\log n)$ bearing particular interest. A line of advances over the past decades has led to an upper bound on $k^α_n(\ell_\infty)$ for $α= Ω(\log n)$, but a matching lower bound has remained open. We close this gap, establishing: for every fixed $β> 0$, $$ k^α_n(\ell_\infty) =Θ\bigg(\frac{\log n}{\log(\fracα{\log n}+1)}\bigg)\quad \mbox{for every $α\geq β\log n$}. $$ This resolves a question from Naor's 2018 ICM plenary lecture. Our result is obtained by characterizing the minimum dimension $d$ for which, with high probability, a random regular graph admits an $α$--embedding into some $d$--dimensional normed space. |
| title | Metric dimension reduction modulus for superlogarithmic distortion |
| topic | Metric Geometry Combinatorics Functional Analysis |
| url | https://arxiv.org/abs/2507.02785 |