학술

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

arXiv Math
CC BY
이 매체는 공공·자유 라이선스로 본문을 직접 표시합니다.

Abstract

What is the maximum number of points that can be selected from an $n\times n$ square lattice so that no $k+1$ of them are collinear?

This was asked more than $100$ years ago for $k=2$ and it remained wide open ever since.

In this paper, we prove the exact answer is $kn$, provided that $ n\ge k\ge C\log n$ for an absolute constant $C<20$.

The proof relies on carefully constructed block-uniform random bipartite graphs and concentration inequalities.

관련 뉴스