North-East Lattice Paths with Few Collinear Vertices

Let $A(k)$ be the largest possible number of moves in a north-east lattice path whose visited vertices contain no $k$ collinear points. Gerver (1979) and Gerver and Ramsey (1979) gave lower and upper bounds on $A(k)$ of the form $$\exp (\mathrm{\Omega }(\log (k{)}^2))\le A(k)\le \exp (O(k^4))\mathrm{.}$$ Improving upon these results, we show that $$\exp (\mathrm{\Omega }(k^{1\mathrm{/}3}))\le A(k)\le \exp ((\frac{2}{e}+o(1))(k-1{)}^2)\mathrm{.}$$