Monochromatic $k$ in a row

Abstract

We study a variant of the $k$-in-a-row game in which players alternatively claim positions until a $k$-in-a-row is created among all claimed positions. This leads to the constraint near $k$-in-a-row avoiding on configurations and the associated problem of determining their extremal densities of such configurations. We investigate this problem on two types of boards: the grid ${\mathbb{Z}}^2$ and hypercubes $[k{]}^d$. For the grid ${\mathbb{Z}}^2$, we establish nearly tight bounds on the maximum density $D(k,{\mathbb{Z}}^2)$, showing that $D(k,{\mathbb{Z}}^2)=1-\frac{2}{k}$ whenever $3\nmid k$, and determine both $D(3,{\mathbb{Z}}^2)$ and $d(3,{\mathbb{Z}}^2)$ exactly. We also bound the minimum density $d(k,{\mathbb{Z}}^2)$ up to a gap of $(8+o(1))k^{-1}$. For hypercubes $[k{]}^d$, we derive asymptotic bounds on $D(k,[k{]}^d)$ up to order $k^{-2}$ and obtain the exact value of $d(k,[k{]}^d)$. Our results contrast with the classical no-$(k+1)$-in-line problem, a similar problem imposing different constraint, where the trivial upper bound is conjectured to be attainable.

24 pages