# zbMATH — the first resource for mathematics

Chain-making games in grid-like posets. (English) Zbl 1270.05069
Summary: 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-\lfloor r/2\rfloor$$, 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 \geq 14$$; this result uses a solution to J. H. Conway’s Angel-Devil game [Games of no chance. Combinatorial games at MSRI. Workshop, July 11–21, 1994 in Berkeley, CA, USA. Cambridge: Cambridge Univ. Press. Math. Sci. Res. Inst. Publ. 29, 3–12 (1997; Zbl 0872.90133)]. 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 N. E. Clarke et al. [Australas. J. Comb. 43, 91–102 (2009; Zbl 1155.05328)] by studying a related game. It is unknown whether Walker can guarantee all levels when $$4 \leq d \leq 13$$. In the product of two chains of equal size, Walker can guarantee 2/3 of the levels asymptotically.
##### MSC:
 05C57 Games on graphs (graph-theoretic aspects) 06A07 Combinatorics of partially ordered sets 91A46 Combinatorial games
##### Keywords:
Maker-Breaker game; chain-product poset
Full Text: