Consider a positively weighted connected simple graph with bounded degree $X$ . Denote by $d(x,y)$ the weight on the edge with endpoints $x$ and $y$. Suppose we have the following compatibility axioms:

  1. If $x_0,x_1,\ldots,x_{n-1},x_n$ and $y_0,y_1,\ldots,y_{n-1},y_n$ are two shortest paths in the unlabeled graph connecting the same points (i.e. $x_0=y_0$ and $x_n=y_n$), then $$ \sum d(x_{i-1},x_i)=\sum d(y_{i-1},y_i) $$

  2. If $x_0,x_1,\ldots,x_{n-1},x_n$ is a shortest path in the unlabeled graph connecting $x$ to $y$ and $y_0,y_1,\ldots,y_{m-1},y_m$, with $m>n$, is another path connecting $x$ to $y$, then

$$ \sum d(x_{i-1},x_i)<\sum d(y_{i-1},y_i) $$

Define a metric on the set of vertices just adding the various weights that you encounter moving along a shortest path. Suppose this metric is locally finite. The two axioms above say that this metric is well-defined and that it is in some sense compatible with the graph structure: the shortest-paths are geometrically the same and the distance is additive only along shortest paths.

General question: Has somebody studied these objects?

In particular, I am interested in the following questions:

Question: Suppose that our graph (without labels) is a tree with positive isoperimetric constant. Is it still true that it does not have bi-lipschitz embeddings (with the new metric) into a Hilbert space?

Also, let $\delta_1(X)$ be the best nonnegative constant, if exists, such that every side of a geodesic triangle is contained in the $\delta_1$-neigborhood of the other two sides. (If you like quasi-isometry, let $\delta$ be the infimum of all $\delta_1(Y)$ when $Y$ runs over the quasi-isometric class containing $X$). I am very tempted to say that $X$ has curvature bounded above by $-\frac{1}{\delta(X)}$.

Question: Has been this notion studied before? More specifically, what happens if I take, as graph, the 1-skeleton of a very good triangulation of a compact negatively curved metrizable manifold with labels given by the induced metric?

Thank you in advance,



1 Answer 1


I suspect there is some terminology confusion here. Without the axioms 1 and 2, what you define is just a 1-dimensional polyhedral space (they are usually called metric graphs). Or, more precisely, the set of vertices of a metric graph with the induced distance. The "weights" are usually referred to as "edge lengths".

The axioms impose an additional requirement that the shortest paths of the "weighted" metric are the same as those of the "unweighted" one. This is a very unusual requirement, and I wonder where it comes from. By the way, it is not satisfied in the triangulation example from your last question.

Concerning bi-Lipschitz embeddings: if the edge lengths are bounded away from 0 and infinity, then there is no difference from the unit lengths (the two metrics are bi-Lipschitz equivalent). And if they are not bounded, then any tree (I mean the set of vertices) can be bi-Lipschitz embedded into $\mathbb R$. Assign the $k$-th edge the length $10^k$, then the distance between any two vertices is dominated by the longest edge between them. Now mark one of the vertices as the origin and, for every vertex $x$, let $f(x)$ be the distance from $x$ to the origin. Then $f$ is a bi-Lipschitz map to $\mathbb R$.

I wonder what you mean by quasi-isometry (in your curvature bound definition). The notion of quasi-isometry I am used to allows arbitrary bi-Lipshitz rescaling, so the supremum and infimum of $\delta$ do not make sense. What you define is Gromov's $\delta$-hyperbolicity. This property is preserved under quasi-isometries, but the actual value of $\delta$ is not.

As for you last question, I presume that you are talking about the lift of the triangulation to the universal cover of the manifold (otherwise it is just a finite graph). In this case the graph is certainly Gromov-hyperbolic because it is quasi-isometric to the universal cover itself (with its negatively curved metric).

  • $\begingroup$ Thank you very much for interesting answer. Some questions/comments: 1) it comes from the fact that I want to try to prove some results for locally finite spaces and I am starting from a simpler case, but more general than graphs. I have modeled those axioms thinking about a "travelling salesman graph": graphs whose vertices are cities and the edges are weighted with the distances. 2) many thanks for the example of the tree. In fact I have proved a partial result where I allow that the distances go to zero, but they can diverge only in a controlled way (subexponential more or less); 3) I put $\endgroup$ Feb 18, 2012 at 21:11
  • $\begingroup$ the quasi-isometries just because, in case of Cayley graph, maybe one wants to allow certain quasi-isometries (those coming from changing the generating set of the group). But OK, it's not necessary. I know that I am defining just Gromov's hyperbolicity, but I am wondering whether or not looking at the problem in terms of curvature can be of some utility. I see that the graph of a triangulation may not be satisfy those axioms, but the definition of curvature makes sense also without those axioms. I am wondering if there is a nice relation between the curvatures of the manifold and the graph, $\endgroup$ Feb 18, 2012 at 21:20
  • $\begingroup$ in particular I am thinking about some convergence (or maybe a controlled error) when $n\rightarrow\infty$ and $T_n$ is the $n$-th barycentric subdivision of a fixed triangulation $T$. $\endgroup$ Feb 18, 2012 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.