This is the question that I should have asked before asking this older question.

If $(X,d)$ is a metric space, we associate with it a simple, undirected graph, called its proximity graph $G(X,d)$ given by $V(G(X,d)) = X$ and $$E(G(X,d)) = \big\{\{x,y\}:x\neq y\in X \text{ and } d(x,y)\leq 1\big\}.$$

As MO user @YCor pointed out in a comment to a recent deleted question, given any (not necessarily finite) simple, undirected graph $G=(V,E)$, the map $d:V\times V\to \mathbb{R}$ given by $d(v,v) = 0$ for $v\in V$, $d(v,w)=1$ iff $\{v,w\}\in E$ and $d(v,w) = 2$ otherwise gives a metric on $V$ such that $G\cong G(V,d)$.

Question. If $G=(V,E)$ is a finite graph, is there a positive integer $n\in\mathbb{N}$ and a finite subset $S\subseteq \mathbb{R}^n$ such that $G \cong G(S,||\cdot||),$ where $||\cdot||$ denotes the Euclidean metric that $S$ inherits from $\mathbb{R}^n$?


Yes. If $n=|V|$, then for small $\varepsilon$ any metric spaces on $n$ points with distances belonging to $\{1-\varepsilon, 1+\varepsilon\} $ is embeddable to $\mathbb{R}^{n-1} $.

  • $\begingroup$ Do you have a proof (or reference) for the existence of this small $\varepsilon$? $\endgroup$ – Dominic van der Zypen Dec 10 '18 at 8:33
  • 4
    $\begingroup$ Both proof and reference. You start with a regular simplex $\{v_0,v_1,\dots,v_{n-1}\}$, with all distances equal to 1, and look for the points $u_i$ close to $v_i$ in the affine hull of $v_0,\dots,v_i$. The map which sends such a sequence of vertices to the array of mutual distances has non-zero Jacobian (easy to see in appropriate coordinates), thus the claim follows from inverse function theorem. Alternatively you may use explicit conditions on embeddability to $\mathbb{R}^d$ via positive definiteness, like Schoenberg. $\endgroup$ – Fedor Petrov Dec 10 '18 at 8:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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