Determining the maximum number of distance relationships that can be defined between points in Euclidean space

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