Infinite walks in small dimensions avoid long collinear point runs
Brown-Gerver-Ramsey Theorems in Small Dimensions
Discrete Mathematics
Summary
This work studies paths that move step-by-step in a multi-dimensional grid without hitting too many points in a straight line. The authors show such infinite paths exist for certain combinations of dimensions and allowed straight-line lengths. They notably improve an earlier result for three dimensions by reducing a large previous number to a much smaller one. Their findings also connect to the creation of infinite sequences that avoid certain repeated patterns in a relaxed way.
What this means in practice
- •For discrete mathematicians: Use improved infinite paths in small dimensions to construct sequences avoiding certain repetitive patterns with better bounds.
- •For coding theorists: Apply findings to design sequences over small alphabets that avoid weakly abelian repeats for error detection schemes.
A theory result. No direct application yet.
Authors
Stijn Cambie, Erik Kalviainen, J. Shallit
Abstract
We consider infinite walks in $\mathbb{N}^k$ with standard unit basis vector steps that avoid $t$ collinear points, and show that these walks exist for $(k,t) \in \{(6,3), (4,4), (3,7)\}$. In particular, our construction for $k = 3$ improves the previous bound $189$, obtained by Lidbetter, to $7$. Our results also imply the existence of infinite words over small finite alphabets that are weakly abelian squarefree (resp., weakly abelian cubefree, weakly abelian 6th-power-free).