Erdős Problem #1066

declared status 'open'. Formalized: no. Let $G$ be a graph given by $n$ points in $\mathbb{R}^2$, where any two distinct points are at least distance $1$ apart, and we draw an edge between two points if they are distance $1$ apart. Let $g(n)$ be maximal such that any such graph always has an independent set on at least $g(n)$ vertices. Estimate $g(n)$, or perhaps $\lim \frac{g(n)}{n}$. Current best: This lower bound has been improved to $\frac{9}{35}n$ by Csizmadia [Cs98] and then $\frac{8}{31}n$ by Swanepoel [Sw02]. The current record bounds are therefore$$\frac{8}{31}n \approx 0.258n \leq g(n) \leq 0.3125n=\frac{5}{16}n.$$Pollack [Po85] also reports a letter from Erd\H{o}s which poses the more general problem of, given $n$ points in $\mathbb{R}^d$ with minimum distance $1$, let $g_d(n)$ be maximal such that there always exist at least $g_d(n)$ many points which have minimum distance $>1$. Is it true that $g_d(n) \gg n/d$ in general? The upper bound $g_d(n) \ll n/d$ is trivial, considering widely spaced unit simplices. Prize: no. Tags: graph theory, planar graphs.

Notation is rendered from the stored source. The pinned checkout remains the exact record.