9
$\begingroup$

This is from a physicist I know and as may be expected, I am threading my way between poorly defined and poorly translated.

What groups have Cayley graphs (w.r.t. a fixed finite generating set, and metrized so that each edge has length 1) that can be isometrically embedded in some reasonably nice space? Let us start with either f.d. Euclidean space, or f.d. hyperbolic space as the list of reasonably nice spaces.

This fails to mention whether the embedding should be a quasi-isometry, but let us bring in that question only if it seems to be looming in importance.

Yes, Cartesian products of finitely many copies of $\mathbf Z$ did occur to me, as well as (in dimension 2) triangle groups, but the length restrictions will severely restrict which ones work.

Helpful contributions will be either a few examples, or a few families, or pointers to what references might be relevant and anything else that might be relevant.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ If you are talking about the geodesic metric on the Cayley graph, there will never be even a locally isometric embedding in a Riemannian manifold. $\endgroup$
    – Lee Mosher
    Commented Feb 9, 2013 at 1:34
  • $\begingroup$ The question is too vague, so I do not think you will get any answer. One only can say something related. First of all isometric should mean quasiisometric (otherwise the question has no sense). Say if you are interested in Euclidean space then the group has polynomial growth --- it is sufficient, but that is for an other question. Asymptotic dimension is yet an other thing which should forbid embeddings in Hyperbolic spaces as well as Euclidean spaces. I am sure it can be continued forever... $\endgroup$
    – Anton Petrunin
    Commented Feb 9, 2013 at 2:31
  • $\begingroup$ For embedding groups into Euclidean spaces, try googling "hilbert compression exponents". But then again, this is very far from isometry, since in this theory you can get, at best, only Lipschitz embeddings. The requirement of embeddings being isometries, rather than some weaker classes of maps, seems very stringent. Is that really what you want? $\endgroup$
    – Marcin Kotowski
    Commented Feb 9, 2013 at 2:38
  • $\begingroup$ Okay, so the word metric does not survive so well in the ambient target space. My apologies. Now that I am brought to a bit more sense in this, I would have thought the taxi metric more useful than the max metric suggested below, but I don't trust myself at the moment. I will discuss all this with my friend. $\endgroup$
    – Matt Brin
    Commented Feb 9, 2013 at 3:56
  • 1
    $\begingroup$ What Lee said is 99.9% correct, since cycles embed isometrically into $S^1$ and the doubly infinite path embeds isometrically into $\mathbb{R}$. But these are the only cases. Indeed, a 3-pointed star in a graph (with 3 vertices at distance 1 of a central vertex) cannot be realized in a Riemannian manifold, using standard properties of geodesics. So a regular graph isometrically embeddable in a Riemannian manifold, necessarily has degree 2. $\endgroup$
    – Alain Valette
    Commented Feb 9, 2013 at 9:42

4 Answers 4

Reset to default
5
$\begingroup$

You can get a general answer avoiding the discussion on the choice of the generating set or of the metric on the larger space: which finitely generated (f.g.) groups have a bilipschitz embedding into a Euclidean space?

The answer is: virtually abelian f.g. groups (i.e. having a f.g. abelian group of finite index).

Indeed such groups admit proper cocompact actions on $\mathbf{R}^n$ for some $n$, giving rise to a quasi-isometric embedding which can easily be deformed to a bilipschitz embedding (alternatively, if you like to stay with an action, you can add some extra dimensions to make the action [whose kernel is finite] faithful but you lose cocompactness).

Conversely, if a group $\Gamma$ admits a bilipschitz embedding (coarse embedding --aka uniform embedding-- would be enough) into a Euclidean space, by a growth argument, the group has polynomial growth. So it is virtually nilpotent, by Gromov's polynomial growth Theorem. Then a result of general result of Pauls (2001) shows that a virtually nilpotent f.g. group admits a bilipschitz embedding into a CAT(0) space (or a uniformly convex Banach space). However, I guess that this follows, in this special case (Euclidean target) from Pansu's 1989 Annals paper about metric differentiability. The argument consists of observing that a bilipschitz map $\Gamma\to\mathbf{R}^n$ induces a bilipschitz embedding from the asymptotic cone (which is a simply connected nilpotent group $G$ with a Carnot-Caratheodory metric, by an older result of Pansu) into $\mathbf{R}^n$, to show that generically it is metrically differentiable and the differential is generically an injective homomorphism; in particular $G$ is abelian, and this holds iff the original discrete group is virtually abelian.

To go back to the original question: if you stick to isometric embeddings, what you get as a corollary is that if $\Gamma$ is a group with a finite generating set $S$, and $E$ is a finite-dimensional Banach space, then if the Cayley graph of $\Gamma$ w.r.t. $S$ embeds isometrically into $E$ then $\Gamma$ is virtually abelian (which is an extremely restrictive condition). The converse, however, depends on the specific choice of $S$ and the norm on $E$, as pointed out in other answers.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Even more, Scott Pauls proved in his thesis that a nilpotent group QI embeds in a CAT(0) space if and only if the group is virtually abelian. $\endgroup$
    – Misha
    Commented Feb 9, 2013 at 14:44
  • $\begingroup$ @Misha: it's the same: you can trivially change a QI (from a f.g. group) into a bilipschitz map (into a geodesic space not reduced to a point) by a little perturbation. $\endgroup$
    – YCor
    Commented Feb 9, 2013 at 19:27
0
$\begingroup$

I'd like to suggest to study the embeddings of Cayley graphs into $\mathbf Z^n$ with the max metrics $d$: $$d(x \ y) := \max_{k=1...n}\ |x_k-y_k|$$ My short note, on (the degree of) the universality of the $\mathbf R^n$ space with the max distance function (metrics), published in AMS Notices (in the late 1970s I'd think), may motivate the above approach. Let me stress that a finite metric space with integer distances is isometrically embeddable in $\mathbf R^n\quad\Leftrightarrow\quad$ it is embeddable into $\mathbf Z^n$, both spaces considered with the max metrics.

The max metrics makes embeddings easy.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Could you please give a more precise reference to your short note? It is impossible for me to guess either title of the paper or its author from the information on this page. $\endgroup$
    – Martin
    Commented Feb 9, 2013 at 3:41
  • $\begingroup$ I am sorry. My name is Włodzimierz Holsztyński. The title was something like "$\mathbf R^n$ as a universal metric space". (It's not easy for me to access a mathematical library, and I don't have my reprints at this time, and some of them I don't have at all). I'll post my name in my profile (thought that it was easily available to the participants of OM). $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 9, 2013 at 5:44
  • $\begingroup$ The taxi metrics is inferior to the max metrics in the context of your question. Indeed, you need ease of embeddings. The max product preserves the injectivity. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 9, 2013 at 7:30
  • $\begingroup$ Hm, your question admits more than one interpretation. I was concerned with the finite metric space which has the group as its set of points (there would be no other points), and the distance function induced by the Cayley graph. I was not concerned with the edges as parts of the space to be embedded. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 9, 2013 at 7:38
  • $\begingroup$ Thank you. I found the article: W. Holsztyński, $\mathbf R^n$ as a universal metric space, Notices AMS 25 (3) (1978) A- 367. $\endgroup$
    – Martin
    Commented Feb 9, 2013 at 10:27
0
$\begingroup$

In my first answer above I considered the embeddings of the group only (according to the Cayley graph). The requirement to embed isometrically the whole graph (an infinite metric space) in a sense does not add any complication at all when you embed the whole graph into $\mathbf R^n$ with the max metrics, while you may insist on embedding the vertices into $\mathbf Z^n\subseteq\mathbf R^n$  (if you want to).  Indeed, once vertices are embedded, the embedding can be extended to an isometric embedding of the whole graph (injectivity); furthermore, there is exactly one canonical (the simplest) isometric extension.

While considering other distance functions in the Euclidean spaces can be of some interest, it's clear to me that max is special, is "the right one"--"the best". This is also what the theory of categories strongly suggests.

Improve this answer
$\endgroup$
0
$\begingroup$

The Cayley graph of arbitrary cyclic group, for any $1$-element generating set, can be isometrically embedded in   $R^{\lceil\frac n2\rceil}$   with the distance function given by maximum (while the group itself gets embedded in   $Z^3$).

On the other hand it is not difficult to show that the cyclic group $Z/5$, with a 1-generator presentation, cannot be isometrically embedded in $R^3$ with the max distance.

Improve this answer
$\endgroup$
3
  • $\begingroup$ How do you that, say, for the cyclic group of order 3 ? $\endgroup$
    – Alain Valette
    Commented Feb 17, 2013 at 9:01
  • $\begingroup$ $Z/3$ is embeddable in $Z^^2$ with the max metric: $$\\{(0\ 0)\ \ (0\ 1)\ \ (1\ \ 0)\\}$$ while mapping onto the unit vectors of $R^3$ is nicer. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 17, 2013 at 9:34
  • $\begingroup$ A typo correction: that "Z^^2" above is really $Z^2$. $\endgroup$
    – Włodzimierz Holsztyński
    Commented Feb 17, 2013 at 9:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .