Pairing strategies for the Maker-Breaker game on the hypercube with subcubes as winning sets

Abstract

We consider the Maker-Breaker positional game on the vertices of the $n$-dimensional hypercube $\{0,1{\}}^n$ with $k$-dimensional subcubes as winning sets. We describe a pairing strategy which allows Breaker to win if $n$ is a power of 4 and $k\ge n/4+1$. Our results also imply that for all $n\ge 3$ there is a Breaker's win pairing strategy if $k\ge \lfloor \frac{3}{7}n\rfloor +1$.

24 pages