Journal of Combinatorics
Volume 3 (2012)
Chain-making games in grid-like posets
Pages: 633 – 649
We study the Maker-Breaker game on chains in a poset. In a chain-product poset, the maximum size of a chain that Maker can guarantee building is $k-$[$r/2$], where $k$ is the maximum size of a chain in the poset and $r$ is the maximum size of a factor chain. We also study a variant where Maker must build a chain in increasing order, called the ordered chain game. Within the bottom $k$ levels of a product of $d$ chains of size at least $k$, Walker can guarantee a chain that hits all levels if $d\ge14$; this result uses a solution to Conway's Angel-Devil game. When $d=2$, the maximum that Walker can guarantee is only $2/3$ of the levels; when $d=3$, Walker cannot guarantee all levels, as shown by Clarke, Finbow, Fitzpatrick, Messenger, and Nowakowski by studying a related game. It is unknown whether Walker can guarantee all levels when $4\le d\le 13$. In the product of two chains of equal size, Walker can guarantee $2/3$ of the levels asymptotically.
Published 21 February 2013