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

• @MoisheKohan euclidean, I added this information to question Commented Feb 28, 2020 at 8:28
• The problem of characterizing finite metric spaces which admit isometric embeddings in $E^n$ was solved by Menger and, a bit differently, by Shoenberg, in 1930s. I will describe their solutions later. Commented Feb 28, 2020 at 17:10

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.

1. 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.

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.

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

• thanks, although one more question: are there any conditions to on determining $k=f(n)$? for example having $K_4$ when we can embed it in $R^2$? is it possible to compute some sort lower boundary on $k$? Commented Mar 2, 2020 at 18:16
• @quester: The issue is that the smallest $k$ such that $(X,d)$ embeds isometrically in $E^k$ depends not only on $|X|$ but also on the specific metric on $X$. Some metric do not embed isometrically in any Euclidean space. Commented Mar 2, 2020 at 18:38
• ok but is it solved somewhere specifically for $R^k$ space with "standard" metric $L_2$? Commented Mar 2, 2020 at 20:44
• @quester: Yes, this is denoted $E^k$ in my answer. Commented Mar 2, 2020 at 21:00
• thank you sir!! Commented Mar 2, 2020 at 21:03

Obvious necessary conditions are non-negativity of all edge weight and the triangle inequalities. When these conditions are satisfied, we have a problem on an embedding a finite metric space into $$\Bbb R^k$$ with minimum $$k$$. More than six years ago I answered a similar question for an embedding into a plane, and now I can reformulate my conjecture as follows.

Conjecture. For any natural $$k$$, a metric space $$(X,d)$$ can be isometrically embedded in the space $$\mathbb R^k$$ endowed with the standard metric iff each $$k+2$$-point subspace of $$(X,d)$$ can be isometrically embedded in $$\mathbb R^k$$. In particular, $$(X,d)$$ can be isometrically embedded in the space $$\mathbb R^{|X|-1}$$, provided $$|X|>1$$.

The construction of the embedding should be similar to that given in my answer.

• Your conjecture is almost correct. It is a theorem due to Menger that: Let $X$ be a metric space whose cardinality is not equal to $n + 3$. Then $X$ embeds isometrically in the Euclidean space $E^n$ if and only if each of its finite subsets with at most $n + 2$ elements embeds isometrically in $E^n$. There are counter-examples for sets of cardinality $n+3$. Commented Feb 28, 2020 at 14:29