5
$\begingroup$

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.

1 Answers 1

2

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.

  • 0
    Great, thanks a lot!2011-05-17