MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 3 Rollback to Revision 1

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 exist $a$ exists a triplet of points ${P_1, P_2, ... P_a}$ where for which all the three pairwise 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$.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.
show/hide this revision's text 2 Edited question to exclude cases pointed out by @Will

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 exist $a$ points for which ${P_1, P_2, ... P_a}$ where all three pairwise the distances $P_i P_{i+1}$ are defined , and these three distances do not satisfy the triangle inequality.$P_1 P_a>P_1 P_2+P_2 P_3 +...+P_{a-1}P_a$.

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.
show/hide this revision's text 1

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