×

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
PDF BibTeX XML Cite
Full Text: DOI arXiv