Erdős Problems

Tags Prizes

SOLVED

Let $t(n)$ be the minimum number of points in $\{1,\ldots,n\}^2$ such that the $\binom{t}{2}$ lines determined by these points cover all points in $\{1,\ldots,n\}^2$.

Estimate $t(n)$. In particular, is it true that $t(n)=o(n)$?

#798: [Gu81]

geometry

A problem of Erdős and Purdy, who proved $t(n) \gg n^{2/3}$.

Resolved by Alon [Al91] who proved $t(n) \ll n^{2/3}\log n$.