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

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

2012-05-27T16:37:19Z

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

There exists some configuration of $m$ points satisfying all the distance relationships, OR
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 by Will Sawin for Determining the maximum number of distance relationships that can be defined between points in Euclidean space

2012-05-27T17:38:29Z

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.

Answer by Sergei Ivanov for Determining the maximum number of distance relationships that can be defined between points in Euclidean space

2012-05-27T18:31:37Z

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.