Settling the no-$(k+1)$-in-line problem when $k$ is not small

Abstract

What is the maximum number of points that can be selected from an $n\times n$ square lattice such that no $k+1$ of them are in a line? This has been asked more than $100$ years ago for $k=2$ and it remained wide open ever since. In this paper, we prove the precise answer is $kn$, provided that $k>C\sqrt{n\log n}$ for an absolute constant $C$. The proof relies on carefully constructed bi-uniform random bipartite graphs and concentration inequalities.

13 pages, 2 figures