The extensible No-Three-In-Line problem

Nagy, Dániel and Nagy, Zoltán Lóránt and Woodroofe, Russ (2023) The extensible No-Three-In-Line problem. EUROPEAN JOURNAL OF COMBINATORICS, 114. ISSN 0195-6698

Text the_extensible_no_three-in-line.pdf Restricted to Repository staff only until 31 December 2025. Download (334kB) | Request a copy

Abstract

The classical No-Three-In-Line problem seeks the maximum number of points that may be selected from an n × n grid while avoiding a collinear triple. The maximum is well known to be linear in n. Following a question of Erde, we seek to select sets of large density from the infinite grid Z2 while avoiding a collinear triple. We show the existence of such a set which contains Θ(n/ log1+ε n) points in [1, n]2 for all n, where ε > 0 is an arbitrarily small real number. We also give computational evidence suggesting that a set of lattice points may exist that has at least n/2 points on every large enough n × n grid.

Actions (login required)

Edit Item