North–East lattice paths avoiding k collinear points via satisfiability
Advances in Applied Mathematics · 2026-09 · 179 · 103112
DOI: 10.1016/j.aam.2026.103112 ↗Kurz gefasst
Fachartikel in der Zeitschrift Advances in Applied Mathematics, 2026-09. Verfasst von Aaron Barnoff und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Natural Sciences and Engineering Research Council of Canada.
Abstract (Originalsprache)
We investigate the Gerver-Ramsey collinearity problem of determining the maximum number of points in a north-east lattice path without $k$ collinear points. Using a satisfiability solver, up to isomorphism we enumerate all north-east lattice paths avoiding $k$ collinear points for $k \leq 6$. We also find a north-east lattice path avoiding $k = 7$ collinear points with 327 steps, improving on the previous best length of 260 steps found by Shallit.
Förderung
- Natural Sciences and Engineering Research Council of Canada
Zitieren
APA
Barnoff, A., & Bright, C. (2026). North–East lattice paths avoiding k collinear points via satisfiability. Advances in Applied Mathematics, 179, 103112. https://doi.org/10.1016/j.aam.2026.103112
Vancouver
Barnoff A, Bright C. North–East lattice paths avoiding k collinear points via satisfiability. Advances in Applied Mathematics. 2026;179:103112. doi:10.1016/j.aam.2026.103112
BibTeX
@article{Barnoff2026,
author = {Barnoff, Aaron and Bright, Curtis},
title = {North–East lattice paths avoiding k collinear points via satisfiability},
journal = {Advances in Applied Mathematics},
year = {2026},
volume = {179},
pages = {103112},
doi = {10.1016/j.aam.2026.103112}
}
EUVIMED