Question

Let there be $m$ points in the Euclidean space $\mathbb R^n$. Randomly choose $k$ distinct pairs of these $m$ points, and assign a random (positive) value for the Euclidean distance between each of these $k$ pairs.

Determine the maximum value of $k$ as a function of $n$ and $m$ such that, for any random choice of $k$ distinct pairs of points and the Euclidean distances between the points, either

1. There exists some configuration of $m$ points satisfying all the distance relationships, OR
2. There exists a triplet of points for which all three pairwise distances are defined, and these three distances do not satisfy the triangle inequality.

The question above is similar to this one http://mathoverflow.net/questions/97611/reconstructing-an-euclidean-point-cloud-from-their-pairwise-distances (and others like it) but I believe the math involved is different.

Answer 1

The following 6 distances between 4 points $a,b,c,d$ can not be realized in a Euclidean space of any dimension: $d(a,b)=d(b,c)=d(a,c)=1$ and $d(a,d)=d(b,d)=d(c,d)=0.51$, although all triangle inequalities are satisfied and even strict.

Adding any number of points and assigning any set of other distances to be equal to 1 does not change this fact. So no $k\ge 6$ is good if $m\ge 4$. As Will Sawin showed, $k=4$ is not good either. For $k=5$, add a point $E$ and the relation $d(A,E)=1$ to Will's example.

Thus the answer to the question as stated is $k=3$ for all $n\ge 2$ and $m\ge 5$. If $m=4$ and $n\ge 2$, one can take $k=5$. If $n=1$ and $m\ge 3$, the answer is $k=2$, obviously. In the remaining cases ($n\ge 2$, $m\le 3$ and $n=1$, $m\le 2$) one can define all the $m(m-1)/2$ distances.

Answer 2

I have no answer but three different comments. It seems unwieldy to post these all as one or more comments.

1: Let $k=4$, and form a quadrilateral otherwise disconnected to other vertices. There are no triangles to violate the triangle inequality, but you can still violate the quadrilateral inequality: $AB \leq BC+CD+AD$.

This can cause a violation of monotonicity, where $k$ satisfies your condition and $k+1$ does not. Presumably you don't want this?

2: I think probability is a red herring, since there is no probability measure here.

3: An obvious upper bound is, if there are at least $n+2$ choose $2$ distances, you can make $n+2$ vertices into a regular $n+1$-simplex and do something with the other vertices and edges, to get a graph that embeds in some metric space but not $\mathbb R^n$. So $(n+2)(n+1)/2-1$ is an upper bound.