North–East lattice paths avoiding k collinear points via satisfiability

Advances in Applied Mathematics 2026 Open access

Read full text
Authors: Aaron Barnoff, Curtis Bright
DOI: 10.1016/j.aam.2026.103112
Cited by: 0

Abstract

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 ≤ 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.

Fields of Study & Subjects

Computational Geometry and Mesh Generation Complexity and Algorithms in Graphs Facility Location and Emergency Management

Publication details

Journal / source
Advances in Applied Mathematics
Volume
179
Pages
103112–103112
Publication date
15 May 2026
Language
EN