Papers for

discrete mathematicians

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Infinite walks in small dimensions avoid long collinear point runs

Brown-Gerver-Ramsey Theorems in Small Dimensions

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

Thu 17 SeptDiscrete Mathematics

The gist

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.

Open → 2609.20366v1