Origen de un problema de teoría de grafos/geometría plana

Question

¿Alguien recuerda de dónde viene el siguiente problema?

Dejemos que $P_n$ sea un conjunto de $n$ puntos en el plano, y denotamos por $d$ la distancia mínima entre dos puntos cualesquiera de $P_n$ (es decir $d=\min\{d(p_i,p_j)|p_i\neq p_j\in P_n\}$ ). Entonces existe un subconjunto $X \subset P_n$ tal que para todo $p_i,p_j\in X$ , $d(p_i,p_j)>d$ y $|X|\geq\frac{n}{4}$

Si no recuerdo mal, se trataba de un problema abierto (que se resolvió con bastante facilidad utilizando el teorema de los cuatro colores). Sólo que no recuerdo quién lo planteó (presumiblemente Erdős, pero no estoy seguro) y cuándo.
Gracias de antemano.

Answer 1

Creo que te gustará Gyorgy Csizmadia, On the independence number of minimum distance graphs, disponible gratuitamente en http://www.math.nyu.edu/~csiz/cikkek/penz.ps

Csizmadia dice que Erdos pidió límites en 1983. El único artículo de Erdos que cita es Some combinatorial and metric problems in Geometry, en Intuitive Geometry, Colloquia Mathematica Societatis Janos Bolyai 48 (1985) 167-177. La aplicación de la FCT aparece en R. Pollack, Increasing the minimum distance of a set of points, J Combinatorial Theory Series A 40 (1985) 450.