9
$\begingroup$

I want to find a map $v\mapsto \tilde v$ from the vertex set of a connected infinite graph $\Gamma$ to a Euclidean space that meets the following two conditions:

  • there is $\varepsilon>0$ such that $|\tilde v-\tilde w|>\varepsilon$ for any $v\ne w$, and
  • $|\tilde v-\tilde w|\le 1$ for any pair of adjacent vertices $(v,w)$.

(Please note that this condition is much weaker than bi-Lipschitz embedding.)

If such map exists, then (obviously) there is a polynomial $P$ such that $|B_R(v)|\leqslant P(R)$, where $|B_R(v)|$ denotes the number of vertices on distance at most $R$ from $v$.

Is it sufficient?

Postscript. The question is answered in "The intrinsic dimensionality of graphs" by Krauthgamer and Lee [Combinatorica, 27(5) 2007]. (Thanks to aorq.)

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Did you try Cayley graph of the integer Heisenberg group? $\endgroup$
    – Moishe Kohan
    Commented Feb 8, 2023 at 16:17
  • 4
    $\begingroup$ Krauthgamer, R. and Lee, J.R., 2007. The intrinsic dimensionality of graphs. Combinatorica, 27(5), pp.551-585. $\endgroup$
    – aorq
    Commented Feb 8, 2023 at 16:32
  • 1
    $\begingroup$ @AlexandreEremenko Euclidean space is finite-dimensional by the definition :) $\endgroup$
    – Anton Petrunin
    Commented Feb 9, 2023 at 7:50
  • 1
    $\begingroup$ @AlexandreEremenko OK it seems that you are not joking, but this is the first time I see that Euclidean space might have infinite dimension. Instead, finite-dimensional Hilbert spaces are quite common. It does not really matter, but do you have a reference that use your terminology? $\endgroup$
    – Anton Petrunin
    Commented Feb 9, 2023 at 15:35
  • 1
    $\begingroup$ @AliTaghavi just a map from vertex set to $\mathbb{R}^n$. By anyway the reference provided by aorq seems to contain a complete answer. $\endgroup$
    – Anton Petrunin
    Commented Feb 11, 2023 at 17:03

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .