No-$(k+1)$-in-line problem for large constant $k$
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911222035644416 |
|---|---|
| author | Grebennikov, Alexandr Kwan, Matthew |
| author_facet | Grebennikov, Alexandr Kwan, Matthew |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17743 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | No-$(k+1)$-in-line problem for large constant $k$ Grebennikov, Alexandr Kwan, Matthew Combinatorics Metric Geometry 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. |
| title | No-$(k+1)$-in-line problem for large constant $k$ |
| topic | Combinatorics Metric Geometry |
| url | https://arxiv.org/abs/2510.17743 |