Timeline for Are hyperbolic spaces actually better for embedding trees than Euclidean spaces?
Current License: CC BY-SA 4.0
34 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 12, 2023 at 23:43 | comment | added | Daniel Asimov | I assume that the trees in this question have at most countably many vertices and edges. Obviously no tree with more than continuum many vertices can be embedded in any hyperbolic n-space. (The case of a tree with exactly continuum many vertices is probably excluded since two distinct vertices of such a tree must come arbitrarily close to each other in the embedding.) | |
| Jul 12, 2023 at 1:15 | comment | added | Justin_other_PhD | @YCor Which is the Schottky article you are referring to? | |
| Feb 9, 2022 at 17:00 | vote | accept | Carlos_Petterson | ||
| Feb 9, 2022 at 1:51 | history | became hot network question | |||
| Feb 9, 2022 at 1:43 | answer | added | Will Sawin | timeline score: 3 | |
| Feb 8, 2022 at 19:35 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
deleted 1 character in body
|
| Feb 8, 2022 at 19:30 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 16 characters in body
|
| Feb 8, 2022 at 18:50 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 8 characters in body
|
| Feb 8, 2022 at 18:38 | comment | added | Carlos_Petterson | @TomTheQuant Yes, this should prevent Will Sawin + YCor's rescaling trickery; since its not clear if we can locally embed $(X,d)$ into $\mathbb{Z}^2$ in the tangent space of some point in $\mathbb{H}^2$. | |
| Feb 8, 2022 at 18:36 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 110 characters in body
|
| Feb 8, 2022 at 18:33 | comment | added | ABIM | Ah, but if we force $s=1$ then are such embeddings still obvious (for the tree metric case, not the converse)? | |
| Feb 8, 2022 at 16:30 | comment | added | YCor | And actually that we can rescale (this time, to large scale) makes it quite immediate that every finite (weighted) tree can be embedded with distortion $\le 1+\varepsilon$ into the hyperbolic plane (since it embeds isometrically into the asymptotic cone of $H^2$ which is a real tree). | |
| Feb 8, 2022 at 16:22 | answer | added | user476736 | timeline score: 7 | |
| Feb 8, 2022 at 15:40 | comment | added | YCor | @WillSawin Oh, yes indeed. | |
| Feb 8, 2022 at 15:29 | comment | added | Will Sawin | @YCor By the definition given in the question, we are allowed to shrink the metric by a scalar factor $s$, which may be arbitrarily small. Taking $s$ small enough, we should be able to embed the $n$-ball in $\mathbb Z^2$ with arbitrarily small distortion by using the local linearity of hyperbolic space. | |
| Feb 8, 2022 at 14:37 | comment | added | Carlos_Petterson | @YCor I also was thinking the same (About expanders being a good candidate). Do you have a reference for this last statement (I don't know this notion). | |
| Feb 8, 2022 at 14:35 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 568 characters in body
|
| Feb 8, 2022 at 14:35 | comment | added | YCor | Possibly expanders are good candidates, but I'm not familiar enough with this field to be sure. Possibly more plainly, "Euclidean pieces" (e.g., a copy of the $n$-ball in $\mathbf{Z}^2$) can't also be embedded with small distortion in $H^d$ (regardless of $d$). | |
| Feb 8, 2022 at 14:30 | comment | added | Carlos_Petterson | @YCor I clarified this (opposite point) in the question itself. | |
| Feb 8, 2022 at 14:26 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 47 characters in body
|
| Feb 8, 2022 at 14:18 | comment | added | Carlos_Petterson | I mean, aren't there finite metric spaces which don't admit `good' low distortion (bi-Lipschitz embedding with small distortion into low-dimensional Hyperbolic space $\mathbb{H}^n$ for small $n$)? | |
| Feb 8, 2022 at 14:15 | comment | added | YCor | A finite metric space can trivially be embedded bilipschitz into any infinite space (take any injective map). The issue is only to do it with good constants. | |
| Feb 8, 2022 at 14:13 | comment | added | Carlos_Petterson | But then are there finite metric spaces for which this is impossible? | |
| Feb 8, 2022 at 13:59 | comment | added | YCor | For embedding a bilipschitz tree of constant valency $\ge 3$ into the hyperbolic plane, there are plenty of ways. I don't know what is the first reference. One can produce this with actions of free groups; in this way the earliest reference is possibly Schottky. One can also inscribe such trees in regular tilings. | |
| Feb 8, 2022 at 13:56 | comment | added | YCor | That infinite bushy trees (bushy= of valency $\ge 3$ at every vertex) can't be embedded bilipschitz into Hilbert spaces is a result of Bourgain in the 80s (that they can't be embedded bilipschitz or even uniformly into Euclidean spaces just follows from growth conditions). | |
| Feb 8, 2022 at 12:48 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
deleted 30 characters in body
|
| Feb 8, 2022 at 12:47 | comment | added | Carlos_Petterson | @YCor Do you have a reference for those two results you mention? | |
| Feb 8, 2022 at 12:38 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 117 characters in body
|
| Feb 8, 2022 at 12:37 | comment | added | Carlos_Petterson | @YCor Yes I was implicitly assuming finiteness; but I'm interested in both situations. | |
| Feb 8, 2022 at 12:33 | comment | added | YCor | Are you implicitly assuming that $X$ is finite? Infinite trees (of bounded valency) can be bilipschitz-embedded into the hyperbolic space $\mathbb{H}^2$, but not into any Euclidean (or even Hilbert) space. | |
| Feb 8, 2022 at 12:32 | history | edited | YCor | CC BY-SA 4.0 |
formatting, changed tags
|
| Feb 8, 2022 at 12:21 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 137 characters in body
|
| Feb 8, 2022 at 12:16 | history | edited | Carlos_Petterson | CC BY-SA 4.0 |
added 137 characters in body
|
| Feb 8, 2022 at 9:30 | history | asked | Carlos_Petterson | CC BY-SA 4.0 |