how many dimensions we need to represent weighted graph in metric space?
let's consider weighted(on edges) graph $G$ that is fully connected with $n$ vertices ($K_n$), let's assume that weights on edges are distances between vertices.
What conditions have to be met to have metric space with euclidean metric of some dimension (concretely $\Bbb{R}^k$ for some $k$ maybe even $k>n$) to embed this graph $G$ in this space? how to find $k=f(n)$
for sure one of these conditions is triangle inequality to begin with
similar question When can a weighted graph be embedded in a metric space?
The question you are asking is better restated in the following form: Suppose that $(X,d)$ is a finite metric space. What are the necessary and sufficient conditions for $(X,d)$ be isometrically embeddable in the Euclidean space $E^n$ for the given $n$?
There are two solutions to this problem going back to 1930s.
- The first one was given by Menger in
K. Menger, Untersuchungen über allgemeine Metrik. Mathematische Annalen, 100 (1928) 75–163.
and
K. Menger, New foundation of Euclidean geometry, Amer. J. of Math. 53(4) (1931), 721–745.
I will describe Menger's solution following
J. C. Bowers and P. L. Bowers, A Menger Redux: Embedding Metric Spaces Isometrically in Euclidean Space, The American Mathematical Monthly, 124:7 (2017), 621-636.
(See also this Wikipedia article.)
Define the Cayley-Menger determinant of $X=(X,d)$, $X=\{x_1,...,x_k\}$, as $$ \det D(X)= \left|\begin{array}{ccccc} d(x_1,x_1) & d(x_1,x_2) & ... & d(x_1, x_k) & 1\\ d(x_2,x_1) & d(x_2,x_2) & ... & d(x_2, x_k) & 1\\ \vdots & \vdots & ... & \vdots & \vdots\\ d(x_k,x_1) & d(x_k,x_2) & ... & d(x_k, x_k) & 1\\ 1 & 1 & ... & 1 & 0 \end{array}\right|. $$
Theorem 1. An $(n + 2)$-point metric space $(X,d)$ embeds isometrically in $E^n$ if and only if, for each subset $Y \subset X$, the Cayley-Menger determinant $\det D(Y)$ either vanishes or has the sign $(−1)^{|Y|}$, where $|Y |$ is the cardinality of $Y$, and $\det D(X)=0$.
Theorem 2. A finite metric space $X$ embeds isometrically in $E^n$ if and only if, when $X$ contains more than $n + 3$ points, then
(i) for every $Y \subset X$ with precisely $r \le n + 1$ points, the Cayley-Menger determinant $\det D(Y)$ either vanishes or has the sign $(−1)^r$, and
(ii) the determinant associated to each $n+2$ distinct points of X vanishes; and when X contains exactly $n + 3$ points, in addition to these conditions,
(iii) $\det D(X)=0$.
Note that there is no need for a separate discussion of the case when $|X|\le n+1$ since $X$ isometrically embeds in $E^n$ if and only if it isometrically embeds in $E^m$, $m\ge n$.
This is the solution that graph-theorists tend to like.
- The second solution was given by Schoenberg in
I.J. Schoenberg, On certain metric spaces arising from euclidean spaces by a change of metric and their imbedding in Hilbert space. Ann. Math. 38 (1937), p. 787-793.
This solution has led to the notion of (conditionally) negative kernels and it is liked by researchers in functional analysis.
Given a metric space $X=(X,d)$ of cardinality $N$, define its square distance matrix $M$ as the symmetric $N\times N$ matrix whose components $M_{ij}= d^2(x_i, x_j)$. Associated with this matrix, one has the quadratic form $$ q(v)= v^T M v. $$
Definition. Matrix $M$ is said to be of conditionally negative type if for each vector $v\in {\mathbb R}^N$ satisfying $$ \sum_{i=1}^N v_i=0, $$ satisfies $q(v)\le 0$. In other words, the quadratic form is negative semidefinite on the subspace defined by $\sum_{i=1}^N v_i=0$.
Theorem 3. A finite metric space $X=(X,d)$ isometrically embeds in some Euclidean space $E^n$ if and only if the associated square distance matrix $M$ is of conditionally negative type.
The minimal dimension of the euclidean space $E^n$ (in which $X$ isometrically embeds) is the rank of the matrix $C$ with the matrix entries $$ C_{ij} =\frac{1}{2} (M_{iN} + M_{jN} − M_{ij}).$$