Randomised algebraic constructions for the no-$(k+1)$-in-line problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909731485908992 |
|---|---|
| author | Kovács, Benedek Nagy, Zoltán Lóránt Szabó, Dávid R. |
| author_facet | Kovács, Benedek Nagy, Zoltán Lóránt Szabó, Dávid R. |
| contents | The no-(k+1)-in line problem seeks the maximum number of points that can be selected from an $n \times n$ square lattice such that no $k+1$ of them are collinear. The problem was first posed more than $100$ years ago for the special case $k=2$ and has remained open ever since. The general problem was recently resolved in the case $k$ is not small compared to $n$, as Kovács, Nagy and Szabó proved that the upper bound $kn$ can be attained, provided that $k>C\sqrt{n\log{n}}$ for an absolute constant $C$.
In this paper, we show that $\left(1-\tfrac{2}{k}\right)kn \leq f_k(n)\leq kn$ and $\left(1-\tfrac{3}{k}\right)kn \leq f_k(n)\leq kn$ hold for every even $k$ and odd $k$, respectively, provided that $n$ is large enough. This is asymptotically tight as $k\to \infty$. Previously, only $f_k(n)=Ω(kn)$ was known due to Lefmann.
We present further improvements on the lower bounds for constant values of $k$ when $k<23$ holds. All these bounds are based on randomised algebraic constructions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_07632 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Randomised algebraic constructions for the no-$(k+1)$-in-line problem Kovács, Benedek Nagy, Zoltán Lóránt Szabó, Dávid R. Combinatorics The no-(k+1)-in line problem seeks the maximum number of points that can be selected from an $n \times n$ square lattice such that no $k+1$ of them are collinear. The problem was first posed more than $100$ years ago for the special case $k=2$ and has remained open ever since. The general problem was recently resolved in the case $k$ is not small compared to $n$, as Kovács, Nagy and Szabó proved that the upper bound $kn$ can be attained, provided that $k>C\sqrt{n\log{n}}$ for an absolute constant $C$. In this paper, we show that $\left(1-\tfrac{2}{k}\right)kn \leq f_k(n)\leq kn$ and $\left(1-\tfrac{3}{k}\right)kn \leq f_k(n)\leq kn$ hold for every even $k$ and odd $k$, respectively, provided that $n$ is large enough. This is asymptotically tight as $k\to \infty$. Previously, only $f_k(n)=Ω(kn)$ was known due to Lefmann. We present further improvements on the lower bounds for constant values of $k$ when $k<23$ holds. All these bounds are based on randomised algebraic constructions. |
| title | Randomised algebraic constructions for the no-$(k+1)$-in-line problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.07632 |