# Is every metric space quasi-isometric to a graph?

I've proved that if $(X, d)$ is a geodesic metric space then there exists a graph which is quasi-isometric to $X$. During this proof I've precisely used the fact that given two point in $X$ there exists a distance minimizing curve inside $X$ joining those two points.

After this I've tried to generalize my proof for arbitrary metric space, which I could not. Now I think it is not true in general. I've an intuitive guess for a counter-example: consider $X=\{x_i \mid i \in \mathbb{N}\}$ and $d(x_i,x_j)= |i^2 - j^2|$. I think for this metric space there dose not exists any graph quasi-isometric with $(X,d)$ but till now I could not able to prove it.

Can anybody provide me some hints or some counter-example for this fact, or may be some proof of the fact that given any metric space there exists a graph quasi-isometric to that space?

A metric space is QI to a connected graph iff it's large-scale geodesic. See Definition 3B1 here (my book with Pierre de la Harpe), and the characterization is an exercise (check the proof of Proposition 3B7(6)).

Large-scale geodesic implies large-scale connected, and your example (the set of squares of integers) is not even large-scale connected.

The answer is negative. A metric graph $G$ is path-connected: any two points can be joined by a continuous path $\gamma:[0,1]\to G$. A quasi-isometry can destroy path-connectivity, but only to a point. Namely, if $f:G\to X$ is a quasi-isometry then the composition of a continuous curve $\gamma :[0,1]\to G$ with a quasi-isometry $f:G\to X$ is a function $g:[0,1]\to X$ that does not jump by more than $B$; that is, its pointwise oscillation, defined as $$\omega_g(x) = \limsup_{y\to x} |g(y)-g(x)|$$ is at most $B$ for every $x$. One may call such functions $B$-roughly-continuous.

Your example, $\{n^2 : n\in\mathbb{N}\}$, can be used here. Pick $n$ such that $(n+1)^2-n^2 > B$, and argue that there is no $B$-roughly continuous function from $[0,1]$ to $X$ that takes on the values $n^2$ and $(n+1)^2$. Indeed, for such a function both sets $\{t:g(t)\le n^2\}$ and $\{t:g(t)\ge (n+1)^2\}$ would be nonempty, disjoint, and open in $[0,1]$.

(For example: if $g(t)\le n^2$, then $t$ has a neighborhood in which $g<n^2+B+\epsilon$, but this means $g\le n^2$ in this neighborhood if $\epsilon$ is small enough.)

• I didn't get this line "if $f:X\to G$ is a quasi-isometry to a graph, then for any $a,b\in X$ there exists $c\in X$ such that $d(f(a),f(c))=d(f(b),f(c))=\frac12 d(f(a),f(b))$" ... can you explain this to me... Aug 15 '15 at 13:42
• for an example if I consider $X$={$1,2,3$} $\subset \mathbb{R}$ and consider a graph $G$ with two vertices $v_1,v_2$ and an edge...now define $f: X \to G , f(1)=v_1, f(2)=v_1, f(3)=v_2$... $f$ is a quasi isometry..but it does not follow that criterion ... am I doing something wrong here?? Please correct me then... Aug 15 '15 at 13:47
• Okay, how about I delete the first version and keep only the second...
– user147263
Aug 15 '15 at 16:44
• sorry...the last line is not clear to me...why should they be open?? Aug 15 '15 at 20:26
• Added one more line at the end...
– user147263
Aug 15 '15 at 20:31