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.