MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 6 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.