Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

up vote 2 down vote accepted

I think you'll enjoy Gyorgy Csizmadia, On the independence number of minimum distance graphs, freely available at http://www.math.nyu.edu/~csiz/cikkek/penz.ps

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|improve this answer
    
Great, thanks a lot! –  Dennis Gulko May 17 '11 at 7:32
add comment

Your Answer

 
discard

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.