Erdős #1070 · geometry

In other words, estimate the minimal independence number of a unit distance graph with $n$ vertices. If $\omega$ is the independence number and $\chi$ is the chromatic number then $\omega \chi\geq n$, and hence $f(n)\geq n/\chi$, where $\chi$ is the answer to the Hadwiger-Nelson problem [508].

The Moser spindle shows $f(n)\leq \frac{2}{7}n\approx 0.285n$. Larman and Rogers [LaRo72] noted that if $m_1$ is the supremum of the upper densities of measurable subsets of $\mathbb{R}^2$ which have no unit distance pairs then

Croft [Cr67] gave the best-known lower bound of $m_1\geq 0.22936$ and hence

Ambrus, Csiszárik, Matolcsi, Varga, and Zsámboki [ACMVZ23] have proved that $m_1\leq 0.247$, and hence this approach cannot achieve $f(n)\geq n/4$. See [232] for more on $m_1$.

Matolcsi, Ruzsa, Varga, and Zsámboki [MRVZ23] have improved the upper bound to

They conjecture that $m_1=0.22936\cdots$ (the lower bound of Croft mentioned above) and $f(n)=(1/4+o(1))n$.

If we also insist that no two points are distance $<1$ apart then this is problem becomes [1066].

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.