No-$(k+1)$-in-line problem for large constant $k$
Preprint
Abstract
How many points can be placed in an $n\times n$ grid so that every (affine) line contains at most $k$ points? We prove that for $n \ge k \ge 10^{37}$ the maximum number of points is exactly $kn$. Our proof builds on the recent work of Kovács, Nagy, and Szabó (who proved an analogous result when $k$ is at least about $\sqrt{n \log n}$), incorporating ideas of Jain and Pham. Using the same approach, we also obtain new bounds for higher-dimensional extensions of this problem.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Evasive Sets, Covering by Subspaces, and Point-Hyperplane IncidencesDiscrete & Computational Geometry, 2023
- Threshold for Steiner triple systemsGeometric and Functional Analysis, 2023
- Sandwiching biregular random graphsCombinatorics, Probability and Computing, 2022
- Forbidden Configurations in Discrete Geometry2018
- Sandwiching random graphs: universality between random graph modelsAdvances in Mathematics, 2004
- On counting point-hyperplane incidencesComputational Geometry, 2003
- Asymptotic formulae for point lattices of bounded determinant and subspaces of bounded heightDuke Mathematical Journal, 1968