1
$\begingroup$

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$?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
3
$\begingroup$

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} $.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have a proof (or reference) for the existence of this small $\varepsilon$? $\endgroup$
    – Dominic van der Zypen
    Commented Dec 10, 2018 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
    Commented Dec 10, 2018 at 8:47

You must log in to answer this question.

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