No-$(k+1)$-in-line problem for $k \geqslant 3$

Anubhab Ghosal, Ritesh Goenka, Alexandr Grebennikov, Peter Keevash, Matthew Kwan, Huy Tuan Pham

arXivarxiv/2607.05255Jul 6, 2026math.COscore 0

What is the maximum number of points one can place in an $n \times n$ grid such that every Euclidean line contains at most $k$ points? For $k = 2$, this is the notorious no-three-in-line problem of Dudeney. In this paper, we resolve this problem for all other $k$ (and sufficiently large $n$). Namely, for $k \geqslant 3$ and sufficiently large $n$, we show that this maximum is exactly $kn$. To prove this, our key observation is that in the regime $k \geqslant 3$, the problem is dominated in a certain statistical sense by the influence of a small number of "heavy" lines with many grid points.…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2607.05255
curl -X POST /api/v1/records/arxiv/2607.05255/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.05255/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'