Characterization of finite metric spaces with distances taking rational values

33 Views Asked by At

Given a connected simple finite graph $H$, there is always a way of equipping it with a metric,

$$ \begin{align} & \rho_H : V(H) \times V(H) \longrightarrow \mathbb{R} \\ & \quad \quad (v,w) \longmapsto \min_{\xi \in P(v,w)} l(\xi) \end{align} $$

where $P(v,w)$ are the paths from $v$ to $w$ and $l(v_0 \dots v_k) = k-1$. These path sets are non-empty because $H$ is connected, and we admit $P(v,v) = \{v\}$ for all $v \in V(H)$, the trivial paths.

Now, given a finite metric space $(X,d)$ with $\operatorname{im} d \subseteq \mathbb{Q}$, does there always exist a connected finite simple graph $H$ and $\alpha \in \mathbb{Q}_{> 0}$ such that the spaces $(X,d)$ and $(H, \alpha \cdot \rho_H)$ are isometric?

1

There are 1 best solutions below

0
On BEST ANSWER

Your metric $\rho_H$ has the property that for any $a, b, c, d $ with $\rho_H(a,b) > \rho_H(c,d) > 0$ there is $e$ with $\rho_H(a,b) = \rho_H(a,e) + \rho_H(e,b)$. So does its rescaled version $\alpha \cdot \rho_H$. But it's easy to find finite metric spaces that don't have this property.