# Questions tagged [metric-embeddings]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
627 views

### Two questions around the $abc$-conjecture

Let $d(a,b) = 1-\frac{2 \gcd(a,b)}{a+b}$, $d_{ABC}(a,b) = 1-\frac{2\gcd(a,b)^3}{ab(a+b)}$ be two metrics on natural numbers. The abc-conjecture can be formulated using these two metrics as: For ...
96 views

### Is the matrix $\mu_f(X_i \cap X_j)$ positive definite?

Let $X_1,\ldots, X_n$ be finite subsets of some larger finite set $Z$. Let $f:Z \rightarrow \mathbb{R}_{>0}$ be any function, and define a (counting) measure $\mu_f(X) = \sum_{x \in X} f(x)$ for a ...
43 views

228 views

I am interested in finitely generated groups which, endowed with their word metrics, do not admit bilipschitz embeddings into $L_1(0,1)$. I know two classes of such groups: (1) Heisenberg group $\... 1answer 347 views ### Embeddings of finitely generated groups into uniformly convex Banach spaces de Cornulier, Tessera, and Valette (Geom. Funct. Anal. 17 (2007), 770-792) conjectured that a finitely generated group$G$with its word metric admits a bilipschitz embedding into a Hilbert space if ... 1answer 241 views ### Reference request: embedding the hyperbolic triangulation in$\mathbb{R}^3$Let$T_d$be the infinite valence$d$triangulation of the hyperbolic plane, where each triangle is equilateral and$d \ge 7$. Question: Is there an isometric embedding from$T_d \to \mathbb{R}^3$? ... 3answers 426 views ### How hard is it to determine if a weighted graph can be isometrically embedded in R^3? Consider a graph$G$with nonnegative edge weights. Question: In$\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight? ... 1answer 261 views ### Probabilistic Johnson-Lindenstrauss Lemma for arbitrary points Consider the following standard formulation of the Johnson-Lindenstrauss lemma: Lemma (JL). For any$0<\epsilon < 1$and any integer$n$, let$k$be a positive integer such that$k\geq C\...
It is well-known that expanders are hard to embed into Hilbert (or $\ell^p$) spaces - any embedding of an expander with $n$ vertices has distortion $\Omega(\log n)$. Can anyone provide a reference (...
Let $X, Y$ be two random graphs on $n$ vertices (say, in $G(n, p)$ model for some $p$). Can anything (expectation, value with high probabiity, ...) be said about $D(X, Y)$, where $D$ is the minimal ...