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

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.

-
–  Anton Petrunin May 28 '12 at 20:42
Hi Anton, I'm not sure whether the solutions there can be extended to $\mathbb R ^n$, but thanks for the tip. –  Vincent Tjeng May 29 '12 at 15:09

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.

-

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.

-
In comment 1, I assume you mean "quadrilateral" rather than "square" and in comment 3, "distances" rather than "questions"? In any case, thanks for pointing out the issue of the quadrilateral inequality. I'm looking at reformulating the question by replacing the condition on the triangle inequality with the following condition -- There exist $a$ points ${P_1, P_2, ... P_a}$ where all the distances $P_i P_{i+1}$ are defined and $P_1 P_a>P_1 P_2+P_2 P_3 +...+P_{a-1}P_a$. However, does it make the question trivial? –  Vincent Tjeng May 28 '12 at 14:37
No. Sergei's answer still works, it just changes the numbers slightly. You need a stronger condition, that probably involves the words "positive semidefinite", to beat Sergei's example. –  Will Sawin May 28 '12 at 16:56