标题： 当$k$不是小时解决无$(k+1)$-in-line 问题 显示英文标题

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

摘要： 在$n \times n$平方格点上，最多可以选取多少个点，使得其中没有$k+1$个点共线？ 这个问题早在$100$年前就针对$k=2$提出了，但从那时起一直未被解决。 在本文中，我们证明了精确答案是$kn$，前提是$k>C\sqrt{n\log{n}}$对于一个绝对常数$C$而言成立。 该证明依赖于精心构建的双均匀随机二部图和集中不等式。 显示英文摘要

摘要： 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.