Submit progress

on Erdős #1066 · graph theory / planar graphs

The statement

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}$ .

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.