Maker-Breaker games on infinite graphs with precolored edges

Abstract

Suppose we are given graphs $B$ and $G$. In the classical Maker-Breaker game $\text{MB}(B,G)$ two players, Maker and Breaker, alternately claim edges of $B$ and it is Maker's goal to claim a copy of $G$ in $B$, while it is Breaker's goal to prevent that. In this paper, $B$ is the countably infinite complete graph $K_{{\aleph }_0}$ and we are given finitely many infinite subgraphs $G_1,\dots ,G_k\subseteq B$. In the color preserving game, it will be Maker's goal to claim a $K_{{\aleph }_0}\subseteq B$, which contains infinitely many edges of each $G_i$. We present sufficient winning conditions for both Maker and Breaker, if $k>1$ and a full characterization of the game, if $k=1$. This partly answers a question of Bowler, Emde and Gut. In the (partially) pattern preserving game, it is Maker's goal to claim a copy $K$ of $K_{{\aleph }_0}$, such that $G_i\cap K$ is isomorphic to (a subgraph of) $G_i$ for all $i\in [k]$. In those games, we investigate some patterns for which Maker has a winning strategy.

26 pages, 10 figures