# Separating pairs of points in R^n

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

-
Should there be a relation between $n$ and $k$? – François G. Dorais Oct 3 '13 at 14:07
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? – DmitryZ Oct 3 '13 at 16:13
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$. – TOM Oct 3 '13 at 20:12
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$? – usul Oct 3 '13 at 21:35
Yes, for the last comment. – TOM Oct 4 '13 at 19:35

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