Let $A$ be a set of $2k$ points in $\mathbb{R}^n$ such that no open set in $\mathbb{R}^n$ of diameter $2$ contains more than $k$ of these points. What is the largest possible distance $r_n>0$ one can guarantee so that for all $k$ we can pair up $2k$ points under the mentioned condition so that each pair of points is at least $r_n$ apart? It is not difficult to show that $1\leq r_n \leq 2$ ($2$ comes from just taking $|A|=2$ and proving that one can always have them at distance $1$, one can build a distance graph so that two point from $A$ are joined if they are at least $1$ apart - such graph has minimum degree at least $k$ and so has a Hamilton cycle).
6
-
1$\begingroup$ Should there be a relation between $n$ and $k$? $\endgroup$– François G. DoraisCommented Oct 3, 2013 at 14:07
-
$\begingroup$ And I suppose $n$ in $\mathbb{R}^n$ is not the same $n$ which is the maximal number of points in an open set of diameter 2? $\endgroup$– DmitryZCommented Oct 3, 2013 at 16:13
-
$\begingroup$ Sorry, Dmitry, this was a misprint - n has no relation to the number of point and the condition imposed on the set A. Francois: there is no relation between $n$ and $k$. $\endgroup$– TOMCommented Oct 3, 2013 at 20:12
-
$\begingroup$ I think the confusion might be, writing $r_n$ seems to imply that this value should have no dependence on $k$. Do you want, for fixed $n$, the largest possible $r_n$ that holds for every possible $k$? $\endgroup$– usulCommented Oct 3, 2013 at 21:35
-
$\begingroup$ Yes, for the last comment. $\endgroup$– TOMCommented Oct 4, 2013 at 19:35
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
Consider a regular $2k-1$-gon of diameter $2$, meaning the distance between the two most distant vertices is $2$. Then only $k-1$ vertices can be in any set of diameter less than two, becsuse any set of $k$ vertices contains a maximum-distance pair. So the set of vertices plus the center form a set satisfying your condition. As $k$ goes to $\infty$, the polygon approaches a circle of radius $1$, so $r_n=1$ for $n\geq 2$.
answered Oct 6, 2013 at 23:11