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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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