The general position number of integer lattices

Abstract

The general position number $\mathrm{gp}(G)$ of a connected graph $G$ is the cardinality of a largest set $S$ of vertices such that no three pairwise distinct vertices from $S$ lie on a common geodesic. The $n$-dimensional grid graph $\pn$ is the Cartesian product of $n$ copies of the two-way infinite path $P_{\infty }$. It is proved that if $n\in \mathbb{N}$, then $\mathrm{gp}(P_{\infty }^n)=2^{2^{n-1}}$. The result was earlier known only for $n\in \{1,2\}$ and partially for $n=3$.