Determining the maximum number of distance relationships that can be defined between points in Euclidean space - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T10:00:42Z http://mathoverflow.net/feeds/question/98130 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/98130/determining-the-maximum-number-of-distance-relationships-that-can-be-defined-betw Determining the maximum number of distance relationships that can be defined between points in Euclidean space Vincent Tjeng 2012-05-27T16:37:19Z 2012-05-28T16:54:11Z <p>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. </p> <p>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</p> <ol> <li>There exists some configuration of $m$ points satisfying all the distance relationships, OR</li> <li>There exists a triplet of points for which all three pairwise distances are defined, and these three distances do not satisfy the triangle inequality.</li> </ol> <p>The question above is similar to this one <a href="http://mathoverflow.net/questions/97611/reconstructing-an-euclidean-point-cloud-from-their-pairwise-distances" rel="nofollow">http://mathoverflow.net/questions/97611/reconstructing-an-euclidean-point-cloud-from-their-pairwise-distances</a> (and others like it) but I believe the math involved is different.</p> http://mathoverflow.net/questions/98130/determining-the-maximum-number-of-distance-relationships-that-can-be-defined-betw/98134#98134 Answer by Will Sawin for Determining the maximum number of distance relationships that can be defined between points in Euclidean space Will Sawin 2012-05-27T17:38:29Z 2012-05-28T16:54:11Z <p>I have no answer but three different comments. It seems unwieldy to post these all as one or more comments.</p> <p>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$.</p> <p>This can cause a violation of monotonicity, where $k$ satisfies your condition and $k+1$ does not. Presumably you don't want this?</p> <p>2: I think probability is a red herring, since there is no probability measure here.</p> <p>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.</p> http://mathoverflow.net/questions/98130/determining-the-maximum-number-of-distance-relationships-that-can-be-defined-betw/98143#98143 Answer by Sergei Ivanov for Determining the maximum number of distance relationships that can be defined between points in Euclidean space Sergei Ivanov 2012-05-27T18:31:37Z 2012-05-27T18:31:37Z <p>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.</p> <p>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.</p> <p>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.</p>