Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

Does anyone remember where does the following problem comes from:

Let $P_n$ be a set of $n$ points on the plane, and denote by $d$ the minimal distance between any two points of $P_n$ (i.e. $d=\min\{d(p_i,p_j)|p_i\neq p_j\in P_n\}$). Then there exists a subset $X \subset P_n$ such that for all $p_i,p_j\in X$, $d(p_i,p_j)>d$ and $|X|\geq\frac{n}{4}$

If I remember correctly, this was an open problem (which was solved quite easily using the four color theorem). I just can't remember who asked it (presumably Erdős, but i'm not sure) and when.
Thanks in advance.

share|cite|improve this question
up vote 2 down vote accepted

I think you'll enjoy Gyorgy Csizmadia, On the independence number of minimum distance graphs, freely available at

Csizmadia says Erdos asked for bounds in 1983. The only Erdos paper he cites is Some combinatorial and metric problems in Geometry, in Intuitive Geometry, Colloquia Mathematica Societatis Janos Bolyai 48 (1985) 167-177. The application of the FCT appears in R. Pollack, Increasing the minimum distance of a set of points, J Combinatorial Theory Series A 40 (1985) 450.

share|cite|improve this answer
Great, thanks a lot! – Dennis Gulko May 17 '11 at 7:32

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.