No-three-in-line sets on the checkerboard grid
Abstract
The classical no-three-in-line problem asks for the largest number D(n) of points that can be chosen from an n× n grid with no three collinear; it remains open whether the elementary upper bound 2n is always attainable. We study a checkerboard-restricted variant in which all chosen points are monochromatic under the colouring of the grid by the parity of x+y. If Dmono(n) denotes the largest number of monochromatic points with no three collinear, the monochromatic diagonals already give Dmono(n)≤ 2n−2. The main object of the paper is a four-direction linear-programming relaxation on a fixed colour class, using rows, columns and the two diagonal families of slopes ±1. For the ordinary square-grid problem this relaxation gives the trivial bound; on the checkerboard it is substantially tighter, and for 2≤ n≤ 16 its floor agrees with the exact single-colour optimum except at four side lengths, where the gap is one. After symmetry reduction the dual relaxation has three one-dimensional reduced forms, according to the parity of n and the chosen colour class. The central construction is an exact continuum dual certificate for the continuum problem associated with the scaled symmetry-reduced odd-fat case: explicit nonnegative functions A and B satisfying the continuum obstacle inequalities, with objective value the middle real root α≈1.5768 of 401α3−1744α2+2240α−768=0. Combined with a continuum-to-discrete sampling theorem of Aujla, Prellberg and Sandhu, this certificate yields the asymptotic upper bound Dmono(n)≤αn+O(1). Finite LP computations are consistent with α as the exact limiting slope of the relaxation, and the exact small-n data suggest, more speculatively, that the true checkerboard optimum tracks the same scale.
Related
- Moment obstructions and continuum-to-discrete bounds for checkerboard no-three-in-line sets
- Minimal Resolving Sets in Rectangular Grid Graphs: A Complete Characterization and Enumeration
- A superlinear improvement on line-free sets in 𝔽p3
- A Massively Parallel Three-Grid Preconditioner for the High-Frequency Helmholtz Equation
- Non-adjacent triples of cells in a triangular grid: proofs of three conjectured generating functions
BibTeX
@misc{prellberg2026nothreeinline,
title = {{No-three-in-line sets on the checkerboard grid}},
author = {Thomas Prellberg},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.09215},
eprint = {2605.09215},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.09215},
}
RIS
TY - UNPB
TI - No-three-in-line sets on the checkerboard grid
AU - Thomas Prellberg
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2605.09215
UR - https://arxiv.org/abs/2605.09215
AB - The classical no-three-in-line problem asks for the largest number D(n) of points that can be chosen from an n× n grid with no three collinear; it remains open whether the elementary upper bound 2n is always attainable. We study a checkerboard-restricted variant in which all chosen points are monochromatic under the colouring of the grid by the parity of x+y. If D_mono(n) denotes the largest number of monochromatic points with no three collinear, the monochromatic diagonals already give D_mono(n)≤ 2n−2. The main object of the paper is a four-direction linear-programming relaxation on a fixed colour class, using rows, columns and the two diagonal families of slopes ±1. For the ordinary square-grid problem this relaxation gives the trivial bound; on the checkerboard it is substantially tighter, and for 2≤ n≤ 16 its floor agrees with the exact single-colour optimum except at four side lengths, where the gap is one. After symmetry reduction the dual relaxation has three one-dimensional reduced forms, according to the parity of n and the chosen colour class. The central construction is an exact continuum dual certificate for the continuum problem associated with the scaled symmetry-reduced odd-fat case: explicit nonnegative functions A and B satisfying the continuum obstacle inequalities, with objective value the middle real root α≈1.5768 of 401α^3−1744α^2+2240α−768=0. Combined with a continuum-to-discrete sampling theorem of Aujla, Prellberg and Sandhu, this certificate yields the asymptotic upper bound D_mono(n)≤αn+O(1). Finite LP computations are consistent with α as the exact limiting slope of the relaxation, and the exact small-n data suggest, more speculatively, that the true checkerboard optimum tracks the same scale.
ER -