No-three-in-line sets on the checkerboard grid
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918492881551360 |
|---|---|
| author | Prellberg, Thomas |
| author_facet | Prellberg, Thomas |
| contents | The classical no-three-in-line problem asks for the largest number (D(n)) of points that can be chosen from an (n \times n) grid with no three collinear. We study the checkerboard-restricted variant in which all chosen points lie in one fixed parity class of (x+y \pmod 2). Let (D_{\mathrm{mono}}(n)) be the corresponding optimum. The slope-(\pm1) diagonals give the elementary bound (D_{\mathrm{mono}}(n) \le 2n-2).
The main tool is a four-direction linear-programming relaxation on a fixed parity class, using rows, columns, and the two diagonal families of slopes (\pm1). For the ordinary square-grid problem this relaxation is trivial, but on the checkerboard it gives substantially tighter finite bounds. After symmetry reduction, the dual relaxation has three one-dimensional forms, according to the parity of (n) and the chosen colour class.
The main rigorous result is an exact continuum dual certificate for the formal continuum problem associated with the scaled odd-fat case. We construct explicit nonnegative functions satisfying the continuum obstacle inequalities and having objective value (α), where (401α^3-1744α^2+2240α-768=0) and (α) is the middle real root. This proves the upper bound (Λ_{\mathrm{fat}}\leα) for the odd-fat continuum relaxation. Finite LP computations are consistent with (α) as a limiting slope, and exact small-(n) data suggest the same scale for the original checkerboard optimum. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_09215 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | No-three-in-line sets on the checkerboard grid Prellberg, Thomas Combinatorics Primary 52C10, Secondary 05B40, 90C05 The classical no-three-in-line problem asks for the largest number (D(n)) of points that can be chosen from an (n \times n) grid with no three collinear. We study the checkerboard-restricted variant in which all chosen points lie in one fixed parity class of (x+y \pmod 2). Let (D_{\mathrm{mono}}(n)) be the corresponding optimum. The slope-(\pm1) diagonals give the elementary bound (D_{\mathrm{mono}}(n) \le 2n-2). The main tool is a four-direction linear-programming relaxation on a fixed parity class, using rows, columns, and the two diagonal families of slopes (\pm1). For the ordinary square-grid problem this relaxation is trivial, but on the checkerboard it gives substantially tighter finite bounds. After symmetry reduction, the dual relaxation has three one-dimensional forms, according to the parity of (n) and the chosen colour class. The main rigorous result is an exact continuum dual certificate for the formal continuum problem associated with the scaled odd-fat case. We construct explicit nonnegative functions satisfying the continuum obstacle inequalities and having objective value (α), where (401α^3-1744α^2+2240α-768=0) and (α) is the middle real root. This proves the upper bound (Λ_{\mathrm{fat}}\leα) for the odd-fat continuum relaxation. Finite LP computations are consistent with (α) as a limiting slope, and exact small-(n) data suggest the same scale for the original checkerboard optimum. |
| title | No-three-in-line sets on the checkerboard grid |
| topic | Combinatorics Primary 52C10, Secondary 05B40, 90C05 |
| url | https://arxiv.org/abs/2605.09215 |